音声ブラウザ専用。こちらより利用者別メニューへ移動可能です。クリックしてください。

音声ブラウザ専用。こちらよりメニューへ移動可能です。クリックしてください。

音声ブラウザ専用。こちらよりカテゴリ内メニューへ移動可能です。クリックしてください。

音声ブラウザ専用。こちらよりメインコンテンツへ移動可能です。クリックしてください。

慶應義塾大学理工学部
English
サイトマップ
KEIO NAVI
受験生の方
在学生の方
卒業生の方
企業・研究者の方
YAG@MIX(学内向)
概要
学部・大学院
教育・研究
教員プロフィール
関連リンク
交通アクセス
理工学部創立75年

理工学部HOME > 学問のすゝめ > 圧縮とマイニングと分析

学問のすゝめ

圧縮とマイニングと分析

櫻井 彰人 (管理工学科 教授)

ファイル圧縮と圧縮アルゴリズム
皆さんは、ファイル圧縮ということをご存じでしょうか。大きなファイルを、小さいUSBメモリに入れたりメールに添付したりするときに使います。ファイルを圧縮すると大きさが半分ぐらいから数分の1ぐらいになるので、便利です。また、Office2007以来、マイクロソフト社のOfficeソフトでは、ファイルを保存するときに自動的に圧縮しています。

圧縮する(そして、解凍してもとに戻す)基本原理は極めてシンプルです。例えば、0101…01 というように、01が500回繰り返す文字列を考えて下さい。全部で1000文字になります。しかし、「01を500回」と書けば、7文字で済みます。圧縮アルゴリズムは、このように、文字列の中にある規則性を発見し、それを上手に書き下すことによって、圧縮を行っているのです。

究極のデータ圧縮
では、究極の圧縮アルゴリズムというのはあるのでしょうか?コルモゴロフとチェイティンは、ほぼ同時期に独立に、そして、少し(いや大分か)違う形で、これを考えました。文字列xが与えられたとき、あるプログラム(これも文字列) y を考え、 y を動かしたときに出力される文字列が x であるようなもの(無限にあります)のうち、もっとも短いもの(文字数が少ないもの)を、文字列 x の圧縮文字列と考えることにしたのです。この x から y への写像は存在するのでしょうか? 文字列 x よりもほんの少し長いプログラムで x を印字することは簡単にできます。ですから、長さ1~「このプログラムの長さ」までの全部の文字列(有限個しかない)を実行して、 x を出力する最も短いプログラムを見つければよいので、この写像は存在します。

この究極圧縮プログラムはものすごく強力です。何しろ究極に圧縮するのですから、文字列 x に含まれるあらゆる規則性を考慮に入れ、最も圧縮に役立つものを見つけだしていることになります。つまり、 x を最短に圧縮したプログラム y をみれば、 x の性質は非常によく分かるということになります。例えば、ティコ・ブラーエの得た膨大な観測データから法則を得たケプラーと同様のことができるわけです。

言い換えれば、データ x から知識 y を取り出したと表現できます。

法則の発見
実はこのコンセプトに沿った行動は、人類はずっと行ってきています。太陽・月・惑星の運行から、それを説明する季節の移り変わりを予測し、神の意志を推定したこともあります。近世になっては、多くの実験データから、できるだけ短い・美しい理論(ニュートンやアインシュタインの式、先日放映された神の数式など)を帰納すれば、それが未知の現象を含むより多くのデータを説明する、予測することができることを知り、その手法を科学として確立してきました。

と、思いを馳せるとおかしなことに気が付きます。この究極圧縮プログラムが存在すれば、科学の偉大な発見が、データを集めるだけで可能になってしまうことになります。この究極圧縮プログラムは、夢のような道具ですが、実は、まさに夢なのです。計算論的には計算不能なのです。つまり、我々はそれをアルゴリズムに書き下すことはできないのです。残念です。

機械学習
もっとも、近似することはできるし、分野を限ればよりよい近似が得られます。それが我々の研究分野である「機械学習」が行っていることです。データから知識を得る道具に関する研究です。データマイニングともいいます。最近流行りのビッグデータの分析にも関わります。機械学習の研究では、通常は、汎用的な究極圧縮プログラムはコンセプトにとどめ、実際には、データに潜むある特定の型(例えば、一次式)で記述できる規則性を探しだす、よい方法を探しています。

勿論、究極圧縮プログラムの近似を用いた研究もあります。この稿の最初に出てきた圧縮プログラムを用いた機械学習の研究です。普通の圧縮プログラムは、単に文字列の出現頻度の偏りを用いるだけですので、究極圧縮プログラムに比べれば、おもちゃにすぎません。それでも、例えば、文書分類(スパムメールの検出、聞きたいニュースだけの選択など)は、ベストな分類方法に少し劣る程度の精度でできます。変わったところでは、圧縮プログラムを用いて楽譜間の距離を計算し、ショパンとドビュッシーの曲を分けた研究があります。

圧縮プログラムは一次元列を圧縮するものですから、例えば、2次元である画像に適用しても、圧縮性能はあまりよくありません。つまり、役に立つような規則性の抽出はできません。例えば、写っている対象(飛行機、ライオン、建物等)に拠って画像を分類するといったときに、発見したい対象物の像に存在する規則性の抽出は難しいのです。これは、次元の違いという本質的な困難さともに、画像に存在するノイズ・歪・類似性・多義性等の、現実データの特性に起因する困難さが原因となっています。それでも、画像の「特徴量」の抽出・記述に工夫を加えることにより、ベストな認識方法の半分以上の性能が出せるようになりました。

機械学習の重要な道具の一つにニューラルネットワークというものがあります。ニューラルネットワークの学習方法の中に、無理やりデータ圧縮をさせる方法があります。最近、このデータ圧縮方法を多段に組み合わせることにより、画像分類に適した、画像の「特徴量」(画像を記述するときに使う、頂点とか面とかといった基本的な「単語」)を自動的に発見する方法が発見され、盛んに研究されています。Deep learning と呼ばれる方法です。

終わりに
このように、データ圧縮、規則性発見、知識発見、機械学習、データマイニング等の間には、共通の基盤があります。実は、哲学的にも面白い話題がありますが、説明するには少々スペースが足りません。興味がある方は、例えば、「オッカムの剃刀」を調べてみることをお勧めします。

ここ1~2年データの重要性、そしてそれを分析する必要性が認知されるようになりました。自然に存在するデータはもとより、人間活動が生み出すデータにもさまざまな特徴があり、適切に分析すれば様々な知見、例えば、人間の本能的な行動を勘案した避難経路の設計、商品の適切な配置に基づく販売促進など、適切な行動への指針が得られます。分析手法も次々に開発され、どんどん発展しています。

データ分析から入るのもよし、オッカムの剃刀から入るのもよし、計算論から入るのもよし、みなさん、一緒に考えてみませんか?

↑PAGE TOP