« May 2006 | Main | July 2006 »

2006.06.30

夏の予定

が、大体決まってきました

7/10から9月はじめまでアメリカでインターンやってくる予定です。いろいろ学んできます。
(そのうち7/16-7/23はオーストラリアのシドニーでACL/COLINGとEMNLP行ってくる予定。)

その間の連絡はメールではとれると思います。

7月はじめには研究会、帰ってきた直後に修士中間発表とかもあったりします。
締め切りもあったりなかったり。準備をしっかりしないと。

いろいろな方々にご迷惑をおかけするかもしれません。よろしくお願いします。

| | Comments (1) | TrackBack (0)

2006.06.29

意識

朝までデバッグした後に寝て学校行き、会社飲み会。新しいメンバーも加わってだった。
泡盛を二杯一気に飲んだあたりで、聞き取れなくなりこれはまずいなと感じた。
人の話していることがすーっと遠くになっていく場合に、それから数分以内に意識がなくなる。この猶予時間の間に財布や携帯は手の届かないところに隠さないといけない。偉い人からも離れないといけない。で、今回もそれから数分後なくなった。柄杓?みたいのを取り上げたところまでは覚えているのだが。

後半は少し復活し、山や型や関数型やデータフローとかISっぽい話をした。
家に帰り、朝とれなかったバグをとり寝た。

| | Comments (0) | TrackBack (0)

2006.06.28

近況2

いろいろな予定が前倒しでぐつぐつしてます。研究や仕事やその他もろもろ一杯一杯です。

先日はガイド活動に参加してきました。カナダ人の方々が傘をささない主義(小雨が多いトロント地方やロンドンとかはささない人が多い)だったので、自分も頑張ってささなかったけど、ずぶぬれで、さした方がよかったねという共通見解でした。

また、この前は強行日程で、京都奈良行ってきました。大仏・鹿、見てきました。よかったです。
「奈良なら鹿しかいない」という名言も生まれました。

--
「行く手は荒野だぞ!」というフレーズが頭の中をリフレインしています。ある漫画で未来の自分が昔の自分に会いに行き警告を出す場面です。結局、未来の自分を言い負かしてしまうのですが。今が荒野なわけではないですけど、なんとなく奮い立たせる感じで。

全然関係ないですが、「二次元総裁」という惜しい言葉も良かったです。いそうです。

| | Comments (0) | TrackBack (0)

2006.06.15

近況

・毎日少なくとも5km走ることを決め夏に向け鍛えてます。のんだあともつらいですが走ってます。
・帰省して物置の移動を手伝いしたりしてました。30年ぶりに開けたサイダーは爆発し衝撃でせんぬきがとんでいきました。夜、やはり飼い猫に襲撃されました。
・W杯をやNBA finalを可能な限り見てます。幸せな時期です。
・積分やったりHessian行列求めたりしてます。一応自然言語処理です。
・いろいろな会社にいってデモしたり話伺ったり飲んだりしてます。今日もおじゃまし貴重な話を聞けました。とても参考になります。

| | Comments (2) | 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 (29)

2006.06.07

部分復元可能なデータ圧縮

通常の(可逆)データ圧縮は入力データを圧縮して保存し、それを利用する場合は、全て復元して元のデータに戻してから利用する。この場合、圧縮した後、データの一部分のみを利用したい場合においても、全てを復元してからでなければデータを利用できない。

これを解決する最も簡単な方法は、データを小さいブロックに分割してから、それぞれを独立して圧縮し、一部分だけ利用する場合は該当するブロックだけを復元することである。しかし、この方法では、ブロックが小さい場合、全体の情報が利用できず圧縮率は著しく低下する(1kBのデータを圧縮した場合と1MBのデータを圧縮した場合の圧縮率は数倍違う)。

この問題を解決するため、圧縮アルゴリズム自体に(高速な)部分復元操作を備えさせる方法ががいくつか提案されている。

Static PPM(pdf@dcc2004,pdf@comp-nhc2006)は圧縮に用いるためのモデルをPrefix Treeで表現し(Prefix Treeは各contextの次の文字の出現確率をコンパクトに表現する)圧縮したデータと一緒に保存する。入力データを小さいブロックに分けてそれぞれを独立に圧縮し、圧縮した後の位置を保存しておくところまでは最初に紹介した方法と同じだが、全体の情報を利用したモデルをどの位置でも利用できるのでブロックを小さくしても圧縮率は低下しない。例えばブロックサイズが4KB程度でも、bzip2などと同程度の圧縮率である。

Compressed Suffix ArraysやFM-indexなどの圧縮全文索引なども部分復元可能なデータ圧縮法としてみることもできる。これらは元々、任意のパターンを検索するための索引だが、元データを必要せず、また任意の位置から部分復元可能であることも知られている。この本質はBurrows Wheelers変換(bzipの復元を途中から行う)を利用していることである。詳細はfull-textのサーベイ(version 2できたて)を参照。

さらにこの考えを推し進めて連続するlog n bit(nは入力データ長)を定数時間で復元可能なデータ圧縮法が提案されている。これが意味するところはlog n bitのメモリを定数時間でアクセスできる計算モデルにおいては、アルゴリズム中のデータ参照をこのデータ圧縮を通じた参照に置き換えても計算量は変わらないということである。

"Squeezing Succinct Data Structures into Entropy Bounds", Sadakane and Grossi SODA 2006 はデータをLZ78法でパーシングしてフレーズ列に分解し、それぞれに番号をつけたものを保存する。フレーズ列はLZ-trieで保存する。このtrieは括弧列で表現された木で表現される。部分復元する場合はこのtrie上の対応するノードまでのパスを復元する。この操作はlookupテーブルを組み合わせることで定数時間で行える。これによりlog n bitの部分復元を定数時間で実現している。

一般の圧縮法を利用した方法も提案されている("Statistical Encoding of Succinct Data Structures.", Gonzalez and Navallo, CPM 2006 ps.gz)。これはStatic PPMとよく似ているが、この方法ではモデルは明示的に持たずに全てのlogn の復元表をテーブルで保存している(ただし、これを実現するためには、かなり入力長が大きくなければならない)

| | Comments (16) | TrackBack (0)

言語モデル

今日は研究室のミーティングで統計的言語モデルの話をしました。

確率的言語モデルは与えられた文(や文書)sに対して確率p(s)を与えるモデルで、より正しそうな文に対して高い確率を与えます(実際は与えるようにモデル化する)。パラメーターは大量の文(加工されていない文)を利用して推定します。
言語モデルは音声認識、統計的機械翻訳、文字認識、情報検索(クエリーと対象文書の言語モデルのKL-divergenceを測る)などに使われています。多くの問題では入力fに対して、その出力の自然言語文eを求める問題でp(e|f)が最大となるeを求めるのですが、このp(e|f)を変形してp(e|f)=p(f|e)p(e)/p(f) として、p(e)の部分で言語モデルを利用します(p(f)はeを選ぶ際には関係ない)

よく使われている言語モデルはn-gramと呼ばれるモデルです。文sが単語列 w1...wm からなる時、p(s)はp(s) = p(w1...wn) = p(w1)p(w2|w1)p(w3|w1w2)p(w4|w1..w3)...p(wm|w1...wm-1) と直前の単語列で条件付けされた単語の生成確率の積に分解できます。n-gramは直前の単語列をn-1単語で打ち切ったモデルで、例えば2-gram modelはp(w1)p(w2|w1)p(w3|w2)...p(wm|wm-1) となります。n-gramを最尤推定を用いて、各パラメータをp(w2|w1) = c(w1w2) / c(w1) と推定する場合、過学習を起こすので、より短い履歴を利用するなどしてスムージングを行います。

#最近、最も優れているスムージングの一つのKneser-Ney法の意味づけがPitman-Yor過程を用いた階層型ベイズ言語モデルからできるという論文が出ました。(link

他にも言語モデルはいろいろ提案されていて、直接パーシングを利用するもの (immediate head parsingを利用したものk)や、topicをベイズ統計の枠組みで捕らえたもの(言語処理年次大会チュートリアル)や、discriminativeなモデルを利用するもの(link)、決定木を組み合わせたもの(random forest)などがあります。

--
言語モデルはデータ圧縮とよく似ています。データ圧縮でも言語モデルと同様に与えられたデータd を最大の確率で表せるモデルを選び(学習)、そのモデルを用いてdを符号化します。この二つが使う理論的枠組みは同じですが、実用上は結構違います。

言語モデルは大量のデータを用いて巨大なモデルを作り、それを利用して未知の正しそうな文の確率が大きくなるようにします。モデル自体のサイズは関係ありません。

それに対し、データ圧縮ではこのモデル自体も復号時に必要となり、モデル自体と圧縮した後のデータの合計サイズが圧縮後のデータとなります。また、モデルの適用対象となるデータは、学習データそのものであり、モデルの記述サイズとのバランスを考えた上でぎりぎりまで過学習させた方がいいことになります。

データ圧縮ではこのモデルの記述量が無視できないため、大抵はモデルを符号/復号時に動的に構築するか(PPM法,LZ法)、モデルが短く記述できるようにデータを変換しています(BWT法は変換操作によってn-gram情報を位置情報に巧妙に変換しているとみることもできます)。

データ圧縮と学習理論の関係はmackay本が詳しいみたいです

| | Comments (23) | TrackBack (0)

« May 2006 | Main | July 2006 »