2008.02.15

線形識別器チュートリアル

ワークショップ中の夕食で話したのですが、今のところ日本で(素性関数ベース&線形識別器)機械学習のいろいろな手法をまとめて体系的に教えてる資料などがあまりないなぁという話をしていました。

で、探すと、このあたりの大部分をまとめて説明しているいいチュートリアル(英語)がありました。
夏の学校資料[pdf]
その他のコードやリンク

ちょっとだけ解説

現在自然言語処理の多くで使われている学習器は線形識別器です。
入力x(例:単語、文、文書)から出力y(例:品詞、品詞列、文書のトピック)を予測したいという場合は、(x,y)のペアからいろいろな値を取り出し(x,yのペアから値を取り出す関数を素性関数と呼ぶ)、その値を並べたベクトルを素性ベクトルと呼び、f(x,y)とかきます。そして、その素性ベクトルf(x,y)と同じ次元数を持つ重みベクトルwとの内積を測って、その値が正か負か、または大きいか小さいかを調べて、出力は何が尤もらしいかを予測します。

機械学習では、この重みベクトルwを正解データの集合(x_1, y_1), ..., (x_n, y_n) を使って、推定(普通は訓練と呼ぶ)します。正解が正しくでるようにwをチューニングするわけです。このチューニングは基本的には訓練データから各素性に関する統計量を取り、最適化問題を解く事で行われます。

例えば、入力が文書で、出力が「その文書がスパムだったら正の値、そうじゃなかったら負の値をとる」、という問題の場合は、まず、実際にスパムかどうかのラベルがついた文書集合を集めます(もしくは自分で作る)。次に素性関数を設計します。文書分類の場合は単語の出現が重要な情報となるので、各単語が1次元分を担当し、各素性の値は例えばその出現回数とすることが多いです。

素性関数1, 2, 3, 4がそれぞれ単語"Best","Drag","Congratuation","flower"に対応するとしたら、訓練データを使って重みベクトルを訓練すると、重みベクトルは(-1, 3, 1, -2)というふうに、drag, congratuationが出たらスパムとなって、best, flowerが出たらスパムじゃないとなってくれるように学習されます。

それで文書として、best, drag, congratuation, flowerという単語がそれぞれ、1, 3, 0, 1回出現しているものが与えられたら、その素性ベクトルは(1,3,0,1)であり、重みベクトルとの内積は -1*1 + 3*3 + 0*0 + 1*1 = 9 となり、これは正なのでスパムとめでたく判定されるわけです。

線形識別器は非常に単純ですが、それでも自然言語処理だと有効です。理由の一つとして、次元数が非常に大きく(例えば数千万次元とか)、線形でも十分区別する能力があるということがあげられます。

で、問題はどのようにこのwを訓練するかということになり、これには、いろいろな方法があります。例えばNaive Bayesは一番単純なモデルです(それでも強力だが)。このモデルでは各次元が完全に独立だとし、それぞれ独立に学習、推定し、結果をまとめます。

もうちょっと賢い線形識別器だと、各素性は独立じゃなく相関があるものだとし(推定時は独立に扱うが)、学習時にどのような基準(損失関数)で学習するかも工夫されてます。

有名なのだと、出力が簡単な問題(例えば文書分類とか二値分類)を解こうとする場合は次のようなものがあります。
- 線形対数モデル(最大エントロピーモデル、ロジスティック回帰)
- (Linear) Support Vector Machines

出力が構造を持ってる場合、例えば系列(品詞列とか形態素列)とかの場合は、上記のそれぞれが次のようなモデルに拡張されます。
- Conditional Random Fields (条件付確率場)
- Max-margin Markov Network
これらのモデルでは出力、素性、損失関数が部品に分解できるようになっており、出力の候補数が入力長の指数個に比例する数ぐらいあっても動的計画法などで効率よく学習/推定ができるようになっています。

あとは、実装が非常に簡単だけど強力な次のような手法があります。これらはオンライン学習、つまり訓練データを1例ずつ見てパラメータを更新していきます。
- Averaged Perceptron 
- Structured Perceptron 
- MIRA

これらについては上記のチュートリアルにまとめられてます。

#あるといっても広く知られるためにも、やはり日本語の資料もつくりたいですね。

| | Comments (0) | TrackBack (0)

2007.12.15

nips 2007 tutorial

nips 2007(行ってないけど)のtutorialが例年のようにweb上から見れるようになってます [link]
たぶんそのうちvideoも公開されるのでしょう。
面白いもの揃いですが、とりあえず目についたのは次の二つかな

Learning Using Many Examples
非常に大量の訓練用データが使える場合の学習はどうすればいいのという話。結論から言うとStochastic Gradient Descent(確率的勾配降下法)が理論的にも、実践的にも優れている。
パーセプトロンスタイルの学習(Online Passive Agressive Algorithm [pdf])とか、Online Exponentiated Gradient Algorithm[pdf]とか、どんどんオンライン型学習(データまとめて見ないで、一個ずつ見てすぐパラメータ更新する)手法の優位性がどんどん示されてきてます。実装もどんどん楽になります。

Deep Belief Nets
最近の学習モデルは隠れ層(観測できない層)が無いか、多くても1層の場合が殆どだけど、旧来のニューラルネットワークのように非常に深い層を使って学習する手法が、最近多くのタスクで今の最新手法を超える高性能を挙げはじめてます。
#隠れ層の数が1つでも、それ以上でも表現できる能力は等価であることは示されているが、特徴間に高次の相関があるような有限個の訓練データを使って学習できるかということになると、多層の方がモデルを遥かにコンパクトに表現できるので、多層の方がいい。
これは学習手法の発展があったことが大きく(1層ずつgreedyに学習させてから全体をcontrastive divergenceで学習しなおす)、従来では想定できなかったような大量のパラメータ、層数で学習、推定ができるようになってて、文書の関連度合の高速なhashingとか、従来想定されていない用途にも使われるようになってます。[link]

| | Comments (0) | TrackBack (0)

2007.11.21

マルコフ情報源上で次の文字を予測する

文字列(単語列)を解析する際、i番目の文字はその直前(N-1)文字のみ依存するというマルコフ情報源を仮定することはいろいろな場面で現れます。

例えば音声認識とか機械翻訳では、次の単語を直前(N-1)単語を使って予測するというN-gramモデルが古くから今でも使われてますし、データ圧縮でもこれと全く同じように履歴を使って次の文字を予測し、その予測確率を用いて符号化するPPMモデルがあります。

ここで問題になるのは、何文字前まで見れば次の文字を予測できるかということが一般のデータだと分からないということです。例えば4文字前まで見た場合より5文字前まで見たほうが次の文字が確実に予想できそうですが、4文字前までは過去のデータで何回もでているのに5文字になると途端に出現回数が少なくなってサンプル数が少なくなってしまい予測精度が低下してしまう問題があります。

そのため大抵は1,2,3..,N文字前の文字を使ってそれぞれで予測した結果の線形結合を最終の予測として使ったり、もしくはk文字前まで見れば一番確信度が高いというようなkを別の方法で求めてk文字前までの結果を使って予測します。

で、最近でも様々な方法が提案されてきましたのでちょっと紹介

言語モデルでは最近mochihashiさんがSuffix Tree上に階層型Pitman-Yor Processを載せる方法("The Infinite Markov Model" [pdf])を提案していて、何文字(単語)前まで見て次の文字を予測するとよさそうなのかというのを求めてます。すごい。

データ圧縮の分野だとppmII("PPM: one step to practicality"[pdf])ので使われている方法が高精度です。どの深さまで見るかというのは、”見る履歴を一文字短くする”命令を表すescape文字の出力確率でコントロールできます。このエスケープ確率を様々なコンテキスト情報で条件付けて推定します。この推定には過去の情報を利用して最尤推定っぽいことをしています(SSEとよばれる部分)。コンテキスト情報は最頻の文字の頻度情報から、周期(英語だと単語の区切れ目で過去のことを忘れてよい確率が高くなる)などなどなんでも使ってます。例えば表データとかは一定文字数毎に全く違う分布に切り替わることがおこるのですが、そういった傾向もとらえることができます。

データ圧縮ではBWTという手法もあります。BWTでは履歴情報を直接扱わずに各出現文字を接尾辞をキーとして使ってソートします。この変換後の文字列は同じ文字が連続しやすく圧縮しやすくなっており、これを単純な符号法でencodeしてもかなり圧縮できることが知られており、任意のk文字前まで見て次の文字を予測して符号化した場合の結果にかなり近づくことが知られています("A simpler analysis of Burrows-Wheeler based compression"[ps] "Most Burrows-Wheeler based compressors are not optimal"[ps])。
bwtでの符号は昔はMTF + RunLengthが使われていたのですが、最近ではDistance Coding(A Simpler.. の中に説明あり)と呼ばれる手法が理論的にも実用的にも高精度だというのが知られてます。
しかし、Most Burrows-Wheer...で述べられているように本当にマルコフ情報源から生成されたデータでBWTを試すとLZ法とかと比べても性能が悪くなってしまう現象がおきます。自然言語はマルコフ情報源で仮定するのは大胆すぎるとはよくいわれていますが、BWTが自然言語上では実験的にはなぜ他の手法よりうまくいくのかを説明するあたりに、よりよい自然言語のモデル化があるのかもしれません(全くないかも)

#となるとbwt + distance codeから演繹される確率分布を使って次の文字を高精度に予測することができるかも、という怪しい話を今ためしにやっているところです。符号化の順番が前から後ろじゃないのでちょっと難しいですが・・

機械学習の分野では、確率を出さなくても、当てればいいというマージン法+Perceptronでやっている手法もあります。下記で紹介されてます(論文はないようで本でしか情報がないです。どこかに落ちてる?)
"Discriminative Learning of Prediction Suffix Trees with the Perceptron Algorithm", Ofer Dekel, et. al., Predicting Structured Data
各履歴がfeatureになっていてそれぞれに重みがついていて(重みは深くなると指数関数的に小さくなるようになている)、あたらなかった場合は通常のパーセプトロンのように現在の重みに足しこみます。これをそのままやった場合は、履歴の数は非常に多くなってしまい使うfeatureの数が膨大なものになります。しかし、ちょっと工夫することで木の深さを「間違えた回数」に制限しても性能は保証できることが示されてます。ただ、実験結果がないので実際試してみようかなぁ・・

| | Comments (3) | TrackBack (0)

2007.11.05

L1正則化付LLMの双対化

タイトルの内容で現在開催中のIBIS 2007で発表してきました。論文[pdf] 発表パワポ [ppt]

タイトルからしてよくわからない人もいると思うので”タイトル”を簡単に説明します。

まず LLM (Log Linear Model)というのは指数型分布族と一般に呼ばれるのですが、p(x; w) = exp(wx - Z'(w)) x∈R^m, w ∈R^mの形をしている確率分布です。自然言語処理などでは最大エントロピーモデルとかCRFとかいろいろ名前を変えて使われているモデルです。いろいろな確率分布(例えば正規分布)がこの形に属します.Log-linearというのはこの確率分布の対数をとると、log p(x) = wx - Z'(w) と線形の式がでてくるところからそう呼ばれています。

次は、L1正則化です。やりたいことは訓練データを利用して確率分布を決定するパラメータを推定することです.指数型分布族の場合はwを求めることになるのですが、オーバーフィットの問題が常につきまといます。例えば高次の多項式で二次元中のn点を通る関数を求めようとすると,がたがた振動するようなことがおきますが、今回推定する場合もwを推定するのに十分データがないので同様の問題が発生します。あまりフィットしないで滑らかで単純なモデルを選ぶように指定する部分が正則化になります。正則化の中でもL1正則化は最近注目されています。というのは、この正則化を適用すると多くの重みが0に潰されるといういい性質があるからです。自然言語処理タスクの場合はmが数百万にもなりwが数百万次元のベクトルとなるのですが、L1正則化を使うと、wの成分の殆どが0になってくれて、結果が分かりやすい、速い、省メモリといいところだらけです。

で、最後が双対化。今回の確率分布の推定問題は最適化問題を解くことによって得られます。最適化問題とはf(x)という関数があってこの関数の値を最大(最小)にするxを探す問題です。一般に最適化問題は難しい問題なのですが、今回解くのは、その中でも解きやすい凸最適化問題になっています。双対化は、この問題を直接解かずに、それと同じ解にたどり着くような解きやすい問題に変換するものです。今回も最終的に解く問題はパーセプトロンのような非常な単純な式になりました。数値最適化とかの手法とかは必要いらずで実装も簡単です。

ずいぶん適当にかいてみましたが、これで少しはタイトルが分かっていただけましたでしょうか。ppt, pdfをみていただける人が増えたら幸いです。いたらすごい。この論文で作った実装も将来的には公開する予定です。

ちょこちょこ修正してすいません。
 

| | Comments (3) | TrackBack (0)

2007.08.04

機械学習の実用化

プログラマがどうたらこうたらという話はあんまり乗らないけど

このブログ
東大関連の話はkzkさんのを参考にしてもらうとして

>もちろん、実装は中学生でもできることだ。

機械学習を実用化レベルに持っていくためにはかなりの総合力が必要だと思います。
数学的な知識や機械学習の知識はもちろん、数値最適化の各手法やデータ構造を使い分けて、高速化、省メモリをどう達成するか、現実世界に発生するモデル化しきれないノイズをどう取り除ければいいかとかまで考えないといけない。

そのまま作ると、重い、動かない、間違っている、なんかよく分からないのが出るってことになると思います。
やりがいのあり面白いですが、結構大変。

機械学習も流行っているのは流行っているかもしれんですが、圧縮とかこれらの全部機械学習と一括りするのは違う気がする。根底に流れているのは似ているけど

例えば、JMLR とかにある論文を読んでまともに動かすのは大変だと思います。SIGGRAPHでやっている実装競争の機械学習版とかとかしてみたいですけどねぇ。

| | Comments (4) | TrackBack (0)

2007.07.25

講義ビデオ

一度は見てみたかった(知っている人は知っていて知らない人は全然知らない)有名人の話している講義ビデオが見られるvideolecturesというサイトがありますが、そこにICML2007の発表のいくつかがアップされてるようです。link
よくみてみたら他の学会のもたくさんあるんですねlink2

| | Comments (0) | TrackBack (0)

2007.06.15

最大エントロピーモデル

自分の復習も含め、最大エントロピーモデルについて勉強会で発表しました。発表資料 [ppt] [pdf]
今年のACLやICMLなどでの発表などを解説してます。論文中になかった式導出とかもしてみてます。
発表中では結構口頭で補足した部分があって、この資料だけでは不十分だと思います。適宜引用先などを参照してください。

最大エントロピーモデルは高次元の確率分布推定に適していて自然言語処理や、最近だと動植物がどのように分布しているかなどの推定等、広い分野で使われている確率モデルです。

#修正+質問・回答スライドを追加しました

| | Comments (1) | TrackBack (0)

2007.06.12

凸最適化

凸最適化問題に触れる機会が多くなり、復習しています

凸最適についてはboyd本が有名ですが(なによりpdfがおいてある)、730pは読むのが大変です。講義用スライドが絵も多くおすすめです。

凸最適といえば、離散凸最適もちゃんとおさえときたいですが、よさそうなチュートリアルとかはないですかねぇ。

凸が縦に並ぶとおもしろいなぁ

| | Comments (4) | TrackBack (0)

2007.06.04

Core Vector Machine

SVMをはじめとした、多くの"Kernel法を利用した凸二次計画法問題"は、ある条件(自分自身同士のカーネル値が常に定数)を満たしていれば、適切に問題を変換することで最小包含球問題として解けることが知られている(core vector machine [google scholar] )。

凸二次計画法問題は入力データサイズに対してスケールせず、訓練データ数が1万以上とか多くなるととたんに破綻するのに対して、最小包含球問題は近似法がいくつか知られており、それらを利用すれば大規模な訓練データを利用した学習が可能となる。

で、その最小包含球の近似法の一つに中心を適当に決めて半径を決めた後に、球から外れている要素をぽこぽこ追加し、半径を最小にしつつ中心を更新していく方法が提案されたが[link]、結局中心の更新式がPassive-Agressive Learning[link]と殆どに似た形になり、パーセプトロンの学習則のように(変換された)訓練データを重み付きでたしこんでいく形になる。

似て当然な気もするけど最後が似た形になったので気持ちいいなぁ。

そう思った日曜の昼下がりでした。

| | Comments (2) | TrackBack (0)

2007.02.14

本当?

ロジスティック回帰分析と線形対数モデルと最大エントロピーモデルって式の形は違いますけど、(featureを入力とラベルのペアにとれば)同じモデルですよね。不思議

| | Comments (4) | TrackBack (0)

2006.06.12

教師あり学習の比較

ICML2006に興味深い論文がありました。
"An Empirical Comparison of Supervised Learning Algorithm", Rich Caruana caruana and Alexandru Niculescu-Mizil [link]

90年代初め以降、数多くの画期的な教師あり学習が提案されてきましたが、どれがいいかを包括的に比較したことはあまりありませんでした (文書分類などでは、SVMとAda-boosting 強いねということだったのですが Sebastiani@ACM Survey 2002
決着をつけようじゃないかということで、11の問題に対してハイパーパラメータも完璧にチューニングして、いろいろな分類器を比較しているみたいです。比較内容は精度や再現率やクロスエントロピーなど様々で、確率を直接出さないやつはsigmoid関数など単調増加関数を通して変換して確率を出すようにすると。

比較したのは以下の分類器
Support Vector Machines (SVMs)
Artificial Neural Network (ANN)
Logistic Regression (LOGREG)
Naive Bayes (NB)
K-Nearest Neighbors (KNN)
Random Forest (RF)
Decision Trees (DT)
Bagged Trees (BAG-DT)
Boosted Trees (BST-DT)
Boosted Stumps (BST-STMP)

で結果を言ってしまうと、
BST-DT RF BAG-DT SVMs ANN KNN BST-STMP DT LOGREG NB
の順らしい。詳しくは論文を読んでください。
で、以下は勝手な意見など。
SVMが意外に低く、決定木関連(Random Forest含めて)が強いということだが、それは各問題で特徴種類数が10-100と少なく、特徴を全部列挙して調べられる範囲だというのが大きいのだと思う。まぁ、そうはいってもきちんとチューニングして、特徴を適切に選べるのであればBST-DTやRFの性能はいいのだよということで。

特徴種類数が数千から数十万の場合で傾向は変わってくるんでしょうかね。比較されていなかったMaximum Entropy法とかはこうした状況だと効いてくるだろうし。

#教師付き学習?教師あり学習? そして、どちらもぐぐったらひっかかるのがすごく少ない・・

| | Comments (4)

2006.05.10

Searn

Searn (Search and Learn)はStructured Predictionを行うためのアルゴリズムです。

#発表の仕方がいろいろあったみたいですが、今回はそのことには触れません。論文の投稿数が増えていてレビュアーの負担が増えているのは確かですよね。

Structured Predictionは構造を持った出力を学習する問題です。例えば、品詞付けや、固有表現抽出などのシーケンスラベリングの問題やパーシングの構文木を求めたり、統計的機械学習でよくされる翻訳前と翻訳後の単語のアライメントをするためのマッチングを求めたりなどは全てこのStructured Predictionの範疇に入ります。今までこうした問題は小さい問題に分割して、それぞれ小問題の最善な結果を集めたものが全体の答えの一番よいものという形で解いていたのですが、全体の出力に制約がかかっている場合や全体の特徴を使いたい場合は直接構造を持った出力を予測することが必要となります。

これを解く方法は例えばConditional Random Fieldsやmax-margin Markov networks、multi-class SVMの延長線上にある最適化問題を解く形で問題を解方法などが提案されています。

SearnはStructured Prediction問題を探索問題として扱い、各ステート上でのアクションを次々と選んでいくことによって問題を解きます。例えばシーケンスラベリングの場合は各ステートはそれぞれの位置(とそれまで付けたラベル)に対応して、各アクションはその位置にどのラベルをわりあてるかに対応しますし、木構造の問題は決められた順番に木構造を決めていく(例えばshift, reduceで)ことになります。このままだと、今までの小問題に分割していた方法と同じようですが、違うのがgreedyに各問題を解いていっても全体として最適な値となるように問題を調整/学習するという点です。例えばシーケンスラベリングである時点で、ラベルAを選んだ場合、その時点では全体の結果からそれがどれだけ良いアクションだったかはわかりませんが、それ以降いろいろ選んだ結果の期待値と、最適なラベルを選んだ場合の結果との差を求めて、それをそのアクションを選ぶ際のreward(報酬)とします。これは強化学習と同様のアイディアで、全体の損失関数が少なくなるように各ステップが良いアクションをとれるような報酬を決定していきます。これをブースティングのように収束するまで何回も繰り返します。

実際にはもうちょっと複雑なことになっていて、訓練時最初探索する範囲は、正解のシーケンスに対応するところですが、そこから、実際にテスト時に探索するようなところに少しずつ離れていく(正解のシーケンス情報を出力するoptimal policyが少しずつ薄まる)ことなります。

高速化のためにもいろいろやられているようで、例えば途中のラベルAを選んだ結果の全体の損失関数の期待値を真面目に求めるのは大変なので、モンテカルロサンプリングとして何回か最後まで探索問題をおこなって、その結果を期待値として使ったりするようです。他にも高速化のためにいろいろ工夫があるようですが、それは公開されるとしているソースコード読んでみないとわからない。

まだ、いろいろ分からないところがあります。例えば過学習してしまうよねぇとか、パーシングなど探索空間が広く、ステートが大きく間違えた方向にいってしまった場合でもこの手法有効に働くのかなどです。

それでも、Structured Predictionは複雑になりがちな中でこのような簡単な枠組みでできるというのはありがたい。

| | Comments (0) | TrackBack (0)

2006.04.21

Structural learning

Structural Learningはsemi-supervised learningを行う新しい手法です。

(構造を持った出力を予測するStructured output predictionとは関係ないです)

この話は、次の中で提案されています
"A High-Performance Semi-Supervised
Learning Method for Text Chunking.", R. K. Ando, T. Zhang, ACL 2005, [pdf]
ジャーナル版
"A Framework for Learning Predictive Structures from Multiple Tasks and Unlabeled Data", R. K. Ando, and T. Zhang, Journal of Machine Learning Research [pdf]

Semi-supervised learningは、機械学習を行う際、正解の付いた教師付きデータだけではなく、大量の教師無しデータを利用することで、精度を向上させようとするもので、今までにco-training, transductive inference, EM, bootstrap, data-manifold などが提案されていました。これらの多くは分類器の精度(や再現率)を直接向上させるために教師無しデータを使っていました。

このstructural learningでは教師無しデータを、良い分類器ではなく、良い仮説空間を探すために使います。実際の議論はこのまま進むのですが、仮説空間とはなんだということで内容を具体的にすると、分類器は線形分類器(SVMやboostingを含む)を使うとすると、仮説空間を探すというよりは入力のfeature集合(重みもついている)から、より分類がうまく行えるようなfeature空間への写像(線形写像)を求めるということになります。

教師無しデータは正解が付いていないのですが、自明に正解が分かるような大量の補助問題を作り、それに対する精度がよくなるような仮説空間を求めます。この補助問題は実際に解きたい問題と相関があるようなものとします。例えば、実際に解きたいのが単語の品詞を求める問題の場合、補助問題は、ある位置にある単語は何かという問題となります(答えは自明に実際にそこに出現した単語を使う)。また、分類器が予測するのは何かというのを予測する補助問題も考えることができます。こうした補助問題の損失を同時に下げるような仮説空間を求めます(ポイントはこの仮説空間を求める部分がSVD:特異値分解でできるらしいのですがそこまでは理解できてません)。

こうして得られた仮説空間の中で実際に解きたい問題を学習、解くことになります。

似たようなことは考えたことはあるのですが、この論文では理論的な解析(補助問題数mがm→∞となった時、実際に良い仮説空間の推定ができる)や、具体的なアルゴリズムなどが示されています。そして、実際に精度が、教師付きデータのみを用いた場合と比べてかなりよくなっているということがCoNLL2003のshared task*等の結果で示されています。うまくいくのか・・

(CoNLL2003のshared taskは固有表現抽出で、大量の非教師データを使ってどこまで精度が上がるのかということが期待されたらしいですが、トップチームはみんなsupervised learningのみだったそうです。NISTの機械翻訳ワークショップでも同じような感じでしたね [link])

| | Comments (0) | TrackBack (0)

2006.01.24

Bayesian Sets

Bayesian Sets, Z. Ghahramani, K. A. Heller, NIPS 2005 [paper]
が面白い

Google Setsにインスパイヤされたと書かれている。これが扱っている問題は、複数のクエリを与えた時に、それが含まれているだろうクラス/コンセプト/クラスター集合の残りの要素を返すという問題。このペーパーでも書かれている通り、clustring on demand という言葉がぴったりだと思う。

このペーパーでは、その問題をきちんと確率モデルで定式化していて、それは効率的に解けて、結果も(たぶん)いい。

このペーパーを見てまだもやもやしているのは、supervised clustring とどう違うのかという点。ざっと読んでみた感じだと、従来のクラスタリングでは正解のクラスタリングが一つ存在していて、それを求めるのに対し、今回のやつはおなじ要素でもクエリーによって違うクラスターに分類されるという点(一組のパラメーターから生成されていない) かなぁ。

#(追記)後でよく読んでみたら、bayesian setは、てんで、supervised clusteringではありませんでした。

あと、今回はクエリ対象となる要素とそのfeature(とはいってなかったけど)が明示的に与えられていたけど、latent featureも仮定するとかなるとさらに面白くなりそう。シンプルさが失われてしまうかもだけど。

#(追加)これも後で考えてみたら、違う方向。できるとすればsetではなく、階層化中の位置とかかなぁ・・。

| | Comments (0) | TrackBack (0)

2005.12.16

feature種類数

今、実験をしているのだが、使っているfeature種類数がちょうど1000000だった。すごい衝撃をうけた。そんな年末ですよ。

| | Comments (0) | TrackBack (0)

2005.11.11

IBIS2005二日目

今日は午後から。

観測スパイク時系列に経験ベイズ推定を当てはめて解析。スパイクというのは脳内のニューロン同士がインパルス状の電気信号のことらしい。この話は初めてだったので新鮮だった。

次はセンサーネットの話。同一のものを複数のセンサがノイズ有で読み取り、それをそれぞれ独立に歪み有りでセンターに送る。センターはそれらのデータからから元のデータを推定し復元する。この時、通信量は一定であるという前提をおくと、センサの数を増やして圧縮率を高めて送るのがいいのか、センサの数を減らして圧縮率を低くして送ればいいのかを理論的(といっても構成可能)に解析。ノイズの具合によって最適なセンサ数が変わってくるという話。
今年のDCCでも複数の入力源からの歪有で送信の話があったような。

リスク回避型学習では、エラーのうち、大きなミスの上位x%のミスは避けてやるという話。具体的には期待ショートフォール(とバリュー・アット・リスクの二つ。個人的には選択を確率的に複数できるようなポートフォリオのケースが面白いなぁと。

Yair Weissさんによる招待講演。Belief Propagation (BP)の話。でも、まだBPよくわかってないので・・
BPは次のあたりを読んでおくとよいのでしょうか。
Understanding Belief Propagation and its Generalizations , Generalized Belief Propagation [link]
Map estimation via agreement on (hyper) trees [pdf]

| | Comments (0) | TrackBack (0)

2005.11.10

IBIS2005

IBIS2005に来てます。
機械学習の話。

午前の構造化データの機械学習は面白かった。

最初はグラフ構造からの頻出パターンのマイニング。gSpan,FGS,GASTON等の解説。やはり、ここがいいよという話。オランダは幾何強いなぁ。土地柄のせい?

次のグラフカーネルを使って化学化合物の分類では、Tanimoto係数参照が構造物の類似度として使われるということで、これでKernelを作ろうという話。グラフが与えられた時、最初に、グラフ中(化合物中)の各頂点から深さ優先探索で深さdまでのpath(フィンガープリント)をハッシュの初期値にして、そのハッシュ値のところが1になったbit配列を用意する。同じ部分構造を持つ場合、同じ場所に1がたっている。グラフX,Yのtanimotoカーネルは、これらから作られたbit配列x, yを使って (x & y) / (x | y) で高速に求められる。性能もいいらしい。

構造データのラベル付け学習モデルの設計では、普通のCRF(全損失から導出。全部のラベルがあっていないとだめ)とPoint-wise CRF(点損失から導出。それぞれのラベルがあっていればよい)の線形和を作ると、k次マルコフの損失関数を最小化するやつができるという話。不思議に思えたが、直感的な図を見たらすぐ理解できた。これをSemi-CRFの上に導入したら、k次Semi Markovができるのかなぁ。そんな単純じゃないのかなぁ

Mochihashiさんに、その後言語モデルや確率モデルの話を教えてもらいました。いろいろ謎だったことが解けました。どうもです。内側(入力側から)のモデルの豊かさに興味を持つ人と、外側(出力側)のモデルの豊かさに興味を持つ人という話が興味深い

| | Comments (3) | TrackBack (5)