# Generative Machine Learning algorithms on tree structure

I'm looking into PCFG sentence grammar dependency structure parsing using StanfordNLP PCFG parser. It generates tree structures represented as a string like this:

Happy new year => (ROOT (VP (VBN Happy) (NP (JJ new) (NN year))))

Or in a more visual way, the tree structure looks like this:

(ROOT
(VBN (JJ Happy)
(NP (JJ new) (NN year))))

Since some machine learning algorithms are generative, and I'm wondering if I group tree structures into two sets: one set contains sentences with negative emotions, one set on positive emotions. Can I use the machine learning algorithm to get the most commonly occurred subtree structure within each set?

I'm very sorry if I caused any confusion. First of all, I want to know if this problem is solvable in the realm of machine learning.

Remember topic modeling? Where the algorithm reads large chunks of text and generate similar topics and return keyword strings grouped together as a topic? One topic could be: Gun, ship, sailer, ocean, fish, war, Gulf, oil

It provides an insight into what computer understands what this document might be talking about, so we can compare it with what humans think.

However, what I want to do, is ask the question if I can find common syntactical subtree structures in a sentence that might indicate the attribute of this sentence: negative or positive.

No, I am not asking for a sentiment analysis classifier, and that is not my interest at all.

For example, (this is an unpublished study right now), as us humans, we can say certain things about the future, and it will appear in a special structure, like "I will go to the mall" or "I'm going to jogging." You can see that "will" or "going to" might appear in many sentences, and serve as a common grammatical/syntactical structure. Those structures can be spotted by us human beings (namely linguists), however, is it possible to let machine find such common pattern?

I know in data science, or in realm of machine learning, people use algorithms to find/generate common patterns. I can group my parsed sentences (as tree structures represented above) into two groups: negative group and positive group (NOT emotions, just names for two groups), and then I want to use this algorithm to see if one or multiple subtree structures are very common among the group so I can extract them out.

As I stated before, I only need two things:

1. Is this solvable in Machine Learning realm?
2. If it is, which algorithm should I use?
• I'm sorry, I can't understand what you are asking. What machine learning algorithm? You seem to be referring to some machine learning algorithm, but you haven't told us what one. Also, your next-to-last sentence is very hard to parse. Try breaking it down into smaller pieces, and elaborate on each piece and how they relate? You might also try adding an example. Finally, you might tell us what you have tried or what your thoughts are. – D.W. Jul 5 '14 at 6:20
• you seem to be presuming or interested in testing the hypothesis that the tree structure of the sentence has an influence on whether it contains negative or positive emotions? aka sentiment analysis? thats just a shot in the dark right? yes there are ML (classification) algorithms that can work with unstructured problems such as this but it can require a lot of user ingenuity.... – vzn Jul 5 '14 at 15:03
• @D.W. Thank you for your interest! I typed many more sentences to help clarify what I mean. – windweller Jul 6 '14 at 22:49
• @vzn Thank you for your help as well :) I'm not looking for a sentiment analysis classifier (which is based on frequency counting classification, however, I'm dealing with tree structures, not flat sentences). – windweller Jul 6 '14 at 22:50
• So, it sounds like what you want is a machine learning algorithm that works on trees, in the supervised learning context. I'd imagine there are probably many possible algorithms you could try. To start out.. have you tried using naive Bayes? (The feature set might be each possible subtree that appears anywhere in your training set.) – D.W. Jul 6 '14 at 22:59

It sounds like what you want is a machine learning algorithm that works on trees, in the supervised learning context. I'd imagine there are probably many machine learning algorithms that could be adapted to this setting, but a natural one to try first is naive Bayes. So, let me sketch how to use naive Bayes in this setting.

First, we need a feature set. A simple feature set would be: each possible subtree that appears anywhere in the training set is a feature. So, in the example in the question, your feature set would include the subtree (NP (JJ new) (NN year)) and (JJ new) and every subtree of every parse tree that appears in the training set. Let $S_1,\dots,S_n$ denote these $n$ subtrees. This gives you a bunch of features. Now you can label each sentence with its label (positive or negative); and for each, you know whether it contains that feature or not.

Now remember how Naive bayes works. We have a boolean random variable $Y$ that indicates the class of an item, and $n$ boolean random variables $X_1,\dots,X_n$ that indicate which features it has. In particular, $X_i=+$ means that the $i$th feature is positive, i.e., that the $i$th subtree $S_i$ is a subtree of the current item. We want to calculate

$$\Pr[Y=+ | X_1=x_1,\dots,X_n=x_n].$$

We do this using Bayes theorem. In particular, we use our training set to calculate

$$\Pr[X_i=x_i | Y=y],$$

for each of the 4 possibilities of $x_i,y$. Then, we use Bayes theorem to compute $\Pr[Y=+ | X_1=x_1,\dots,X_n=x_n]$.

Now everything works as usual for naive Bayes. We've converted this into a situation where there's a set of $n$ features that can be present or absent for each item, and we want to label all the items; there's no more need to reason about the tree structure, we can just use a standard classifier like naive Bayes. You could also plug in some other classifier as well, too; hopefully you can see how this might work, from here.

• Holy! That is kind of what I need! I'll wait for other interesting answers for one or two days but THANK YOU. Including subtrees as features make sense. However, I have many sentences. I can't manually add all substructures. Is there a quick way to get them out? – windweller Jul 6 '14 at 23:21
• Would you think a string splitting based on parentheses would work? Like peel (ROOT (VP (VBN Happy) (NP (JJ new) (NN year)))) like an onion and use every layer a feature? – windweller Jul 6 '14 at 23:22

You could use the techniques of syntactic pattern recognition. More specifically, you could use the UpWrite predictor, a method for inducting language grammars:

"Introducing the UpWrite Predictor", Jason L. Hutchens. International Colloquium on Grammatical Inference, 1999.