Difference between revisions of "Kessler et al. 2009"

From Cohen Courses
Jump to navigationJump to search
(Created page with '== Citation == Jason S. Kessler and Nicolas Nicolov. 2009. Targeting Sentiment Expressions through Supervised Ranking of Linguistic Configurations. In Proceedings of the Associ…')
 
 
(3 intermediate revisions by the same user not shown)
Line 11: Line 11:
 
== Summary ==
 
== Summary ==
  
−
This paper follows many other sentiment analysis papers in analyzing graphs of words with synonym and antonym links to estimate the net sentiment of each word. Their estimation model, however, is a clear departure from most other work in NLP.
+
This paper examines four different methods of attaching sentimental-containing phrases (sentiment expressions) with the nouns they describe (mentions). They assume a separate module is able to accurately identify both sentiment expressions and mentions, and seek only to determine which sentiment expressions modify which mentions.
  
−
The fundamental idea of the paper is that sentiment of words occurring near each other (according to search engine hit counts) are likely to have similar sentiment values. They observe that this phenomenon is similar to the problem of determining the mostly likely spin states of each electron in a field of electrons.
+
Furthermore, their algorithms build a graph-like structure linking the speaker or holder of the opinion with the sentiment expression, the sentiment expression with the mention, and meronyms of mentions with their parents. This allows for efficient extraction of results beyond just the single sentiment value of one mention. Instead, queries such as "What do people not like about product X?" or "What other features do users who
 +
dislike the camera’s zoom lens feel strongly about?" may be answered by their data representation.
  
−
As they describe it, on a local scale electrons near each other tend to have the same spin. To have two electrons near each other with differing spins requires some amount of energy, and as such, the goal of the optimization problem is to find the state of the electron field with the lowest possible energy. Fortunately, computational physicists have studied this [[UsesMethod::spin model]] thoroughly. While exhaustive computation requires exponential time, they have also found tractable approximations.
+
Their data set consisted was constructed by them, and while their resulting precisions were lower than some other papers, their blog-based data set poses its own difficulties. Their methods did, however result in higher precision than other papers's methods on Kessler et Al.'s custom dataset.
  
 
== Brief description of the method ==
 
== Brief description of the method ==
−
The method asserts that the 'energy' of an electron system <math>x</math> of <math>N</math> electrons is given by
+
This paper explores four methods for linking mentions and sentiment expressions.
  
−
<math>
+
The first is a simple baseline. We assume sentiment expressions and mentions are both already tagged. From there, we simply associate each sentiment expression with the mention closest to it. Should there be a tie, the one to the right is chosen.
−
E(x, w)=-\frac{1}{2}\sum_{i j}w_{i j} x_i x_j
 
−
</math>
 
  
−
where <math>x_i</math> is the spin (+1 or -1) of the <math>i</math>th electron and <math>w</math> is an <math>NxN</math> matrix representing the weights between each pair of electrons.
+
The second system is called the Heuristic Syntax system. They leverage a dependency parse tree wherein they collapse all mentions and sentiment expressions to one node in the parse. Then, if a sentiment expression governs or is governed by a mention, they are associated.
  
−
The probability of an electron configuration is given by
+
The third system is based on work by Bloom, Garg, and Argamon, and is simply referred to as 'Bloom'. Again, this method leverages a dependency parse, as well as 42 hand-crafted rules produced by the aforementioned three authors. Each rule is a sequence of relational arcs in the dependency parse that is designed to lead from a sentiment expression to a mention. The rules are ordered such that the first rule of the list to match is supposed to be the best one.
  
−
<math>
+
Finally, the new work done by this paper is an approach called the RankSVM. The idea is to learn a model that for each sentiment expression will rank mentions in the same sentence according to their likelihood of being the target of the expression.
−
P(x|W) = \frac{1}{Z(W)} exp(-\Beta E(x, W))
 
−
</math>
 
  
−
where <math>Z(W)</math> is the normalization factor and <math>\Beta</math> is a hyper-parameter called the <i>inverse-temperature</i>.
+
The authors use the SVMLight implementation with default parameters to create their SVM. They repeatedly point out that one large benefit to their system is that it can assign the same score to multiple instances, thus allowing one sentiment expression to connect to multiple mentions. This is particularly useful in the presence of coordinating conjunctions.
  
−
Unfortunately, evaluating <math>Z(W)</math> is intractable, due to the fact that there are <math>2^N</math> possible configurations of electrons. As such Takamura et al. use a clever approximation. They seek a function <math>Q(\theta,W)</math> that is as similar to <math>P(x|W)</math> as possible. As a distance metric between the two functions they use the <i>variational free energy</i> <math>F(\theta)</math> which is defined as the difference between the mean energy with respect to <math>Q</math> and the entropy of <math>Q</math>.
+
== Experimental Result ==
−
 
+
On their own data set they showed an overall F-score of 69.8% with their best model, the RankSVM. The other methods scored from 44.5% with the Bloom method, up to 58.9% with the proximity-based model. The heuristic syntax model scored in between at 57.4%.
−
This function's derivative is analytically findable, and hence given a starting value of <math>x</math> an analytic update rule can be found, and is shown in the paper.
 
−
 
 
−
They then require a way to compute the weighting table <math>W</math>. They do this by using their glossary of similar terms and defining <math>W_{i j} = \frac{1}{\sqrt{d(i) d(j)}}</math> where <math>d(i)</math> represents the degree of word <math>i</math>.
 
−
 
 
−
Finally, they discuss two methodologies for determining the hyper-parameter <math>\Beta</math>. The first is a simple leave-one-out error rate minimization method, as is standard in many machine learning problems. The second is physics-inspired and is called the <i>magnetism</i> of the system, defined by
 
  
−
<math>
+
Interestingly, their baseline proximity-based model actually out performed both the Bloom and Heuristic Syntax. Their RankSVM model had very high precision, with 74.8%, but relatively low recall at just 65.4%.
−
m = \frac{1}{N}\sum_i \bar{x_i}
 
−
</math>
 
  
−
They seek a value of <math>\Beta</math> that makes <math>m</math> positive, but as close as possible to zero. To accomplish this, they simply calculate <math>m</math> with several different values of <math>\Beta</math> and select the best one they find.
 
−
 
−
== Experimental Result ==
 
−
The approach described achieved accuracies from 75.2% using two seed words to 91.5% using leave-one-out cross validation. They compare their results to two previous methods for accomplishing the same task on a separate lexical graph constructed using only synonym connections. The first is the graph-based shortest-distance algorithm of Hu and Liu, which achieved a 70.8% accuracy, while Takamura et Al.'s approach achieved 73.4%. The second was Riloff et al.'s bootstrapping method which achieved 72.8%, compared to Takamura et al.'s 83.6% on that data set.
 
 
== Related papers ==
 
== Related papers ==

Latest revision as of 02:30, 2 October 2012

Citation

Jason S. Kessler and Nicolas Nicolov. 2009. Targeting Sentiment Expressions through Supervised Ranking of Linguistic Configurations. In Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI '09).

Online version

Indiana CS

Summary

This paper examines four different methods of attaching sentimental-containing phrases (sentiment expressions) with the nouns they describe (mentions). They assume a separate module is able to accurately identify both sentiment expressions and mentions, and seek only to determine which sentiment expressions modify which mentions.

Furthermore, their algorithms build a graph-like structure linking the speaker or holder of the opinion with the sentiment expression, the sentiment expression with the mention, and meronyms of mentions with their parents. This allows for efficient extraction of results beyond just the single sentiment value of one mention. Instead, queries such as "What do people not like about product X?" or "What other features do users who dislike the camera’s zoom lens feel strongly about?" may be answered by their data representation.

Their data set consisted was constructed by them, and while their resulting precisions were lower than some other papers, their blog-based data set poses its own difficulties. Their methods did, however result in higher precision than other papers's methods on Kessler et Al.'s custom dataset.

Brief description of the method

This paper explores four methods for linking mentions and sentiment expressions.

The first is a simple baseline. We assume sentiment expressions and mentions are both already tagged. From there, we simply associate each sentiment expression with the mention closest to it. Should there be a tie, the one to the right is chosen.

The second system is called the Heuristic Syntax system. They leverage a dependency parse tree wherein they collapse all mentions and sentiment expressions to one node in the parse. Then, if a sentiment expression governs or is governed by a mention, they are associated.

The third system is based on work by Bloom, Garg, and Argamon, and is simply referred to as 'Bloom'. Again, this method leverages a dependency parse, as well as 42 hand-crafted rules produced by the aforementioned three authors. Each rule is a sequence of relational arcs in the dependency parse that is designed to lead from a sentiment expression to a mention. The rules are ordered such that the first rule of the list to match is supposed to be the best one.

Finally, the new work done by this paper is an approach called the RankSVM. The idea is to learn a model that for each sentiment expression will rank mentions in the same sentence according to their likelihood of being the target of the expression.

The authors use the SVMLight implementation with default parameters to create their SVM. They repeatedly point out that one large benefit to their system is that it can assign the same score to multiple instances, thus allowing one sentiment expression to connect to multiple mentions. This is particularly useful in the presence of coordinating conjunctions.

Experimental Result

On their own data set they showed an overall F-score of 69.8% with their best model, the RankSVM. The other methods scored from 44.5% with the Bloom method, up to 58.9% with the proximity-based model. The heuristic syntax model scored in between at 57.4%.

Interestingly, their baseline proximity-based model actually out performed both the Bloom and Heuristic Syntax. Their RankSVM model had very high precision, with 74.8%, but relatively low recall at just 65.4%.

Related papers

Retrieved from "http://curtis.ml.cmu.edu/w/courses/index.php?title=Kessler_et_al._2009&oldid=13377"