Amazonの中の話はあまりWeb上で見たことがなかったので興味深く読めた。
会社の方針は、ジェフ・ベゾスの意思を強く反映している感じ。 ジェフ・ベゾスは顧客のことを第一に考えていて、それを背景にして社員の福利厚生はかなり貧しい感じ。 例えば、社員にバスが動いている時間に帰ってほしくないから、という理由でバスの定期を買う際の補助金を却下しているらしい。 また、長期的なメリットを考えて、短期的な利益は考えずに赤字覚悟で商品の価格を引き下げたりしている。 これで競合他社が立ち入る隙を見せないようにしている。すごい。。 いちAmazonユーザからすると、なんて顧客のことを考えてくれる会社なんだろうと思う。
誰かを雇ったら、その人を基準に次はもっと優れた人を雇うようにすると言った、Googleなどの話でも聞いたようなことをやっていて、 人材はどの企業でも大事なんだなあと改めて思った (小並感)。
ジェフ・ベゾス個人の話も書いてあった。 仕事では冷徹で、鬼のような怖さだけど、家族には優しい一面ものぞかせいている。
A9がたまに学会のスポンサーとかで見かけていて、Amazonのにっこりマークが付いていてどういう関係なんだろうと思っていたが、A9はAmazonの技術系の子会社だということもこの本で知った。 あと、もともと本を始めとする小売業のようなことをやっていたのに、どのようにAmazon Web Serviceを提供するに至ったかの話も書いてあって面白かった。
個人的には、部門間の調整が難しいという大企業ならではの問題をなんとかしたいと思った中間管理職のチームが、部門間の対話を推進する仕組みを提案した時にジェフ・ベゾスが言った以下の言葉が印象に残った。
「言いたいことはわかるが、それは大まちがいだ。コミュニケーションは機能不全の印なんだ。緊密で有機的につながる仕事ができないから、関係者のコミュニケーションが必要になる。部署間のコミュニケーションを増やす方法ではなく、減らす方法を探すべきだ。」
エッセイの一部をメモ。
主張をまとめると「自然言語の機械的な理解には、大規模なデータ、性能の良い機械学習も重要だけど、言語の構造をしっかり考えることも大事」。
Introduction Machine Comprehension of Text (MCT) (テキストの機械的理解) は人工知能のゴールである このゴールを達成したかどうかを確かめるために、研究者はよくチューリングテストを思い浮かべるが、Levesque (2013)が指摘するように、これは機械を知的に向かわせる、というよりは人間の知能を下げるほうに作業者を差し向けてしまう ※ チューリングテストとは、ある人間から見て、二人の対話のどちらが人間かどうか判別するテスト Levesqueはまた、チューリングテストよりも、世界知識を必要とするような選択肢が複数ある問題のほうが適しているとも主張している このエッセイでは、MCTは、“ネイティブスピーカーの大半が正しく答えられる質問に対して機械が答えた回答が、ネイティブスピーカーが納得できるものであり、かつ関連していない情報を含んでいなければ、その機械はテキストを理解しているもの"とする (つまり質問応答) このエッセイのゴールは、テキストの機械的理解という問題に何が必要なのかを観察することである How To Measure Progress 複数の選択肢がある質問応答のデータセットをクラウドソーシングを利用して作った 7歳の子供が読めるレベルのフィクションの短いストーリー Winograd Schema Test proposal (Levesque, 2013) は、質問と回答のペアは世界知識を要求するように注意深く設計されているので、生成には専門知識を要する質問を使うことを提案している “それは紙で出来ているので、ボールはテーブルから落ちた"の"それ"は何を指しているか？ クラウドソーシングなのでスケーラビリティもある 進捗が早ければ、問題の難易度を上げることもできる 語彙数を現状の8000から増やす ノンフィクションなストーリーを混ぜる タスクの定義を変える 正解が1つ以上、あるいは正解が1つもない問題など 回答の根拠を出力するようにする 興味深いことは、ランダムな回答をするベースラインでは25%が正しい回答を得られる一方で、単純な単語ベースな手法が60%で、最近のモダンな含意認識システムを使っても60%くらいであることである Desiderata and some Recent Work machine comprehensionに必要なものは、興味深い未解決な問題と通じている
意味の表現は二つの意味でスケーラブルであるべきである、すなわち (1) 複数ソースのノイジーなデータから教師なし学習で学習できて、 (2) 任意のドメインの問題に適用できるべきである モデルが巨大で複雑になっても、推論はリアリタイムでおこなえるべきである 構築、デバッグの簡易化のためにシステムはモジュール化すべきである モジュラ性はシステムを効率的に反応できるようにするべきである エラーが起きた時に、何故それが起きたか理解可能にするために、各モジュールは解釈可能であるべきであり、同様にモジュールの構成も解釈可能であるべきである システムは単調的に修正可能であるべきである: 起きたエラーに対して、別のエラーを引き起こさずに、どのようにモデルを修正すればよいかが明白であるべきである システムは意味表現に対して論理的推論をおこなえるべきである システムの入力のテキストの意味表現とシステムの世界モデルを組み合わせることで論理的な結論をだせるべきである もろさを避けるため、また根拠を正しく結合するために、論理的思考は確率的であるべきなようである (Richardson and Domingos, 2006) システムは質問可能であるべきである 任意の仮説に関して、真であるかどうか (の確率) を断言することができること 私達はなぜその断言ができるか理解することができるべきである 最近の研究では 論理形式を文に対してタグ付けするなど、意味のモデル化はアノテーションコストがとても高い 興味深い代替手段としては、質問-回答のペアから論理形式を帰納するアノテーションがより低いものがある (Liang et al.
proceeding slide: slideshare
まとめ CIKM 2013でBest paperを取った、著者が全員女性(参考)という、自分が今まで読んだ中でおそらく一番華やかな論文で、Yahoo Answersを知識源として、セレンディピティ (思ってもみなかったけど、クエリと関連していること) を感じる検索を提供する話。 何か新たな手法を提案した、というよりは、Yahoo Answersという知識源を使うことで、何か思ってもみなかったけど、面白い検索結果を提供できるんじゃないかな〜というアイディアを実際に試してみた、という感じだろうか。
以下、メモ。
Why/when do penguins wear sweaters? タスマニアで起きた原油漏れで体に油がついてしまったペンギンが、再び元の生活に戻れるようにするためのチャリティーソング (James GordonのSweaters for Penguins) 羽毛に原油がつくことで断熱性が落ち、ペンギンが凍えてしまう くちばしで羽毛に付いた原油を落とそうとすることで体を傷つけてしまう Serendipity 役に立つんだけど、特に探していたわけではないもの。
Entity Search この論文ではWikipediaとYahoo! Answersから抽出した、メタデータで情報を豊富にしたentityネットワークを基にentity-driven serendipitous search systemを作成する。
この論文の焦点 WHAT ウェブコミュニティの知識源はどのようなentity間の関係を提供するのか？
WHY そのような知識源がどのように面白く、セレンディピティなブラウジング経験に寄与するのか？
データ Yahoo! Answers ごくわずかにまとめられた意見、ゴシップ、個人情報 観点が多様 Wikipedia 高品質の情報が整理されている ニッチなトピックが豊富 Entity & Relation Extraction Entity: Wikipediaに記述されている概念 1 テキストから表層形を識別し、 2 Wikipediaのentityと紐付けして、
文脈依存 文脈非依存な素性 click log 3 Wikipediaのentityを、テキストとの関連度順に基いてランキングする (aboutnessスコア(34)を使ってランキングする)
個人的にはプログラミングの勉強は写経が一番頭に入る気がする、ということで読んでいた。
気になったところ データに正規分布を仮定したときのナイーブベイズ分類器について。 平均を\(\mu\)、分散を\(\sigma^2\)としたときの正規分布は
\[ p(x;\mu, \sigma^2) = \frac{1}{\sqrt{2\pi \sigma^2}} \{\exp{-\frac{(x-\mu)^2}{2\sigma^2}}\} \]
これのlogをとると、
$$ \begin{eqnarray} \log p(x;\mu, \sigma^2) &=& \log \{\frac{1}{\sqrt{2\pi \sigma^2}} \{\exp{-\frac{(x-\mu)^2}{2\sigma^2}}\}\} \\\
&=& -\frac{1}{2}\log (2\pi \sigma^2) - \frac{(x-\mu)^2}{2\sigma^2} \end{eqnarray} $$
ナイーブベイズ分類器の対数尤度関数は、データがK次元ベクトルで表現されていて、それがN個あるとすると、 $$ \begin{eqnarray} \log L(X, Y; \mu, \sigma) &=& \log(\prod_{n=1}^N p(\mathbf{x}_n, y_n))\\\
&=& \log(\prod_{n=1}^N p(y_n)p(\mathbf{x}_n|y_n))\\\
&=& \sum_{n=1}^N \log p(y_n) + \sum_{n=1}^N \log p(\mathbf{x}_n|y_n)\\\
&=& \sum_{n=1}^N \log p(y_n) + \sum_{n=1}^N \sum_{k=1}^K\log p(x_{nk}|y_n)\\\
&=& \sum_{n=1}^N \log p(y_n) + \sum_{n=1}^N \sum_{k=1}^K \{-\frac{1}{2}\log (2\pi \sigma_{y_nk}^2) - \frac{(x_{nk}-\mu_{y_nk})^2}{2\sigma_{y_nk}^2}\} \end{eqnarray} $$
acl anthologyよりロングペーパーとして 採択された論文の中からSummarizationをタイトルに含む論文を探して概要だけを読んだときのメモ。
Fast and Robust Compressive Summarization with Dual Decomposition and Multi-Task Learning (P13-1020.pdf) 概要 複数文書要約のための文選択、文圧縮を同時におこなうモデルを使った双対分解を提案。 先行研究のIneger Linear Programmingに基づいた手法と比べると 提案手法はソルバーを必要としない 提案手法は有意に速い 提案手法は簡潔さ・情報の豊富さ・文法のきれいさが優れている さらに既存の抽出型要約、文圧縮の要約データを活用したマルチタスク学習を提案する TAC2008のデータで実験をおこなって今までで一番高いROUGE値となった。 Using Supervised Bigram-based ILP for Extractive Summarization (P13-1099.pdf) 概要 Integer Linear Programmingによる抽出型文書要約において、bigramの重みを教師有り学習により推定する regression modelによってbigramが参照要約の中でどれくらいの頻度で出現するかを推定。 学習では、参照要約中での真の頻度との距離が最小になるように学習をする 選択されるbigramの重みの総和が最大になるように文選択をおこなうような定式化をしている 提案手法は既存のILPな手法と比べてTACのデータにおいて良い性能であることと、TACのbestだったシステムとの比較結果を示す Summarization Through Submodularity and Dispersion (P13-1100.pdf) 概要 Linらのサブモジュラな手法を一般化することにより新たな最適化手法を提案する 提案手法では要約にとって欲しい情報はサブモジュラ関数と非サブモジュラ関数の総和で表される。この関数をdispersionと呼ぶ 非サブモジュラ関数は要約の冗長性を除くために文同士の様々な似ていなさの度合いを図るために使う 三つのdispersion関数を使って、全部の場合で貪欲法を使っても最適解が得られることを示す DUC 2004とニュース記事に対するユーザのコメントを使って実験 サブモジュラ関数だけを使ったモデルよりも良い性能であることを示す Subtree Extractive Summarization via Submodular Maximization (P13-1101.
KDD 2013読み会に参加させていただきました。 せっかくなのでと思い論文を読んで発表してきた。 主催してくださった@y_benjoさん、会場を提供してくださったGunosy Inc.さん、ありがとうございます。 これまであまり外部の勉強会で発表する機会が無かったので少し緊張したけどその緊張感はとてもよい感じだった。 個人的には参加者数が多すぎず少なすぎなかったのが良かった。
読んだ論文 Diversity Maximization Under Matroid Constraints, Zeinab Abbassi, Vahab S. Mirrokni and Mayur Thakur, KDD 2013
proceeding (pdf)
ニュース配信サービスがいかに小さくて多様なニュース記事を提示するかという話。 カテゴリに対してたかだかp個ずつニュース記事を選択してdiversityを最大化するのだけど、その制約をpartition matroidで表現している。 記事集合の選択にはdiversityがある程度上がるなら文書をどんどん入れ替えるgreedyなアプローチをとっているのだけど、最悪でも一番高いdiversityの1/2以上であることを保証してくれる。
ペアワイズの距離を定義して、その総和をdiversityとしているのだけどそのペアワイズの距離が少し変わった形をしている。 これは1/2近似であることを証明する時に必要な性質をもっているため。 この式をgeneralized Jaccard distanceと呼んでいて、重み付きの要素をもつ集合間の距離を測るときに用いることができる。 今まで見たことがなかったのだけど、（この式はよくあるものなのかという質問もいただき）調べてみたら他の論文でもJaccard距離の一般的な表現として登場しているのでこの論文で定義されたものではないみたい。
人手の評価もおこない、diversityを考慮しない場合よりもdiversityを考慮した文書集合の方が観たいと答えた人の割合が多いという結果になった。
関数の定義が書かれていなかったり、average distanceと書いてある評価指標が距離の総和を取っているだけの式に見えたり、Googleの中の人じゃないと分からないことを書いていたり、読むときに少し障壁を感じた。
発表資料 議論 大事なことだと思ったので発表時に頂いたコメントを自分なりにまとめた。 自分の解釈が間違っているかもしれないので、もし間違っていたらご指摘ください。
diversityに価値があることはなんとなくわかるけど、diversityを考慮していないものと考慮したものを比べても意味ないのでは diversityを良くしたら本当にユーザにとってためになるものが提供できるのか 極論するとランダムな文書集合で満足するユーザがいるかもしれない diversityにも色々あるし、diversityの良さは人によって違うのでは 色々なdiversityと人間の評価の相関とか調べると面白いかも
proceeding (pdf), slide (html), journal (pdf)
KDD 2012の時点では元々Yahoo! Researchにいた著者らがjournalでは所属がみんなばらばらになっているので興味があって調べてみたけど、 マリッサ・メイヤーのYahoo! CEO就任は2012年7月17日、KDD 2012は2012年8月中旬、 おそらくその後にjournalを出しているのでマリッサ・メイヤーの就任は転職に影響したのだろうかという 余計な詮索をしていた。 journalのpublish dateはMarch 2010となっているけどreferenceにはそれ以降の論文もあるし、 これは2010に出たjournalではないらしくて時系列がどうなっているのか混乱した。
概要 entity matchingでは正例に対して負例がとても多く、学習にはprecisionがしきい値以上であるような 制約を満たすようにrecallを最大化するactive learningアルゴリズムが提案されている。 ただ先行研究のアルゴリズムはlabel complexity、computational complexityともに高いので 提案手法では近似的にprecision制約付きのrecall問題を解く方法を提案してそれが先行研究 に比べて早く、しかも精度もよく学習できることを示している。
発表資料 以下メモ。
Convex hull algorithm precisionの制約付きrecall最大化問題を解きたいのだけど、制約があると面倒なのでラグランジュの未定乗数法 のようにして問題から制約を取り除く。 また分類器の空間Hは次元数に対して指数的に増加するのでそこで探索するのを避けて、分類器を recall、precisionの空間に写像して、写像した空間P={(X(h), y(h)):h∈H}で探索をおこなう。 探索には二分探索を用い反復的に0-1 lossを最小化する問題をactive learningアルゴリズムによって解いている。 ここで、active learningはどんなものでも良くてblack boxとして扱うことが出来る。 Rejection sampling algorithm black boxの学習をおこなう前に呼び出されるアルゴリズム。 気持ちを理解するにはMachined Learnings: Cost-Sensitive Binary Classification and Active Learningが詳しい。 要約すると分類器の学習にはfalse positiveやfalse nagativeに対してどちらをより優先して 少なくするような重み付けをした目的関数を最適化する方法があるのだが、この重みはラベル が付いていないサンプルに関しては人間にラベルの問い合わせをおこなわないとできない (正解 が正例、 負例のどちらかがわからないとα、1-αのどちらを掛けたらよいか決められない) 。 今の状況では、active learningのアルゴリズムがラベルの問い合わせをおこなったサンプル についてのみ正解のラベルがわかっている。そこで、ラベルの問い合わせをしたサンプルのみ 正例の場合は確率α、負例の場合は確率1-αで訓練データとして扱い、そうでなければ棄却をする。 棄却されなかったサンプルの集合の期待値を計算するともとの目的関数と同じになる。
