ダウンロード - Researchmap

ビッグデータ高速処理に向けた
計算理論的アプローチ
宇野 毅明 (国立情報学研究所
,総合研究大学院大学)
2012年6月
「宇野の技は、大規模データでの計算の高速化です 」
「特に、類似検索、パターン発見、最適化など」
国立情報学研究所 宇野 毅明
東工大、情報科学卒: 東工大経営工学  現職
専門分野: アルゴリズム理論 (計算量&実利用)
計算方法の改良による高速化の研究。
データ規模増加に対する計算時間の増加カーブを改善
大規模データに対する、基礎的な情報処理に取り組む
頻出パターン、類似性解析、クラスタリング、可視化、最短
路・・・、などに使われる基礎計算
データベース
100万項目
10000倍
実験1 実験2 実験3 実験4
●
▲
▲
●
▲
●
●
▲
●
●
●
▲
●
▲
●
●
●
▲
●
●
▲
▲
▲
▲
実験結果
ATGCGCCGTA
TAGCGGGTGG
TTCGCGTTAG
GGATATAAAT
GCGCCAAATA
ATAATGTATTA
TTGAAGGGCG
ACAGTCTCTCA
ATAAGCGGCT
ゲノム情報
自己紹介: 理論向け
研究分野: アルゴリズム理論とその応用
+ グラフアルゴリズムを中心とした離散アルゴリズム
+ 組合せ最適化とそれにまつわる数理
+ 列挙アルゴリズムと、頻出パターンマイニングへの応用
得意なところ:
+ 2分木やリストを使ったデータ構造の工夫による高速化
+ 列挙アルゴリズムの高速化
+ NP完全性の証明
+ (グラフクラスに対する)動的計画法の設計
最近の研究: ゲノム情報学やデータマイングで出てくる巨大なデー
タベースの基礎的(とはいっても非常に時間のかかる)な解析を超
高速で行うアルゴリズムの開発
アルゴリズム技術的には
• どういう問題を解くか、が問題
(検索、索引付け、認識、学習… 基礎的なことは意外と速くできる)
• データ自体は商品ではない。解法・アルゴリズムも商品ではない
商品は「モデル」かもしれない。
企業価値は「モデル力(もでるりょく)」 かもしれない
• アルゴリズム技術については、「何が出来るのか」を知ること
• ビッグデータならではの「モデル」に有効な計算技術は何か
何を計算したらいいのか。どれくらい正確/有効/速いのか
ビッグデータ
• 最近、センサ類の発達により、随所で「ビッグデータ」を見るよう
になった
• ビッグデータ、メリットもたくさんあるが、同時に難しいところも沢
山ある
 特に「計算できない」「扱いきれない」という話は良く聞く
• まずは「モデル化と計算」の面から見た、ビッグデータの難しさを
見てみましょう
サンプリング
• データの中から、(ランダムに)一部を取り出して評価することを
「サンプリング」といいます。
• ほんとにデータが大きいのが困るだけなら、サンプリングして小
さくすればいい
 インターネットのパケットを分析するときなど、使われている
• でも、みんなそうしないのは、理由があるから
 見たいものの一部だけしか見れない(個人の行動履歴など)
 重要なものを落とすかも
• もう少し詳しく見てみましょう
ビッグデータでの「困難」
• ビッグデータの難しさ/利点をモデル&計算の面から見る
モデル: ノイズ、多様性、初歩的、不整合、、、
計算 : 計算時間、メモリ/ディスク、逐次計算(オンライン)
動的な変化とリアルタイム性、、、
• 確かに厳しそうだが、逆にメリットもある
モデル: 多様性、初歩的、多量、リアルタイム、、、
計算 : 疎性、類似性、ある種の単一性、、、
• うまく使いこなせば、きっといいことができる
もう少し詳しく
• ノイズ
単に精度が低いだけでなく、データに欠落がある。また、うそも
混ざっている。
• 不整合
集められたデータの生成目的が異なるため、粒度が異なる
• 初歩的
単にセンサーから取ってきたデータなど、それだけでは役に立
たないものが多い
• 疎性
次数やアイテム数が平均的に小さく、データがすかすか
• 多様性
データの項目が多量の(重なりを持つ)グループを含む。その
ため、局所的な密構造を持つ
なぜこうなるか
• なぜこういうデータを作る/使うはめになっているのだろうか
• それは、「集めたもので」「多くの人に」「(再)利用される」から
 目的にあったデータの収集デバイスを設計すれば、
このようなことにはならない
• 逆に言えば、「データ収集デバイス」を作らなくていいのがミソ
ここに関する(非常に高い)コストを削減できる
• さらにつきつめれば「手に入るデータで何かいいことをしよう」
となる。このアプローチはビッグデータの基本
そうなると
• とりあえず、出口的な話は置いておきます。
(個人個人でやりたいことが違うので)
• ビッグデータに使える、共通基盤の様な技術は何か、考えます
• 個別の問題を作り込んでも、他の人/他の問題では使えない
 ある程度、いろいろな問題に共通した問題を解くべき
 応用が利くようにするためには、単純な問題であるべき
 使いやすさのため、入力が単純で、出力が明解であるべき
 なるべく高速&省メモリであるべき
 解が頑強で、入力の変動に安定的であるべき
長所もある
• こうなると、「大変だな」と思うが、
逆にデータが大きいことによるメリットもある
+ データが大きいので、簡単なモデルでも精度があがる
+ 小さいデータでは見つかりにくい、少数派や例外が
比較的簡単に見つかる
• 大変だな、と思っていても、そうでもない面もある
+ データは巨大だが、局所的なまとまりを持つ
+ すかすかであることが多い
• データが大きくなると精度が上がるもの、そうでないものがある
+ 因果関係は、変数が増えても候補が増えるだけ
小さいデータでちょっとずつ比較
• ゲノムの比較。小さいデータで文字だけ見ると大変
人X:GCAAAATTATCCTTGAGTTCAGAGTCAGAATTGATTCA
GATATTAAGGAAATTATGAAACTTTAAGTTCCATATTAAGAAA
ATTAAAACATTCTATAATGATTTCATTTAAGGTTACTATGACAT
AAAAAGTTTCGTAGCTTTTAATTAAGCACACATTTATAATAAT
AGTTGTTATTTTAGGTAATATCAGGGTGTTGTAAAAGAATTG
マウスX:
GCCCTATCCCCTCTGGGCTCCATTTTCTAGTCTACAA
CTCTAACTACAACCCCAAGCACCTGGAGCCAGAGACCACCAG
GTGAGACCCTTTCCTCAAATCCCTGCCTGCCAACCTCTCTGG
GTAAACTCAGTGGCAATAGCTCTGACCTGCCCACTCTGTATTA
CATTGCAAGCTACAACTTCCCCTAATTCTCTGGAGACCTGAA
データを大規模にして可視化
Mouse X chr.
マウスXとヒトX
染色体の比較
PCで15分
Note:
BLASTZ で2週間
MURASAKI
だと 2-3 時間
ただし誤差が1%
だそうです。
Human X chr
(両者1.5億文字)
類似性がよく見
えるようになった
少数派がたくさん集まるデータ
• データに多様性があるとは、グループがたくさんあるということ
(グループを持たない多様性はそれほど見かけないし、
ある種分析しても面白くない)
巨大だから見つけられる
• データが沢山あれば、小さなグループでも浮き上がらせられる
• サンプリングすると、これらのグループは見えなくなってしまう
これがたぶん、ビッグデータをサンプリングしたくない理由、ビッグ
データは多様性と局所性が大事な理由の一つ
全体の可視化は難しい
• 多様性があり、グループが多いと、可視化してもぐちゃぐちゃ
(ゲノムは多様性がなかった!)
• 可視化するなら、局所を浮かび上がらせるような方法が重要
可視化に限らず、全体から局所へ行くようなアプローチは遠回り
局所ならボトムアップで
• 全体/大域的にアプローチすると、うまく局所が見つけられない
 2つ2つと分割して、一つ一つのグループは見つけられない
• 直接、局所的なグループをモデル化するアプローチが良い
大きなものに隠される
• 大域的な構造からアプローチすると、少数派は隠れてしまう
• 大きな構造に半ば含まれるように存在する、小さな構造を見つけ
出すのが難しいポイント
• 各項目が2つ以上の顔を持ちうる(複数のグループに属する)こ
とをモデル化する必要がある (項目の多様性)
• 局所的に際立つもの、をたくさん見つけることで多少対応できる
ビッグデータのジェネラリスト
• (基礎モデルと計算の面から)「ビッグデータに強い人」に
なるのであれば、
+ 局所的な構造を、大域的なモデルを使わずに見つけ出す
+ 個々のデータ(項目)ごとの多様性も考慮し、単純に扱わない
+ 背景知識や特別な性質をなるべく使わず、
データの基本的な性質(類似性、頻出性など)だけに注目
+ モデルは単純でよいので、スケールする方法を使う
ただし、巨大化すると精度が上がるメカニズムがあること
• こんな心がけを持って向き合うと良いかと思います
情報爆発とビッグデータ
+ 情報爆発
 巨大なデータ
+ ビッグデータ  巨大なデータ
・・・ 同じものに見えますか?
• 両者共に巨大なデータですが、取り組む内容は違うと思います
情報爆発: 巨大なデータをどう扱うか、どうためるか、の技術
ビッグデータ: 巨大なデータの中でも、以前とは異なるアプローチ
を要求するものたち。と、それを使いこなす技術
• データが実際に出てきて、使えるようになったら、多様性とか局
所性とか、難しいものがたくさんでてきた。どういうモデル(問題設
定)を考えて、どう利用しようか、というデータの学問
データの博物学
・・・ ということは、生物学のように「こういうデータがありました。性
質はこうで、こういうことができます」という研究があり?
 実際にWebの会議ではこういうのが多い
(SNS, twitter, flicker, 知恵袋, … 2ちゃん?)
• 博物学だけだと手法がアドホックになり、きりがないので、
手法はある程度「一般的な」ものを、データに基づいて作りたい
• 「何でもOK」 ではなく、データの本質に基づいて設計して、
「データがこういう性質を持つなら高性能」とする
• 「手法のメカニズム」を明らかにして、それがデータの性質とどう
関連しているかを調べる
小さいデータのとき
• データが小さければ、人間がデータを直接観察・分析できる
(人間の能力はすばらしい!)
• それを機械でなんとかしようとするのが機械学習
人間の
観察・解析
データ
人間の
観察・解析
知識
少し難しいとき
• 人間の分析を機械でなんとかしようとするのが機械学習
• 人間の判断を助けるのが可視化
• 人間にネタを提供するのがマイニング
マイニング
知識
データ
可視化
機械学習
ビッグデータだと
• 機械学習: 特徴が多すぎて、何が本質かわからない
• 可視化: データが大きすぎてぐちゃぐちゃ
• マイニング: 現実から遠すぎるものが出てくる。しかも大量に
現実から遠すぎ
マイニング
知識
巨大・多様な
データ
可視化
機械学習
ぐちゃぐちゃ
因果関係が
見えない
どういう風にアプローチするか
• どのステップも距離が離れすぎているのではないか
 ならば、近距離移動を主体とするように設計しよう
マイニング
機械学習
知識
巨大・多様な
データ
可視化
• 距離が近くなれば「意味不明」「ぐちゃぐちゃ」が減るだろう
• ただし、マイニングするものが「単純」でないと利用が難しい
感覚的には
• 自然言語解析をする前に、「形態素解析」をするのに似ている
• 可視化でも、画像処理でも、こういう流れがすでにある
マイニング
機械学習
知識
巨大・多様な
データ
可視化
• 今後はきっと、「もっと使いやすい何か」をうまく定義して、
「それを効率よく見つける技術」が重要になるだろう
だめな未来
• ただし、なるべく広い問題に取り組まないといけない
 細かい研究をしすぎると、道のりがぐちゃぐちゃになる
知識
巨大・多様な
データ
• 経由地を把握するのが大変になる
• 経由の数も種類も、増えすぎないように注意
テーマ: クラスタマイニング
クラスタマイニング
• クラスタマイニング = クラスタを見つけ出すこと
• でも、既存研究では最適化的アプローチ(もっともらしい
クラスタを見つける)というアプローチが多い
• ビッグデータ的には、「マイニング的」、つまり「クラスタである可
能性のあるものをどんどん出す」という方法がいいだろう
• 実際に使うときには、その中からいい物を選んだり、マージしたり、
有望そうなものを拡張/削減したりすれば良い
クラスタマイニングの難しさ
• 1つは、解の爆発をどうさけるか (極大クリークなど、基本的なも
のはノイジーなグラフには大量に存在する)
 単純性を保ちながら数を減らすのが難しい
• 計算時間をどう削減するか(1つ見つけるのが非常に短時間で
ないといけない)
• 意味のあるクラスタをどう見つけるか
クラスタに意味は必要か?
意味のあるクラスタをどう見つけるか
 果たしてクラスタに、人間がわかるような理由付けは必要か
• 人間に分かる理由を付けるためには、知識が必要
 手法・モデルの一般性が無くなる
• そもそも、人間に理由が分からないグループだってある
(ネットのコミュニティーは現実世界を見ただけでは分からない)
• だったら、「機械にわかりやすい」 = 「定義しやすい、手続きしや
すい」 クラスタを定義するのがいいだろう!
極大クリーク
• 似たものの間に線を引いて、グラフを作る
 同じグループに属するものは、線で結ばれているだろう
(こういう頂点の集合を
という)
• 他のクリークに含まれない、極大なクリークを見つければ、グ
ループが見つけられるだろう
問題 与えられたグラフの極大クリークを全て列挙せよ
極大クリークマイニングの特徴
• 極大クリークは、クラスタのモデルとしてはもっとも基礎的
• 一個見つけるのに最悪 O(n2) 時間かかるが実際は速い
• 全列挙も、いいアルゴリズムが複数あるので、実時間でできる
 「解の数が巨大でないこと」が条件。1秒1万個くらい
• 隠れた少数派も、たぶん、きちんと見つかる
(大きいものに含まれていなければ)
• 乱れたグラフだと、大量の極大クリークが出てくる(Webなど)
• どうやって数を減らすかを考えなければ
モデルを考えるか?
違う手を考えるか?
データクリーニング的なアプローチ
• モデルの研究は沢山ある。がんばると単純性がなくなる
逆に言えば、がんばらないと数が減らない
• データクリーニング的に、「必ずここはこうしていいだろう」という
変換を加えてノイズを減らし、数を減らしたい
• あまり高度なことをしたくない。データに基づいた、単純な仕掛け
のクリーニングだけをしたい
グラフのクリーニング
• 積極的に不利な構造をグラフから取り除くと、より局所をはっきりさ
せられる (小さなクリークにしか含まれない枝は消していい)
-A と B 両方に隣接する頂点が多数あるなら、AB 間に枝をはる
★ クリークの枝欠損がなくなる
-A と B 両方に隣接する頂点が少しなら、AB 間の枝を切る
▲ 近いクリークを結ぶ枝が無くなる
クリーク
• 極大クリークの数が非常に小さい
グラフができるものと期待される
クリ
ーク
クリ
ーク
計算実験:Webリンクデータ
• 日本のWebリンクデータ (from 東大喜連川研究室)
- ノード数 550万、枝数1300万 (サイト単位に加工済み)
• Web はデータが大きいために、手法にある程度流れがある
+ データ全体を簡単な手法で解析
((k)連結成分、強連結成分、ページランク、最大流、、)
+ データをしぼって深い解析
(評判分析、リンク予測、、、)
(Webテキストマイニングは、リンク解析ではない)
• クリークを列挙して、コミュニティーを見つける研究もある
(が、解の多さが問題)
計算実験1:Webリンクデータ
• クラスタリングしようと思って極大クリークを列挙すると、
数が大きすぎて列挙できない
 リンク先の類似性でデータを作り直してみる
• 20個以上のリンク先を共有するものを「似ている」とし、大きさ
20以上の極大クリークを列挙
 極大クリーク数が約 8000個に減少!
ほとんどがスパムのグループ、、、
• 計算時間はおよそ10分(大きさ2の頻出集合を見つけているの
と等価)。実用に十分耐えうる
解の分布
• 通常のパターンマイニング(極大クリーク列挙)では、解が大
きくなるにつれ指数的にその数が増える
• 本手法の場合、非常に緩やかに解数が増加し、さらに非常に
大きな解がぽつぽつと見つかる
 大きな解を見つけるために要する時間は格段に短い
 非自明な解を見つけやすい???
極大クリーク数
• ある程度、情報をアブストラクト
することに成功しているのだろう
解の大きさ
なぜうまくいくのか考える
• データを100%信じず、有るべき姿にちゃんと変えてあげた方が
いいんじゃないか、という発想の転換がある
• グラフを変えることで、多くの類似クラスタがまとまっている
つまり、解の爆発を防いでいる
 ひょっとしたら、必要なものも埋もれているかも
しれないが、現実的には考えづらい
• モデル自体はクリークなので単純。理解しやすい
• 道具も重要。列挙が高速で出来るのはポイント。いい道具が使
えるモデルを選んでいる
事例: あいまい文字列検索
頻出文字列
• (巨大な)文字列データから、頻出する文字列を見つけたい
(頻出する=あちこちに現れる)
• suffix array やradix sort などで、ほぼ線形時間で、多数現れ
る部分文字列は見つけられる (閾値以上の回数現れる者の中
で極大なもの、といった設定もOK)
• しかし、アイテムセットのように、「現れる」ことが包含関係で表
されているものに比べると、自由度が低い
( = きっちりと全体が現れるものしか見つけられない)
• ゲノムなどエラーのあるデータ、ひな形や定型文書のような
一部変化するデータでは、今ひとつ
あいまい性の導入
• エラーや、部分的な変化に対応するには、厳密に一致する文
字列だけでなく、曖昧マッチングの意味であちこちに現れる文字
列を見つける必要がある
• 曖昧性の尺度は、ハミング距離、編集距離、固定回数のギャ
ップ、マルチプルアラインメントのスコアが小さい、など
• しかし、こうすると、短い頻出文字列がたくさん存在してしまう
• いくら高速なアルゴリズムを作っても、これらを全部列挙する
のは無理だし、そもそも見つけてもうれしくない
• 困った困った、ので、違うアプローチを考える
不都合をたっぷり享受
• あいまい頻出文字列問題は、パターンマイニングの負の側面
をたっぷりと享受している
 解数の爆発、 解の類似・冗長性、 無意味な解の氾濫
簡単に解決
• データの巨大性をいかして、単純に攻めてみよう
• 似てる文字列は、必ず似ている(短い)部分列を含む
 頻出する文字列は、頻出する短い文字列を含む
 それを見つけ、芯にして長いのを見つけよう
• 頻出する短い文字列を直接見つけるのは難しい
 短くて、似ている文字列の「組」を見つける
 類似文字列の組が、類似グラフを作る
• 頻出する短い文字列は、そのグラフのクラスタから得られる
スタークラスタリングを利用
① 最も似ている物が多いもの S を見つける
② S と似ている物を全て集める ( S1,…,Sm)
③ それらをそろえて並べ、文字が共通している部分を抜き出す
次に進む
• 一番良く現れる物について頻出文字列を見つけたら、次に「2番
目に良く現れる文字列」について同じことをする
• ただし、頻出文字列を見つけるときに使った文字列の部分列で、
「見つけた頻出文字列」の一部になっているものは「もう使ったよ
う」という意味を込めて消去
• どんどん候補が消されるので、それほど多くの解は見つからない
• 仕組みが単純で、計算も速い
• それなりに似通っていない解が見つかる
類似する部分列の発見 (sachica)
問題: 各項目が同じ長さ l の短い文字列(50文字程度)であるデー
タベースを入力したときに、文字列のペアで異なり数(ハミング距離
)が d 文字以下である組を全て見つけよ
• 2分探索で見つけられないので、索引付けが難しい
• 部分一致で探索すると速くなるが、精度を上げると速度が落ちる
• 実際には、複数分類法で高速に解ける
ATGCCGCG
GCGTGTAC
GCCTCTAT
TGCGTTTC
TGTAATGA
...
• ATGCCGCG と AAGCCGCC
• GCCTCTAT と GCTTCTAA
• TGTAATGA と GGTAATGG
...
基本のアイディア:文字列の分割
• 各文字列を、k(>d) 個のブロックに分割する
• k-d 個のブロックの場所を指定したときに、そこがまったく等しく
て、かつハミング距離がd 以下となるようなペアを全て見つけよ、
という部分問題を考える
 各文字列の k-d 個のブロックをつなげてキーにし、ソートをす
る。同じものはグループになる。それを総当りで比較すればよい
• k-d 個のグループ数が大きければ、平均的にグループのメン
バー数は小さくなるので、総当りで比較してもたいしたことない
計算結果
• マウス13番染色体 Genic1 での実験結果(150万文字)。長さ30異
なり数2、多数決の閾値は 70%。10回以上現れるもののみ注目
#T#GCAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTTATGATATCTGA
#TTGCAAAGGCTTTACCACATTGATTACATTCATAAGGTTT#TCTCCAGTATGG#TTCTTTTATGATATCTGA
GAC#A#TGTGACAGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT
GATTACTGTGA#AGGAAAAGGCTTTACCACATTGATTACATTCATAAGGTTTCTCTCCAGTATGGGTTCTTTT
#TGATATCTGAGACTA#TGTGACAGGAAAAGGCTTT#CCACATTGATTACATTCATAAGGTTTCTCTCCAGTA
ATGA#ATTGGAGAT#A
TGGGTTCTTTTATGATAT#TGAGAC#A
#TCTCTGAA#AAAGAAAT#AAAGAAGATCTCAGAAGATGGAAAGATCTCCCATGCTCAT#GATTGGCAGGATC
AATATAGTAAAAATGGCTATCTTGCCAAAAGCAATCTACAGATTCAATGCAATCCCCATCAAAAT#CCAACT#
AATTCTTCA
• # は多数決が決まらない場所、計算時間は10秒ほど
• 実際、多くの回数(20-30回)現れている
計算結果 日本語テキスト
•日本語テキスト100万文字、 20文字中異なり4、次数(頻出度)10
#組の成立となりました。## #月1#日(土)男性12名:女性1#名のご参
加で、5組の成立となりました。## 4月7日(土)男性#0名:女性#
##,###円(税別、送料別)Paul Smith Men’s/ポールスミス メンズ
サイズフェイス:H約4.5cm×W約3.#cm、厚み約#.#cm(リューズ除
く)ベルト:幅約2.#cm腕まわり:最大約###
#年0#月200#年0#月2006年0#月2006年0#月2006年0#月2006
年0#月2006年0#月200#年0#月200#年12月2005年…
• 解は29個。ゲノムより感度が落ちるので、少し低い頻出度、大き
な異なり数で行うといいようです。
調子に乗って
• 調子に乗って、さらに大きな問題を解いてみました。
- 日本語Webテキスト 500MB(2.5億文字程度)
- 頻出度10 長さ20、異なり2
• 計算時間30分ほどで、頻出文字列が6000個ほど。使用メモリは
600MBほど (入力データの1.3倍ほど)
• ほとんどはなんらかのテンプレートで、完全に一致しているようだ
• ときどき、日付などのゆらぎを吸収したパターンが見つかる
• 異なり数を4にすると2時間。ちょっと大きな異なりも見つける
#####[アウトレットセール]メーカー販売価格#,##0円(税込)acc
aplus特価#,##0円(税込)#
なぜうまくいくか考える
• モデルを複雑にする必要はない、データが勝手に精度を上げてく
れる。簡単な問題を解けばいい (ここが発想の転換)
• モデルを作るときに、「いい計算方法を使う」のがポイント
また、構造が簡単なモデルであることが、理解しやすさから重要
• 解が爆発しないように、かなり乱暴に、すでに使ったところを消し
ている。ひょっとしたら、何か見逃しているかもしれない
(ゲノムの場合は、あまりなさそうだが、、、)
 そこは、他の解析方法を使った方がいいかもしれない
、 マジョリティに埋もれたマイノリティを見つける方法とか
まとめ
• ビッグデータ: データの性質を調べ、利用する科学
• 巨大さと多様性に対応する: 単純、頑強、ボトムアップなモデル
• データのある程度不変な質を利用した計算手法
• クラスタマイニング: 重なりを許し、ボトムアップにクラスタをマイ
ニング。数を明解な方法で減らすのがミソ
• 頻出文字列: データの巨大さを逆手に取った、簡単で効果的な
高速計算手法
• 今後は、よりいい構造を見つけ、可視化、機械学習の意味づけ
を容易にする方向を目指すことが大事になるだろう
情報研の取り組み
情報研でも、所を上げてビッグデータに取り組み始めています。
• 他大学と連携してのCPSプロジェクト
• ビッグデータに対するアルゴリズムプロジェクト
(ロボットは東大に入れるか、人工頭脳プロジェクト)
これからの情報研は
ビッグデータだ!
• お気軽にお声をおかけ下さい
アブストラクト
近年の Big data ブームでは、その解析や利用にともなう計算コス
トの高さが問題視されている。アルゴリズム改良はインフラに対す
る投資が不要な上、場合によっては非常に大きな改善が見込ま
れるため、重要性が高い。本講演では、このような計算理論から
大規模データ処理の問題解決に対してアプローチするための、基
礎的な考え方についてレクチャーする。理論を身につけることは困
難であるが、理論からアプローチできる領域や、理論によるアプ
ローチの方向性を知り、具体的にどのようなことがどの程度の
コストで的そうかを見積もることならば、その感覚をつかむことは
難しくない。本講演では、具体的な事例を交え、基礎的な物の見
方を学ぶことを目標とする。