nobuyukishimizuの日記

2006-07-27 HLT, COLT, ICML, Coling-ACL, EMNLP

HLT, COLT, ICML, Coling-ACL, EMNLPで、機械学習の視点から見て大事そうだな、と思った論文について書きます。 自然言語処理の分野で使えそうな structure のある話にバイアスがかかっているので悪しからず。 他にも良い論文はいっぱいありました。

=======

undirected graphical modelについては、近似を使って undirected graphical model を速く学習する方法についての論文が大事そうでした。 


Quadratic Programming Relaxations for Metric Labeling and Markov Random Field MAP Estimation

http://www.icml2006.org/icml_documents/camera-ready/093_Quadratic_Programmin.pdf


Efficient MAP approximation for dense energy functions

http://www.icml2006.org/icml_documents/camera-ready/069_Efficient_MAP_Approx.pdf

=======

structure がある物体についてのクラスタリングや、unsupervised/semi-supervised learningについての論文も大事そうでした。

Clustering Graphs by Weighted Substructure Mining

http://www.icml2006.org/icml_documents/camera-ready/120_Clustering_Graphs_by.pdf


Discriminative Unsupervised Learning of Structured Predictors

http://www.icml2006.org/icml_documents/camera-ready/133_Discriminative_Unsup.pdf


Semi-Supervised Learning for Structured Output Variables

http://www.icml2006.org/icml_documents/camera-ready/019_Semi_Supervised_Lear.pdf


=======

classification & similarity

一応、分類問題なんですが、feature space にある similarityのコンセプトを使っている所が面白いと思いました。 semi-supervised や、constraint clusteringも出てきていますし、少しづつ、クラスタリングと分類の境界が薄れてきている感じがします。 

On a Theory of Kernels as Similarity Functions

http://www.icml2006.org/icml_documents/camera-ready/010_On_a_Theory_of_Learn.pdf


Local Fisher Discriminant Analysis for Supervised Dimensionality Reduction

http://www.icml2006.org/icml_documents/camera-ready/114_Local_Fisher_Discrim.pdf


=======

sequential labeling に特化した論文

少ないデータで学習する系統

Prototypeを使った Unsupervised Learning。 

Prototype-Driven Learning for Sequence Models

http://www.cs.berkeley.edu/~aria42/pubs/naacl06-posinduction.pdf


Semi-Supervised Conditional Random Fields for Improved Sequence Segmentation and Labeling

http://www.cs.ualberta.ca/~fjiao/acl2006.pdf



Semi-Markov を速くする系統

Improving the Scalability of Semi-Markov Conditional Random Fields for Named Entity Recognition

http://www-tsujii.is.s.u-tokyo.ac.jp/~hillbig/papers/acl2006_semicrf.pdf


Efficient inference on sequence segmentation models

http://www.icml2006.org/icml_documents/camera-ready/100_Efficient_Inference.pdf



F-measureが大事

Training Conditional Random Fields with Multivariate Evaluation Measures

http://acl.ldc.upenn.edu/P/P06/P06-1028.pdf


NER Systems that Suit Users Preferences: Adjusting the

Recall-Precision Trade-off for Entity Extraction

http://www.cs.cmu.edu/~wcohen/postscript/hlt2006.pdf



その他

Segment-based Hidden Markov Models for Information Extraction

http://acl.ldc.upenn.edu/P/P06/P06-1061.pdf


An Effective Two-Stage Model for Exploiting Non-Local Dependencies in Named Entity Recognition

http://acl.ldc.upenn.edu/P/P06/P06-1141.pdf


=======

Decoding

Strucuted Output Predictionの、Decodingを直して欲しい情報を取り出すための論文です。

Integer Linear Programming 系統

Viterbiのかわりに ILPを使って、もっとグローバルなConstraintsを入れてもDecoding出来るようにしよう、というやりかたなんですが、今年は結構多いです。


2005年の論文

Integer Linear Programming Inference for Conditional Random Fields

http://l2r.cs.uiuc.edu/~danr/Papers/RothYi05.pdf


ここから2006年の論文で、係受け解析に使う話。

Incremental Integer Linear Programming for Non-projective Dependency Parsing

http://sebrie.freehostia.com/cms/publications/emnlp06-riedel-clarke.fix.pdf


機械翻訳で必要になる、Word Alignmentの方に持ってくる話。

Word Alignment via Quadratic Assignment

http://www.cs.berkeley.edu/~taskar/pubs/naacl06_qap.pdf


ILPよりも、Finite State Machineを使って、もっと速くやろうという話。

A fast finite-state relaxation method for enforcing global constraints on sequence decoding

http://nlp.cs.jhu.edu/~royt/hlt-naacl-2006.pdf


ILPとfinite-state系統以外のdecodingを含めた学習方は Hal Daume III の A* を使ったものや、searnがあります。 賢く検索できるように学習すれば、速くできる。 したがって、ややこしい search space でも探せるという感じでしょうか。


少し毛色を変えて、sequenceの途中でもdecodeする話。

Online Decoding of Markov Models with Latency Constraints

http://www.icml2006.org/icml_documents/camera-ready/083_Online_Decoding_of_M.pdf


=======

その他、ICMLで少し変わっていて面白いと思った論文

Algorithms for Portfolio Management based on the Newton Method

http://www.icml2006.org/icml_documents/camera-ready/002_Algorithms_for_Portf.pdf


The Relationship Between Precision-Recall and ROC Curves

http://www.icml2006.org/icml_documents/camera-ready/030_The_Relationship_Bet.pdf


Nightmare at test time: Robust learning by feature deletion

http://www.icml2006.org/icml_documents/camera-ready/045_Nightmare_at_Test_Ti.pdf


Maximum Margin Planning

http://www.ri.cmu.edu/pubs/pub_5405.html


=======

つぎは、convexity vs non-convexityについて。

学習する際に、convexityは必要ない、と主張している論文があります。 プレゼンテーションで、hinge loss では、decision boudaryのそばにあるsampleだけでなく、すごく遠くの方にあるoutlayerみたいなsampleもsupport vector になってしまう。それだと逆に accuracy が落ちてしまうから、convexityは忘れて、global minima より、accuracyが高くなるlocal minimaに行くべきだ、と言っていました。

Trading Convexity for Scalability

http://www.icml2006.org/icml_documents/camera-ready/026_Trading_Convexity_fo.pdf


また、Predictive Uncertainty in Environmental Modelling Competition

http://theoval.cmp.uea.ac.uk/~gcc/competition/

に勝ったアルゴリズムには local minimaがあります。


Variable noise and dimensionality reduction for sparse Gaussian processes

http://www.gatsby.ucl.ac.uk/~snelson/snelson_uai.pdf


元のalgorithmがconvexでも、semi-supervised や unsupervisedにしたり、hidden variableをつけるとconvexityが失われることが多いので、なんというか、ある種の良い non-convexityというものがあるような気がします。


=======

最適化の方法。 

スタンダードな教科書は多分、

Numerical Optimization (Nocedal & Wright)

http://www.ece.northwestern.edu/~nocedal/book/num-opt.html


SMD (Stochastic Meta Decent)

特に最近はやっているように見えます。 


http://users.rsise.anu.edu.au/~nici/pubs/mvp.pdf

http://users.rsise.anu.edu.au/~nici/bib2html/b2hd-SMD_60min.html


SVMを速くする (JMLR)

http://users.rsise.anu.edu.au/~nici/pubs/SVMDjmlr.pdf


強化学習を速くする (NIPS05)

http://users.rsise.anu.edu.au/~nici/pubs/nips05.pdf


Conditional Random Fieldsを速くする (ICML06)

http://users.rsise.anu.edu.au/~nici/pubs/crfsmd.pdf


Video Tutorial

http://seminars.ijs.si/pascal/2005/mlss%5Fcanberra/

http://seminars.ijs.si/pascal/2006/mlss06%5Fcanberra/


Hidden Variableを入れたり、Semi-supervised にしてUnlabeled Sample を使うとObjectiveがConvexでなくなってしまうことが多いんですが、そのときにどうするか、という話です。 


Continuation Methods

http://www.icml2006.org/icml_documents/camera-ready/024_A_Continuation_Metho.pdf


それから、上でも出てきたTrading Convexityの論文の、Concave-Convex Procedureがあります。

=======

Directed Graphical Modelの系統

Indian Buffet Processを使った論文

このChoice Modelでは、MCMCのやり方できちんとExchangabilityを使えば、サンプリングがもっと正しくできる、という話が出ていました。

http://www.icml2006.org/icml_documents/camera-ready/046_A_Choice_Model_with.pdf


パチンコ Allocation

http://www.cs.umass.edu/~mccallum/papers/pam-icml06.pdf


Clustering Documents with an Exponential-Family Approximation of the Dirichlet Compound Multinomial Distribution

http://www.icml2006.org/icml_documents/camera-ready/037_Clustering_Documents.pdf


Topic Modeling: Beyond Bag-of-Words

http://www.icml2006.org/icml_documents/camera-ready/123_Topic_Modeling_Beyon.pdf


Language Modelですが、Kneser-Ney という、多分一番効果的な smoothing methodを Graphical Modelと関連づけるすごい論文です。

A Hierarchical Bayesian Language Model based on Pitman-Yor Processes

http://acl.ldc.upenn.edu/P/P06/P06-1124.pdf


ここからは単純な Topic Model以外の Graphical Modelです。

次は機械翻訳に出てくる問題の、Word Alignmentを、言語A -> Bへのモデルと、B -> A へのモデルをjoint graphical modelで統合して、Unsupervisedで発見する方法です。 綺麗です。

Alignment by Agreement

http://www.cs.berkeley.edu/~pliang/papers/alignment-naacl2006.pdf

http://www.cs.berkeley.edu/~pliang/papers/alignment-naacl2006-talk.pdf


Segmentation & LabelingをUnsupervised Graphical Modelでやる話です。

Unsupervised Topic Modelling for Multi-Party Spoken Discourse

http://acl.ldc.upenn.edu/P/P06/P06-1003.pdf


Bayesian Query-Focused Summarization

http://acl.ldc.upenn.edu/P/P06/P06-1039.pdf


Contextual Dependencies in Unsupervised Word Segmentation

http://acl.ldc.upenn.edu/P/P06/P06-1085.pdf


=======

機械翻訳と係り受け解析で面白いと思った論文


Prototype-Driven Grammar Induction

http://www.cs.berkeley.edu/~aria42/pubs/acl06-grammarinduction


A Discriminative Global Training Algorithm for Statistical MT

http://acl.ldc.upenn.edu/P/P06/P06-1091.pdf


An End-to-End Discriminative Approach to Machine Translation

http://acl.ldc.upenn.edu/P/P06/P06-1096.pdf


Left-to-Right Target Generation for Hierarchical Phrase-based Translation

http://acl.ldc.upenn.edu/P/P06/P06-1098.pdf


Advances in Discriminative Parsing

http://acl.ldc.upenn.edu/P/P06/P06-1110.pdf