Extracting Opinion Expressions with semi-Markov Conditional Random Fields

From Cohen Courses
Jump to navigationJump to search

Citation

 author    = {Yang, Bishan  and  Cardie, Claire},
 title     = {Extracting Opinion Expressions with semi-Markov Conditional Random Fields},
 booktitle = {Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning},
 month     = {July},
 year      = {2012},
 address   = {Jeju Island, Korea},
 publisher = {Association for Computational Linguistics},
 pages     = {1335--1345},

Online version

ACLWEB 2012

Summary

This paper proposes an opinion expression extraction algorithm. It uses a segment level sequence labeling technique using semi-CRFs. The main focus of the paper is to identify two types of opinion expressions in the corpus. First, direct subjective expressions. Secondly, direct expressive subjective expressions. For Exmaple :

  1. "The International Committee of the Red Cross, [as usual ,[has refused to make any statements".
  2. "The Chief Minister [said that [the demon they have reared will eat up their own vitals".

Dataset

The algorithm is evaluated on Multi Perspective Question Answering (MPQA) dataset. The dataset contains 535 news articles and 11,114 sentences with 55.89% sentences with DSEs and 57.93% with ESEs. 135 documents are used for training and 400 are used for testing.

Background

The previous work of sequence tagging in natural language processing has been limited to word level. This paper extends it to phrase level. Sarawagi and Cohen, 2004 has shown that semi-CRFs outperform CRFs in Named Entity Recognition. So the authors try a new extended semi-CRF model to opinion expression extraction task and measure it's performance with semi-CRF and CRFs for the same task.

Methodology

Semi-CRF

A sentence s is divided into segments . Where = such that is the start position of segment , is the end position and is the label of the segment. Segment length is limited to maximum length seen in the corpus.

Feature function g(x,s,i) is short representation of . The conditional probability of a segmentation s give a sequence x is defined as .

The correct segmentation s of a sentence is defined as a sequence of entity segments(DSE or ESE) and non-entity segments (they are unit length segments that are to be ignored).

Extended Semi-CRF for Opinion Expression Extraction

none
Fig.1 Sentence parse tree
none
Fig.2 Segment Construction Algorithm

The objective is to learn the entity boundaries and labels for opinion expression extraction.

  • First modification, the segment length should not be fixed to maximum segment length based on observed entities, it should be unbounded to allow any length segment candidates.
  • Second,the segment units are generated from sentence parse tree,Fig.1.

Segment candidates are constructed using the segment construction algorithm Fig.2. Function returns true if parent node of have the same rightmost child in their subtrees, otherwise it returns false.

The above generated candidate segments are then validated as follows.

  • For opinion expressions that do not match any segment candidate, break them down into smaller segment using a greedy match process.
    • Starting from start position of the expression, search for the longest candidate that is contained in expression, add it to the correct segmentation for the sentence.
    • Move the start position to the next position and repeat previous.

The segment training data generated from previous step is then used in training semi-CRF model. The authors have used BFGS algorithm,Liu and Nocedal, 1989,for optimizing gradient of log-likelihood L.

where, S is all possible segmentation consisting of generated segment candidates. is probability of having label y for the current segment ( with boundary and is label for previous segment .

Forward-Backward algorithm is used to compute marginal distribution and normalization factor Z(x). For inference best segmentation is arg p(s|x). An efficient inference is implemented by extending Viterbi algorithm to segments.

Features

There are two set of features. First, CRF-style features, string representation of word, its part-of-speech and strong or weak subjectivity feature derived from subjectivity lexicon provided by Wilson et al. 2005. Breck et al.2007 have used similar definition in their work.

Secondly, following segment-level syntactic features are used to capture syntactic patterns of opinion expressions. Since most of the opinion expression involved verb phrases(VP),therefore following features are used to capture VP-related constituents.

  • VPRoot: A VP constituent whose parent node is not VP.
  • VPLeaf: A VP constituent whose children nodes are non-VP.
    • VPcluster: Indicates whether or not segment matches verb-cluster strucutre.
    • VPpred: A feature of the syntactic category and the word of the head of VPLeaf. The head of VPLeaf is the predicate of the verb phrase, which may encode some intention of opinions in the verb phrase.
    • VParg: A feature syntactic category and the head word of the argument in VPLeaf.
    • VPsubj:Whether the verb clusters or the argument in the segment contains an entry from the subjectivity lexicon.

Experimental Results

Evaluation Metrics

  • Binary Overlap : Predicted expression is correct if it overlaps with a correct expression.
  • Proportional Overlap : Only the overlapping proportion of predicted expression over correct expression is consider to be correct.

Baseline Methods

  • Token-level CRF approach, Breck et al.2007, is used as the baseline on MPQA dataset.
  • Two variation of standard CRF are used. First, segment-CRF, treats segment units obtained from parser as work tokens. Second, Syntactic-CRF, encodes segment-level syntactic information in a standard token-level CRF as input features.
  • Semi-CRF model ,Sarawagi and Cohen, 2004, is also used as baseline.

Results

  • The extended semi-CRF is labeled as new-semi-CRF.

Semi-CRF Results.png Semi-CRF Results 2.png

  • Comparison with previous work.

Semi-CRF Results 3.png

Discussion

The extended semi-CRF approach outperforms original semi-CRF,Sarawagi and Cohen, 2004. But as compared to CRF it has lower precision and high recall. This is because the current approach predicted nearly twice the number of DSEs as compared to CRF and this lead to high recall and low precision. Overall the F-measure is boosted as compared to CRF.

The authors propose to add new features and better way to model context surrounding to improve performance. One should note that the semi-CRFs take longer time to train and validate then CRFs. The proposed approach took 2.25 hours for training 11,114 sentences. 2 hours for parsing sentences using Stanford Parser and 15 minutes training on a 4GB RAM, Intel Core 2 Duo CPU.

Study Plan