■

http://nensyu-labo.com/
平成19年の国税庁による年収データを年齢別でグラフ
各年齢別の詳細データは以下の通りだそうです

年齢____ 男性 女性
70歳以上 411 253
65〜69歳 398 215
60〜64歳 505 233
55〜59歳 638 263
50〜54歳 667 266
45〜49歳 662 278
40〜44歳 634 281
35〜39歳 560 296
30〜34歳 463 300
25〜29歳 381 295
20〜24歳 271 231
19歳以下 156 126
平均____ 542 271
（万円）
国税庁　平成19年　民間給与実態統計調査結果より

ICML2007 ＆ 自然言語処理

一年ぐらい更新をさぼってました。
書かないとだめですね。。
注目していた論文の名前がわからなくなってしまったりします。

自然言語で使えそう(?)なICML2007の論文をリストしてみます。

                                        • -

構造予測する分類器で、Decoding を軽くするような話

On Learning Linear Ranking Functions for Beam Search
http://www.machinelearning.org/proceedings/icml2007/papers/168.pdf

CarpeDiem: an Algorithm for the Fast Evaluation of SSL Classifiers
http://www.machinelearning.org/proceedings/icml2007/papers/252.pdf

                                        • -

同じタイプの学習器の比較と、Ensembleの話

Comparisons of Sequence Labeling Algorithms and Extensions
http://www.machinelearning.org/proceedings/icml2007/papers/206.pdf

                                        • -

Domain Adaptaiton, 半教師付学習 関連

Two-view Feature Generation Model for Semi-supervised Learning
http://www.machinelearning.org/proceedings/icml2007/papers/154.pdf

Discriminative Learning for Differing Training and Test Distributions
http://www.machinelearning.org/proceedings/icml2007/papers/303.pdf

Experimental Perspectives on Learning from Imbalanced Data
http://www.machinelearning.org/proceedings/icml2007/papers/62.pdf

Boosting for Transfer Learning
http://www.machinelearning.org/proceedings/icml2007/papers/72.pdf

Uncovering Shared Structures in Multiclass Classification
http://www.machinelearning.org/proceedings/icml2007/papers/229.pdf


ICML2007 以外
Learning Multiple Related Tasks using Latent Independent Component Analysis
http://nyc.lti.cs.cmu.edu/yiming/Publications/zgy-nips05.pdf

                                        • -

距離を学習する話

Information-Theoretic Metric Learning
http://www.machinelearning.org/proceedings/icml2007/papers/404.pdf

Learning Distance Function by Coding Similarity
http://www.machinelearning.org/proceedings/icml2007/papers/158.pdf

A Transductive Framework of Distance Metric Learning by Spectral Dimensionality Reduction
http://www.machinelearning.org/proceedings/icml2007/papers/219.pdf


ICML2007 以外
Toward Robust Distance Metric Analysis for Similarity Estimation
http://www-rocq.inria.fr/imedia/Articles/Toward_Robust_Distance_Metric_Analysis_for_Similarity_Estimation.pdf

Boosting Margin Based Distance Functions for Clustering
http://www.cs.huji.ac.il/~daphna/papers/distboost-icml.pdf

                                        • -

距離を学習する話と分類問題の関係

On the Value of Pairwise Constraints in Classification and Consistency
http://www.machinelearning.org/proceedings/icml2007/papers/192.pdf

Optimal Dimensionality of Metric Space for Classification
http://www.machinelearning.org/proceedings/icml2007/papers/35.pdf


ICML2007 以外
Learning a Kernel Function for Classication with Small Training Samples
http://www.icml2006.org/icml_documents/camera-ready/051_Learning_a_Kernel_Fu.pdf

                                        • -

テキスト関連のKernel

Fast and Effective Kernels for Relational Learning from Texts
http://www.machinelearning.org/proceedings/icml2007/papers/461.pdf

                                        • -

Logistic Regression の最適化系統

Scalable Training of L1-regularized Log-linear Models
http://www.machinelearning.org/proceedings/icml2007/papers/449.pdf

Trust Region Newton Methods for Large-Scale Logistic Regression
http://www.machinelearning.org/proceedings/icml2007/papers/114.pdf

Exponentiated Gradient Algorithms for Log-Linear Structured Prediction
http://www.machinelearning.org/proceedings/icml2007/papers/472.pdf

                                        • -

SVM の最適化系統

Pegasos: Primal Estimated sub-GrAdient SOlver for SVM
http://www.machinelearning.org/proceedings/icml2007/papers/587.pdf
http://www.cs.huji.ac.il/~shais/code/pegasos.tgz

                                        • -

Non-parametric Bayses, Topic Models, Language Models など

Infinite Mixtures of Trees
http://www.machinelearning.org/proceedings/icml2007/papers/180.pdf

Unsupervised Estimation for Noisy-Channel Models
http://www.machinelearning.org/proceedings/icml2007/papers/225.pdf

Three New Graphical Models for Statistical Language Modelling
http://www.machinelearning.org/proceedings/icml2007/papers/425.pdf

Mixtures of Hierarchical Topics with Pachinko Allocation
http://www.machinelearning.org/proceedings/icml2007/papers/453.pdf

Unsupervised Prediction of Citation Influences
http://www.machinelearning.org/proceedings/icml2007/papers/257.pdf

                                        • -

Online Learning 関連

Online Discovery of Similarity Mappings
http://www.machinelearning.org/proceedings/icml2007/papers/591.pdf

Winnowing Subspaces
http://www.machinelearning.org/proceedings/icml2007/papers/497.pdf

                                        • -

ICML以外
Keyphrase Extraction using Semantic Networks Structure Analysis
http://www.jdl.ac.cn/user/chuang/paper/ICDM_Full.pdf

The Intelligent Surfer
http://research.microsoft.com/users/mattri/papers/nips2002/qd-pagerank.pdf

log(1+d^2) norm --- Cauchy distribution
http://www.stat.columbia.edu/~cook/movabletype/archives/2006/11/bayesian_infere_3.html

NIPS2006 ＆ 自然言語処理

NIPS 2006で、自然言語処理に使えそうな論文のリストです。

Scalable Discriminative Learning for Natural Language Parsing and Translation
http://books.nips.cc/papers/files/nips19/NIPS2006_0873.pdf

Training Conditional Random Fields for Maximum Parse Accuracy
http://books.nips.cc/papers/files/nips19/NIPS2006_0891.pdf

Learning to Model Spatial Dependency: Semi-Supervised Discriminative Random Fields
http://books.nips.cc/papers/files/nips19/NIPS2006_0629.pdf

Multi-Task Feature Learning
http://books.nips.cc/papers/files/nips19/NIPS2006_0251.pdf

Analysis of Representations for Domain Adaptation
http://books.nips.cc/papers/files/nips19/NIPS2006_0838.pdf

Large Margin Gaussian Mixture Models for Automatic Speech Recognition
http://books.nips.cc/papers/files/nips19/NIPS2006_0143.pdf

Dirichlet-Enhanced Spam Filtering based on Biased Samples
http://books.nips.cc/papers/files/nips19/NIPS2006_0479.pdf

Modeling General and Specific Aspects of Documents with a Probabilistic Topic Model
http://books.nips.cc/papers/files/nips19/NIPS2006_0305.pdf

Computation of Similarity Measures for Sequential Data using Generalized Suffix Trees
http://books.nips.cc/papers/files/nips19/NIPS2006_0685.pdf

質問応答

Analytical QA の課題の一つは、質問と答えの間にまったく共通する単語がないケースが多いことだと思われます。

例えば、「過去五年に起こった重大な事件について知りたい」というQueryがあるばあい、事件とはなんなのか？ 地震、津波、洪水、9/11やサリン事件のような攻撃、それとも、殺人や誘拐？　日本国内の事件なのか、といったことが問題になってきます。

手前味噌ですが、HITIQAという質問応答のシステムにかかわったことがあります。
http://www.ils.albany.edu/paper.html

HITIQAシステムでは、「アルカイダは資金、武器などをどう調達しているのか？」などの質問の場合、大まかにTransferというFrameを持っているものと解析します。　売るのも、買うのも、寄付するのも、援助するのも、調達するのも、全てTransferです。 Transferされるものは、兵士であったり、武器であったり、お金や麻薬などです。

質問を解析した後は、 IRで見つけたドキュメントからもTransferのFrameを見つけて比べて見ることで、賢く会話や要約をしようとします。　parsingより、抽象度はかなり高くなります。　HITIQAでは、この、Transfer Frame という、抽象的な概念に質問と答えの両方を持っていくことで、QueryとAnswer間の言葉のギャップを塞いでいるわけです。　FrameにはEntity同士の関係を規定しているのですが、Semantic Role Labelingよりも更にアブストラクトで、まず、どちらが主語で、どちらが目的語なのか、などは関係なくて、Knowledgeとして何処から何処へ物の移動があったかが分かればいい、と言った感じです。　こうして質問と答えのギャップをontologyっぽいものとrelationの両方で塞いでいるわけです。　FrameNetなどでも、lingusticsの色が強くなると、頑張っているんですが、ちょっと fine-grain になる傾向があるような気がします。

さらに、Entity Detection & Tracking ですとか、Query basedClustering/Summarizationといった話が重要になってくると思うのですが、QAのシステムは伝統的にpipelineやコンポーネントが多すぎて、綺麗に統合された良いモデルを作るのが難しいのが課題の一つであると思います。　他の人が作ったコンポーネントはブラックボックス、一番単純なシステムを構成して繋げるだけで
一苦労という、結構泥臭いソフトウェア開発になってしまいがちで、そのせいで、いい研究がやりにくくなっている側面があります。

良いPrincipledな方法でQAシステムを作るには、まず、Query と Answer のギャップを埋め、結びつける核となる革新的な洞察が必要で、理想的にはその洞察をきちんとテストすることが大切です。　

どの研究所でもフォーマルな形でこういうことは出来ていないと思うのですが、例えば、Query と Answer を結びつけるのは Case Frame と、IRでいうところの Vector Space Modelである、と、まずHypothesisを立てます。　これが核となる洞察です。　そうしたら、そこにあわせて、全てのコンポーネント、IR, Clustering, Summarization, Dialogue Componentのそれぞれを、Case Frame + Vector Space Model の全ての情報を使いきるよう設計、最適化して構築します。　トータルで見て、全てのコンポーネントがしっくりと繋がるような核が必要です。　それができたら、次に別の核を作ります、例えば核となるのはHITIQA Frame + Latent Sematic Indexingのほうが良い、ということもありえます。　ふたたび、HITIQA Frame + LSIの全てを使いきったIR, Clustering, Summarization, Dialogue Componentを作り、最適化します。　

HITIQA Frameの良い所は、これを使って、図書館の司書の方と会話をするかのように、欲しい情報へとユーザをガイドできることです。　例えば、「日本について知りたいのですが？」「日本の歴史について知りたいのですか？」「それとも、日本の経済ですか？」などと、会話が出来るわけです。　その結果、要約した内容でユーザが欲しがった物だけを見せることができます。　

もしかしたら、これはずるい方法ですが、核にする部分はQuery -> Answer ペアが大量にあるFAQの巨大なデータベースが良いのかもしれません。　企業のユーザ・サポートのQAシステムだと、そういったFAQがある可能性もあります。　AQUAINTで、あるグループの論文は、そのどおりにつくっても同じ性能をreplicateできず、そのグループは論文の内容も作ってはいるが、実際は、バックアップとして人海戦術で上の方法を取ったために性能が高くみえるだけではないか、と疑われています。

話がそれましたが、二つシステムがあって、ようやく意味のある比較が出来ます。きちんとした社会科学系のユーザ・スタディを実験の形で行い、ユーザが、どんな使い方のシナリオで、どんな質の情報を、どれぐらいの時間で得られ、どちらのシステムでどれぐらい満足したか、という統計をとります。　もしかしたら、シナリオによっては、Case Frameの方が　Factoid QAに強く、HITIQA Frameの方がAnalytical QAに強いということが起こるかもしれません。　あるいは、エラー分析の結果、どこのコンポーネントからエラーが増えて、それを補うには何か別な情報がいる、という方向で改良が進むかもしれません。　それを何回か繰り返して改良して、はじめて良いQAの研究をした、と言えるのではないでしょうか。　そうでないと、Ad Hocにコンポーネントをつなげて、なにかけど一つシステムが出来た、で終わる可能性が高く、誰が見ても分かるsignificantな質の違いがある、というような結果は出せないのではないでしょうか。　Pipelineの、どこがまずいのかも分かりにくいし、ここまでやるには強力なプログラマーが何人か必要だし、研究ではない部分の実装や実験もかなり出てくると思います。

興味がないコンポーネントを仕様がかなり指定された段階で担当してしまうと、人によっては研究者として素質が良いがために逆に生産性が落ちるケースがでてきますし、ひとつの論文を十人で書くというのは、核となるアイディアに十人が振り回されるということで難しい面もあるかと思います。　ただ、その分、QAのような大きなシステムに携わるのは、やりがいもあると思います。　

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