Matrix representations, linear transformations, and kernels for disambiguation in natural language
Tóm tắt
In the application of machine learning methods with natural language inputs, the words and their positions in the input text are some of the most important features. In this article, we introduce a framework based on a word-position matrix representation of text, linear feature transformations of the word-position matrices, and kernel functions constructed from the transformations. We consider two categories of transformations, one based on word similarities and the second on their positions, which can be applied simultaneously in the framework in an elegant way. We show how word and positional similarities obtained by applying previously proposed techniques, such as latent semantic analysis, can be incorporated as transformations in the framework. We also introduce novel ways to determine word and positional similarities. We further present efficient algorithms for computing kernel functions incorporating the transformations on the word-position matrices, and, more importantly, introduce a highly efficient method for prediction. The framework is particularly suitable to natural language disambiguation tasks where the aim is to select for a single word a particular property from a set of candidates based on the context of the word. We demonstrate the applicability of the framework to this type of tasks using context-sensitive spelling error correction on the Reuters News corpus as a model problem.
Tài liệu tham khảo
Bentivogli, L., Forner, P., Magnini, B., & Pianta, E. (2004). Revising wordnet domains hierarchy: Semantics, coverage, and balancing. In G. Sérasset, S. Armstrong, C. Boitet, A. Popescu-Belis, & D. Tufis (Eds.), COLING 2004 workshop on multilingual linguistic resources (pp. 101–108), Geneva, Switzerland.
citation_journal_title=Journal of Machine Learning Research; citation_title=Word-sequence kernels; citation_author=N. Cancedda, E. Gaussier, C. Goutte, J.-M. Renders; citation_volume=3; citation_publication_date=2003; citation_pages=1059-1082; citation_doi=10.1162/153244303322533197; citation_id=CR2
citation_title=Introduction to the conll-2004 shared task: semantic role labeling; citation_inbook_title=Proceedings of CoNLL-2004; citation_publication_date=2004; citation_pages=89-97; citation_id=CR3; citation_author=X. Carreras; citation_author=L. Màrques; citation_publisher=Association for Computational Linguistics
citation_title=Introduction to the CoNLL-2005 shared task: semantic role labeling; citation_inbook_title=Proceedings of the ninth conference on computational natural language learning (CoNLL-2005); citation_publication_date=2005; citation_pages=152-164; citation_id=CR4; citation_author=X. Carreras; citation_author=L. Màrquez; citation_publisher=Association for Computational Linguistics
Collins, M., & Duffy, N. (2001). Convolution kernels for natural language.
citation_title=Auc optimization vs. error rate minimization; citation_inbook_title=Advances in neural information processing systems 16; citation_publication_date=2004; citation_id=CR6; citation_author=C. Cortes; citation_author=M. Mohri; citation_publisher=MIT Press
citation_journal_title=Journal of Intelligent Information Systems; citation_title=Latent semantic kernels; citation_author=N. Cristianini, J. Shawe-Taylor, H. Lodhi; citation_volume=18; citation_issue=2–3; citation_publication_date=2002; citation_pages=127-152; citation_doi=10.1023/A:1013625426931; citation_id=CR7
Cumby, C. M., & Roth, D. (2002). Learning with feature description logics. In Proceedings of the 12th international conference on inductive logic programming.
Cumby, C. M., & Roth, D. (2003a). Feature extraction languages for propositionalized relational learning. In Proceedings of the IJCAI’03 workshop on learning statistical models from relational data.
citation_title=On kernel methods for relational learning; citation_inbook_title=Proceedings of the twentieth international conference on machine learning; citation_publication_date=2003; citation_pages=107-114; citation_id=CR10; citation_author=C. M. Cumby; citation_author=D. Roth; citation_publisher=AAAI Press
citation_journal_title=Journal of the American Society of Information Science; citation_title=Indexing by latent semantic analysis; citation_author=S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, R. A. Harshman; citation_volume=41; citation_issue=6; citation_publication_date=1990; citation_pages=391-407; citation_doi=10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9; citation_id=CR11
Fawcett, T. (2003). Roc graphs: notes and practical considerations for data mining researchers (Technical Report HPL-2003-4). HP Labs, Palo Alto, CA.
Gärtner, T., Flach, P. A., & Wrobel, S. (2003). On graph kernels: hardness results and efficient alternatives. In COLT (pp. 129–143).
citation_journal_title=Machine Learning; citation_title=Kernels and distances for structured data; citation_author=T. Gärtner, J. W. Lloyd, P. A. Flach; citation_volume=57; citation_issue=3; citation_publication_date=2004; citation_pages=205-232; citation_doi=10.1023/B:MACH.0000039777.23772.30; citation_id=CR14
citation_journal_title=Journal of Machine Learning Research; citation_title=New techniques for disambiguation in natural language and their application to biological text; citation_author=F. Ginter, J. Boberg, J. Järvinen, T. Salakoski; citation_volume=5; citation_publication_date=2004; citation_pages=605-621; citation_id=CR15
citation_title=Domain kernels for word sense disambiguation; citation_inbook_title=Proceedings of the 43rd annual meeting of the association for computational linguistics (ACL’05); citation_publication_date=2005; citation_pages=403-410; citation_id=CR16; citation_author=A. Gliozzo; citation_author=C. Giuliano; citation_author=C. Strapparava; citation_publisher=Association for Computational Linguistics
citation_journal_title=Machine Learning; citation_title=A winnow-based approach to context-sensitive spelling correction; citation_author=A. R. Golding, D. Roth; citation_volume=34; citation_publication_date=1999; citation_pages=107-130; citation_doi=10.1023/A:1007545901558; citation_id=CR17
Haussler, D. (1999). Convolution kernels on discrete structures (Technical Report UCS-CRL-99-10). University of California at Santa Cruz.
citation_title=Text categorization with support vector machines: learning with many relevant features; citation_inbook_title=Proceedings of the tenth European conference on machine learning; citation_publication_date=1998; citation_pages=137-142; citation_id=CR19; citation_author=T. Joachims; citation_publisher=Springer
citation_title=Learning to classify text using support vector machines: methods, theory and algorithms; citation_publication_date=2002; citation_id=CR20; citation_author=T. Joachims; citation_publisher=Kluwer Academic
citation_title=Speech and language processing: an introduction to natural language processing, computational linguistics, and speech recognition; citation_publication_date=2000; citation_id=CR21; citation_author=D. Jurafsky; citation_author=J. H. Martin; citation_publisher=Prentice Hall PTR
citation_title=Learning semantic similarity; citation_inbook_title=Advances in neural information processing systems 15; citation_publication_date=2003; citation_pages=657-664; citation_id=CR22; citation_author=J. Kandola; citation_author=J. Shawe-Taylor; citation_author=N. Cristianini; citation_publisher=MIT Press
citation_journal_title=Machine Learning; citation_title=Text categorization with support vector machines. How to represent texts in input space?; citation_author=E. Leopold, J. Kindermann; citation_volume=46; citation_issue=1–3; citation_publication_date=2002; citation_pages=423-444; citation_doi=10.1023/A:1012491419635; citation_id=CR23
citation_title=Auc: a statistically consistent and more discriminating measure than accuracy; citation_inbook_title=Proceedings of the eighteenth international joint conference on artificial intelligence; citation_publication_date=2003; citation_pages=519-526; citation_id=CR24; citation_author=C. X. Ling; citation_author=J. Huang; citation_author=H. Zhang; citation_publisher=Morgan Kaufmann
citation_journal_title=Journal of Machine Learning Research; citation_title=Text classification using string kernels; citation_author=H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, C. Watkins; citation_volume=2; citation_publication_date=2002; citation_pages=419-444; citation_doi=10.1162/153244302760200687; citation_id=CR25
citation_title=Integrating subject field codes into WordNet; citation_inbook_title=Second international conference on language resources and evaluation (LREC-2000); citation_publication_date=2000; citation_pages=1413-1418; citation_id=CR26; citation_author=B. Magnini; citation_author=G. Cavaglià; citation_publisher=European Language Resources Association
citation_title=Linear structures; citation_publication_date=1988; citation_id=CR27; citation_author=J. R. Magnus; citation_publisher=Griffin
citation_title=Matrix analysis and applied linear algebra; citation_publication_date=2000; citation_id=CR28; citation_author=C. D. Meyer; citation_publisher=Society for Industrial and Applied Mathematics
citation_journal_title=BMC Bioinformatics; citation_title=Contextual weighting for support vector machines in literature mining: an application to gene versus protein name disambiguation; citation_author=T. Pahikkala, F. Ginter, J. Boberg, J. Järvinen, T. Salakoski; citation_volume=6; citation_issue=1; citation_publication_date=2005; citation_pages=157; citation_doi=10.1186/1471-2105-6-157; citation_id=CR29
citation_title=Improving the performance of Bayesian and support vector classifiers in word sense disambiguation using positional information; citation_inbook_title=Proceedings of the international and interdisciplinary conference on adaptive knowledge representation and reasoning; citation_publication_date=2005; citation_pages=90-97; citation_id=CR30; citation_author=T. Pahikkala; citation_author=S. Pyysalo; citation_author=J. Boberg; citation_author=A. Mylläri; citation_author=T. Salakoski; citation_publisher=Helsinki University of Technology
citation_title=Kernels incorporating word positional information in natural language disambiguation tasks; citation_inbook_title=Proceedings of the eighteenth international Florida artificial intelligence research society conference; citation_publication_date=2005; citation_pages=442-447; citation_id=CR31; citation_author=T. Pahikkala; citation_author=S. Pyysalo; citation_author=F. Ginter; citation_author=J. Boberg; citation_author=J. Järvinen; citation_author=T. Salakoski; citation_publisher=AAAI Press
citation_title=Incorporating external information in Bayesian classifiers via linear feature transformations; citation_inbook_title=Proceedings of the 5th international conference on NLP (FinTAL 2006); citation_publication_date=2006; citation_pages=399-410; citation_id=CR32; citation_author=T. Pahikkala; citation_author=J. Boberg; citation_author=A. Mylläri; citation_author=T. Salakoski; citation_publisher=Springer
citation_title=Fast n-fold cross-validation for regularized least-squares; citation_inbook_title=Proceedings of the ninth Scandinavian conference on artificial intelligence (SCAI 2006); citation_publication_date=2006; citation_pages=83-90; citation_id=CR33; citation_author=T. Pahikkala; citation_author=J. Boberg; citation_author=T. Salakoski; citation_publisher=Otamedia Oy
citation_title=The case against accuracy estimation for comparing induction algorithms; citation_inbook_title=ICML ’98: proceedings of the fifteenth international conference on machine learning; citation_publication_date=1998; citation_pages=445-453; citation_id=CR34; citation_author=F. J. Provost; citation_author=T. Fawcett; citation_author=R. Kohavi; citation_publisher=Morgan Kaufmann
Rifkin, R. (2002). Everything old is new again: a fresh look at historical approaches in machine learning. PhD thesis, MIT.
citation_title=Regularized least-squares classification; citation_inbook_title=Advances in learning theory: methods, model and applications; citation_publication_date=2003; citation_pages=131-154; citation_id=CR36; citation_author=R. Rifkin; citation_author=G. Yeo; citation_author=T. Poggio; citation_publisher=IOS Press
citation_title=The Reuters corpus volume 1: from yesterday’s news to tomorrow’s language resources; citation_inbook_title=Proceedings of the third international conference on language resources and evaluation; citation_publication_date=2002; citation_id=CR37; citation_author=T. G. Rose; citation_author=M. Stevenson; citation_author=M. Whitehead; citation_publisher=ELRA
citation_title=Learning with kernels; citation_publication_date=2002; citation_id=CR38; citation_author=B. Schölkopf; citation_author=A. J. Smola; citation_publisher=MIT Press
citation_title=Prior knowledge in support vector kernels; citation_inbook_title=Advances in neural information processing systems 10; citation_publication_date=1998; citation_pages=640-646; citation_id=CR39; citation_author=B. Schölkopf; citation_author=P. Simard; citation_author=A. Smola; citation_author=V. Vapnik; citation_publisher=MIT Press
citation_title=Kernel methods for pattern analysis; citation_publication_date=2004; citation_id=CR40; citation_author=J. Shawe-Taylor; citation_author=N. Cristianini; citation_publisher=Cambridge University Press
citation_title=Density estimation for statistics and data analysis; citation_publication_date=1986; citation_id=CR41; citation_author=B. W. Silverman; citation_publisher=Chapman & Hall
citation_title=Support vector machines based on a semantic kernel for text categorization; citation_inbook_title=Proceedings of the IEEE-Inns-Enns international joint conference on neural networks; citation_publication_date=2000; citation_pages=205-209; citation_id=CR42; citation_author=G. Siolas; citation_author=F. d’Alché-Buc; citation_publisher=IEEE Computer Society
Suzuki, J., Hirao, T., Sasaki, Y., & Maeda, E. (2003). Hierarchical directed acyclic graph kernel: methods for structured natural language data.
citation_title=Introduction to the conll-2003 shared task: language-independent named entity recognition; citation_inbook_title=Proceedings of CoNLL-2003; citation_publication_date=2003; citation_pages=142-147; citation_id=CR44; citation_author=K. S. E. F. Tjong; citation_author=F. Meulder; citation_publisher=Association for Computational Linguistics
Tsivtsivadze, E., Pahikkala, T., Boberg, J., & Salakoski, T. (2006). Locality-convolution kernel and its application to dependency parse ranking. In The 19th international conference on industrial, engineering & other applications of applied intelligent systems. Forthcoming.
citation_title=Statistical learning theory; citation_publication_date=1998; citation_id=CR46; citation_author=V. Vapnik; citation_publisher=Wiley
Vishwanathan, S., Smola, A. J., & Vidal, R. (2006, to appear). Binet-Cauchy kernels on dynamical systems and its application to the analysis of dynamic scenes. International Journal of Computer Vision.
citation_journal_title=Biometrics; citation_title=Individual comparisons by ranking methods; citation_author=F. Wilcoxon; citation_volume=1; citation_publication_date=1945; citation_pages=80-83; citation_doi=10.2307/3001968; citation_id=CR48
Wong, S. K. M., Ziarko, W., & Wong, P. C. N. (1985). Generalized vector space model in information retrieval. In ACM SIGIR international conference on research and development in information retrieval (pp. 18–25).
Yarowsky, D. (1993). One sense per collocation. In Proceedings, ARPA human language technology workshop, Princeton.
Yarowsky, D. (1995). Unsupervised word sense disambiguation rivaling supervised methods. In Meeting of the association for computational linguistics (pp. 189–196).