でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

AAAI2015一日目&二日目

f:id:yamaguchiyuto:20150127153004j:plain

AAAI2015に参加中(TASAは何なのか知らない)。1,2日目はワークショップとチュートリアルと招待講演があった。例のごとくワークショップはパスしていくつかチュートリアルと招待講演を聞いて回った。

いろいろ聞いた感じだと、AIコミュニティはホントにいろんな分野の融合になっていて、扱う範囲が広すぎると思った。自分は元々AIの人間ではないので、知らない単語とか分野がかなり合って、いろいろ知れただけでも参加してよかったと思った。レセプションで話した人たちもみんな結構バラバラの分野から来てて面白かった。

以下参加したチュートリアルと招待講演のメモ。

The Future of (Artificial) Intelligence - Stuart Russell

最近シンギュラリティやばいとかニュースで話題になったりしてるから、しょうがないそれに対して答えてやろうという招待講演。

色々例を挙げて話してたけど、メディア(?)への答えとしてはこれ。

  • response
    • it'll never happen
    • too late to stop
      • そんなことは起こらないと言いながらのこれ
    • can't control research
      • このセリフはカッコ良かった

あと、「お前ら勘違いしてるぜ」と言ってた。

  • misconception
    • machines have IQs
      • 尺度はたくさんあるしなんでIQ?
      • general intelligenceはまだまだ先
    • It's right around the corner
      • いや、breakthroughはunpredictableだから。
    • armies on robots
      • ないない。

良いAIを作る提案。

  • Proposal: provably "beneficial" AI

それにはこれが重要。

  • Value alignment
    • learn reward functions by other agents
    • 人へのrewardを学習するAI
    • values differ across individuals and contries

その他言ってたこと。

  • AI = making computers do the right thing
  • progress is accelerating
  • Once performance crosses the usability threshold, small improvements are worth billions

Constraint-Based Temporal Reasoning

時間の表し方と、そこからの推論についてのチュートリアル

時間の表し方には

  • qualitative
  • quantitative

の2つがある。例えば、

「朝食中に新聞を読んで、朝食の後にオフィスに歩いて向かった」

というのはqualitativeで、

「朝6時に起きて、その後朝食中に30分間新聞をよんで、朝食後にオフィスに向かった。8時にオフィスに着いた」

というのがquantitative。要するに、時間の表現の中に数値が出てくるかどうかの違い。qualitativeだと各事象の「前後関係」しか表せない。こういう 時間制約 をうまく表現する方法を考える。んで何らかの方法で表現したら、与えられた情報から推論することで、例えば以下の様なクエリに答える。

「オフィスについた時に新聞を呼んでいたか?」 「朝食を食べ始めた時刻のupper boundは?」

時間の表現方法についてはたくさん紹介してたんだけど、基礎的なところとしてはpoint algebraとinterval algebraっていうのが有名らしい。Interval algebraについては聞いたことあったかも。Point algebraは「朝食を食べ始めた時刻」見たいなTime pointの前後関係を代数的に表現する方法で、Interval algebraは「朝食を食べていた時間」の前後関係を代数的に表現する方法。これらはqualitativeな表現方法だけど、前後関係に数値を入れることでquantitativeに拡張していた。

その後はこういう時間関係にpreferenceを入れるとどうなるか見たいな話。例えば、

「火星探査機に火星の写真を取って分析してもらいたいからそのスケジューリングをする。もちろん分析するのは写真を取ったあとなんだけど、出来るだけ写真を取るタイミングは遅くしたい。どの時刻に写真を取って、どの時刻に分析を開始して、終了すればいいか。」

という問題を扱う。「写真を撮るタイミングを遅くしたい」みたいなのがpreference。事象の前後関係の制約を満たしたまま、preferenceを最大化(?)するにはどうしたらいいかっていう話だったんだけど細かいところはついていけなかった。

こんな分野全然知らなかったからすごく面白かった。たぶんAIコミュニティでもあんまりメジャーな分野じゃなかったみたいで、ものすごい基礎的な話から始まったのですごくわかりやすかった。

Voting Rules for AI

何かを決めるときの投票方法についてのチュートリアル

3部構成だった。

  • 1部:「選挙みたいに、いくつかの候補の中からひとつ選ぶときにどうしたら良いか」
  • 2部:「レストランのコースメニューみたいに、いくつかの要素が絡み合ってる場合どう選んだらいいか」
  • 3部:「マッチングの話」

1部

いくつかの候補の中からひとつ選ぶやりかたにも色々あるけど、それぞれ違う性質を持ってる。一般的に、voting ruleは以下の三つの性質を持っていることが望まれる。

  • anonymous: 全ての投票者は等しく扱われなくてはならない。つまり、ある二人の投票者の投票を入れ替えても、同じ結果になる。
  • neutral: 全ての候補は等しく扱われなくてはならない。つまり、候補Aに入った全ての票をBに変えて、候補Bに入った全ての票をAに変えると、AとBの結果が入れ替わる(Aが当選してたならBが当選するし、逆もまたしかり)。
  • monotone: 候補Aが当選していた時、Aの票を更に増やすことでAが落選してはいけない。また同様に、A以外の票を減らすことでAが落選してはいけない。

一番良く使われるのはもちろん「多数決」なんだけど、候補者が二人の時はMay's theoremによって多数決は上の三つの性質を持つことが示されている。

当たり前だろうが!と思うかもしれないけど、候補が3個以上ある時はそうも行かない。Arrow's theoremによって、候補が三つ以上ある(かついくつかの条件を満たす)時は、上記の三つの性質を全て満たすvoting ruleは存在しないことが示されている。

2部

こういう問題を考える。

「5人が夕食のメニューを考えている。メインはバジルペストパスタかトマトパスタのどちらか、ワインは白か赤かのどちらかから選びたい。それぞれの投票者はそれぞれ別の嗜好を持っている。どうやって決めたらいいか。」

ここで複雑なのは、単に「白か赤なら白がいいな」というものではなく、「基本的には白が好きだけど、トマトパスタなら赤がいいな。でもバジルペストパスタならやっぱり白がいいかな。」というように、それぞれの項目に依存関係がある。

こういうふうに、選ぶ対象が複数あって、かつそれぞれに依存関係がある時にどうやって選ぶかという問題。依存関係を全部考慮してたら組み合わせが爆発するので、いかに効率的に評価するかっていう話がされてた。

3部

Stable machingの話。

Gale-shapleyアルゴリズムでは、どちら側からプロポーズするかによってman optimalになるかwoman optimalになるかが変わる。man optimalってのは男性側の嗜好の観点からは最適なマッチング担ってるけど、女性側の嗜好の観点からはそうはなっていないということ。

面白いのが、man optimalの時(男性側からプロポーズする時)には、女性側が自分らの嗜好(どの男性が好みか)において嘘を着くことでより良いけっかを得られる。つまり、女性は正直に好みの男性を言わないほうが、好みの男性と結婚できる確率が高いということ。

大体wikipediaに載ってる話だったかな。

Natural Language Processing in Watson

IBMWATSONのチュートリアル

WATSONの仕組みからどういう応用をやっているかまで話してた。いままで何度か聞いてたけどまた聞きに来てしまった。

導入部では、既存の研究論文とか他人のコード(他のプロジェクトに使われていた)とかを自分のプロジェクトに適用するのはとても難しいから、IBMがやってるようなグランドチャレンジが重要なんだよと言ってた。

WATSONの仕組みについてはもう散々話されてるから他のソース(例えばこことか)に頼るとして、面白かった点を幾つか。

質問の型が大事

jeopardy!ではこういう問題文が出される。

「米国が外交関係を持たない世界の4カ国のうち、この国は最も北にある」

つまり、疑問文になってない。そのため、そもそも何が聞かれてるのかを知る必要がある。そこで、質問の型が重要になってくる。この場合の型は「国」で、問題文に整合する国を答えなくてはならない。

質問の型を導入した時とそうでない時で、精度が10%も変わったんだとか。

実際のアプローチとしては、単に型で限定してから答えを見つけ出すのではなく、いろんな候補解を列挙してから、型に合う答えにより大きなスコアを割り当てるというようにしてるらしい。これを"generate-and-type" principleと呼んでた。

Spatial and temporal reasoning

問題文には場所とか年代に関する記述が多く存在するため、それを手がかりにする必要がある。単純に「1980年」っていう記述が出てきたらそれでキーワードマッチすれば良いじゃんと思うかもしれないけど、「1980年で400周年となる○○」みたいな問題文を出されてしまうと、単純なキーワードマッチだとうまくいかない。○○に関する情報には「1980年」というキーワードはまず出てこないため。