research-article

Free access

BestCut: a graph algorithm for coreference resolution

Authors:

Cristina Nicolae,

Gabriel NicolaeAuthors Info & Claims

EMNLP '06: Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing

Pages 275 - 283

Published: 22 July 2006 Publication History

Abstract

In this paper we describe a coreference resolution method that employs a classification and a clusterization phase. In a novel way, the clusterization is produced as a graph cutting algorithm, in which nodes of the graph correspond to the mentions of the text, whereas the edges of the graph constitute the confidences derived from the coreference classification. In experiments, the graph cutting algorithm for coreference resolution, called BestCut, achieves state-of-the-art performance.

References

[1]

B. Baldwin, T. Morton, A. Bagga, J. Baldridge, R. Chandraseker, A. Dimitriadis, K. Snyder, and M. Wolska. 1998. Description of the university of pennsylvania camp system as used for coreference. In Proceedings of the 7th Message Understanding Conference (MUC-7).

[2]

A. L. Berger, S. A. D. Pietra, and V. J. D. Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 1(22):39--71.

Digital Library

[3]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2001. Introduction to Algorithms, Second Edition. MIT.

Digital Library

[4]

C. Cortes and V. Vapnik. 1995. Support-vector networks. Machine Learning, 20(3):273--297.

Digital Library

[5]

H. DaumeIII and D. Marcu. 2005a. A large-scale exploration of effective global features for a joint entity detection and tracking model. pages 97--104, Vancouver.

[6]

H. DaumeIII and D. Marcu. 2005b. Learning as search optimization: Approximate large margin methods for structured prediction. In The International Conference on Machine Learning (ICML).

Digital Library

[7]

C. Fellbaum, editor. 1998. WordNet: An Electronic Lexical Database and Some of its Applications. MIT Press.

[8]

X. Luo, A. Ittycheriah, H. Jing, N. Kambhatla, and S. Roukos. 2004. A mention-synchronous coreference resolution algorithm based on the bell tree. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics, Barcelona, Spain.

Digital Library

[9]

R. Mihalcea and A. Csomai. 2005. Senselearner: Word sense disambiguation for all words in unrestricted text. In Proceedings of the 43rd Meeting of the Association for Computational Linguistics, Ann Arbor, MI.

Digital Library

[10]

MUC-6. 1995. Coreference task definition.

[11]

V. Ng and C. Cardie. 2002. Improving machine learning approaches to coreference resolution. In Proceedings of the 4Oth Meeting of the Association for Computational Linguistics, Philadelphia, Pennsylvania.

Digital Library

[12]

V. Ng. 2004. Learning noun phrase anaphoricity to improve conference resolution: Issues in representation and optimization. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics, Barcelona, Spain.

Digital Library

[13]

V. Ng. 2005. Machine learning for coreference resolution: From local classification to global ranking. In Proceedings of the 43rd Meeting of the Association for Computational Linguistics, pages 157--164, Ann Arbor, MI.

Digital Library

[14]

NIST. 2003. Entity detection and tracking - phase 1; edt and metonymy annotation guidelines. version 2.5.1 20030502.

[15]

M. Pasca and S. Harabagiu. 2001. High performance question/answering. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 366--374, New Orleans, LA.

Digital Library

[16]

W. M. Soon, H. T. Ng, and D. C. Y. Lim. 2001. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 4(27):521--544.

Digital Library

[17]

M. Stoer and F. Wagner. 1994. A simple min cut algorithm. In Jan van Leeuwen, editor, Proceedings of the 1994 European Symposium on Algorithms, pages 141--147, New York. Springer-Verlag.

Digital Library

[18]

M. Vilain, J. Burger, J. Aberdeen, D. Connolly, and L. Hirschman. 1995. A model-theoretic coreference scoring scheme. In Proceedings of the Sixth Message Understanding Conference (MUC-6), pages 45--52.

Digital Library

Cited By

Le Thi TThanh TThi TThang HHu ZBui MSikdar BIDE IBinh HEngchuan WSang DOanh N(2017)Ontology-Based Entity Coreference Resolution For Sentiment AnalysisProceedings of the 8th International Symposium on Information and Communication Technology10.1145/3155133.3155168(50-56)Online publication date: 7-Dec-2017
https://dl.acm.org/doi/10.1145/3155133.3155168
Pinto DGómez-Adorno HVilariño DSingh V(2014)A graph-based multi-level linguistic representation for document understandingPattern Recognition Letters10.5555/2748148.274852341:C(93-102)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.5555/2748148.2748523
Chen BSu JTan C(2013)Random walks down the mention graphs for event coreference resolutionACM Transactions on Intelligent Systems and Technology (TIST)10.1145/2508037.25080554:4(1-20)Online publication date: 8-Oct-2013
https://dl.acm.org/doi/10.1145/2508037.2508055
Show More Cited By

BestCut: a graph algorithm for coreference resolution
1. Computing methodologies
  1. Artificial intelligence
2. Hardware
  1. Power and energy
    1. Power estimation and optimization

Recommendations

On the Multichromatic Number of s-Stable Kneser Graphs

For positive integers n and s, a subset Sï [n] is s-stable if sï |i-j|ï n-s for distinct i,j∈S . The s-stable r-uniform Kneser hypergraph KGrn,ks-stable is the r-uniform hypergraph that has the collection of all s-stable k-element subsets of [n] as ...
Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes

An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the ...
Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G@?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

EMNLP '06: Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing

July 2006

648 pages

ISBN:1932432736

Program Chairs:
Dan Jurafsky
Stanford University
,
Eric Gaussier
Xerox Research Centre Europe

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 22 July 2006

Qualifiers

Research-article

Acceptance Rates

EMNLP '06 Paper Acceptance Rate 73 of 234 submissions, 31%;

Overall Acceptance Rate 73 of 234 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
594
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)12

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Le Thi TThanh TThi TThang HHu ZBui MSikdar BIDE IBinh HEngchuan WSang DOanh N(2017)Ontology-Based Entity Coreference Resolution For Sentiment AnalysisProceedings of the 8th International Symposium on Information and Communication Technology10.1145/3155133.3155168(50-56)Online publication date: 7-Dec-2017
https://dl.acm.org/doi/10.1145/3155133.3155168
Pinto DGómez-Adorno HVilariño DSingh V(2014)A graph-based multi-level linguistic representation for document understandingPattern Recognition Letters10.5555/2748148.274852341:C(93-102)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.5555/2748148.2748523
Chen BSu JTan C(2013)Random walks down the mention graphs for event coreference resolutionACM Transactions on Intelligent Systems and Technology (TIST)10.1145/2508037.25080554:4(1-20)Online publication date: 8-Oct-2013
https://dl.acm.org/doi/10.1145/2508037.2508055
Sapena EPadró LTurmo JJoshi AHuang CJurafsky D(2010)A global relaxation labeling approach to coreference resolutionProceedings of the 23rd International Conference on Computational Linguistics: Posters10.5555/1944566.1944691(1086-1094)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1944566.1944691
Rao DMcNamee PDredze MJoshi AHuang CJurafsky D(2010)Streaming cross document entity coreference resolutionProceedings of the 23rd International Conference on Computational Linguistics: Posters10.5555/1944566.1944687(1050-1058)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1944566.1944687
Cai JStrube MKatagiri YNakano MFernández RLemon O(2010)Evaluation metrics for end-to-end coreference resolution systemsProceedings of the 11th Annual Meeting of the Special Interest Group on Discourse and Dialogue10.5555/1944506.1944511(28-36)Online publication date: 24-Sep-2010
https://dl.acm.org/doi/10.5555/1944506.1944511
Rahman ANg VJoshi AHuang CJurafsky D(2010)Inducing fine-grained semantic classes via hierarchical and collective classificationProceedings of the 23rd International Conference on Computational Linguistics10.5555/1873781.1873886(931-939)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1873781.1873886
Cai JStrube MJoshi AHuang CJurafsky D(2010)End-to-end coreference resolution via hypergraph partitioningProceedings of the 23rd International Conference on Computational Linguistics10.5555/1873781.1873798(143-151)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1873781.1873798
Reichart RAbend ORappoport ALapata M(2010)Type level clustering evaluationProceedings of the Fourteenth Conference on Computational Natural Language Learning10.5555/1870568.1870579(77-87)Online publication date: 15-Jul-2010
https://dl.acm.org/doi/10.5555/1870568.1870579
Chen ZJi HBanea CMoschitti ASomasundaran SZanzotto F(2010)Graph-based clustering for computational linguisticsProceedings of the 2010 Workshop on Graph-based Methods for Natural Language Processing10.5555/1870490.1870491(1-9)Online publication date: 16-Jul-2010
https://dl.acm.org/doi/10.5555/1870490.1870491
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents