米国大学院PhD出願に対する私なりの臨み方

はじめに

こんにちは、はじめまして、usaito(HP, twitter)です。2016年の4月に東京工業大学の第4類に入学し、その後工学院経営工学系に進みました。途中1年間休学したこともあり、2021年の3月に学士課程を卒業しました。大学入学から丸5年が経ったと思うと、あっという間だったなという感覚ととても長かったという感覚が入り混じっていてなんだか不思議な感じです。

さて、あとでも詳しくまとめますが、昨年12月に米国大学院の博士課程にいくつか出願し、結果的にCornell UniversityのDepartment of Computer Scienceに博士学生として進学することなりました。 本記事では、私が出願過程で経験したことや考えていたことをまとめます。

私としては詳細かつ赤裸々に経験をまとめたつもりですが、 客観的な情報源としてはすでに素晴らしいリソースがいくつも存在するので、この記事を読んでも新たな情報を得られないかもしれません。ただ客観的な情報と言っても、米国大学院博士課程への出願は、分野や大学、置かれた状況などによって人それぞれの経験がかなり違ってくるものであり、「〇〇が一番重要で、次に重要なのは〇〇で...」などについて、誰にとっても正しい情報は存在し無いのではないかと思います。私もありがたいことに多くの方にアドバイスを頂いたのですが、人それぞれ言っていることが異なることもありました。おおよそ意見が一致している部分はあるのでそれは押さえるべきでしょうが、あとは自分にしっくりくる考え方・臨み方で出願準備を進めるものなんだと思います。その上で、これまで出願に対する臨み方などのお気持ちに近い部分を中心に据えている記事はあまり無かったかと思うので、本記事では特にその部分に焦点を当てたつもりです。「そういう臨み方もあるんだ・あってもいいんだ」という一つの選択肢を誰かに提示できていたら嬉しいなと思います。

なお、私が本記事で特に書きたかった内容は主に終盤(特に「これまでの振り返りとこれから」以降)にあります。ということで、少々長いな、この内容は知っているなという部分は適宜飛ばしつつ、是非最後まで読んでもらえたらとても嬉しいです。

留学に至る経緯

この記事の執筆に先立って、合格体験記に当たる既存のブログ記事や報告書をいくつか見させていただいたのですが、多くの方が冒頭に「米国大学院進学に至った経緯」なるものを綴っていました。私もそれにならってそのような導入をしてみようと少し考えてみたのですが、残念ながらあまりかっこいい話は出てきませんでした笑。

その時々で好きだったり楽しいと思えることができていれば良いかなくらいのことしか基本考えていないのですが、いわゆる仕事の中では今のところ研究が楽しいなと思っています。特に、何かしらの提案手法があったときに、それをどんな文脈で説明すると最も受けるのか多くの可能性の中から選択する部分が楽しいです。またそれを文章に落とし込む部分だったり、学会や勉強会の聴衆に合わせてどんな構成が最も受けるのかを都度考え直すのも楽しいなと思います。また、実在するにも関わらず研究としてはあまり扱われていない一方、扱い方次第では受けるストーリーに乗る問題設定を、人の話を見聞きする中で拾い上げるのも楽しいと思っています。

その上でなぜ留学しようと思ったのかというと、「それ以外の選択肢が気付いたら頭に無かったから」というのが一番しっくりくる理由になりそうです。私にとっては博士課程に進むことも、その段階で留学することも至って自然な選択であり、特に決心などはしていませんでした。国内の大学院の併願もしていません。どうして米国大学院進学が自然な選択肢になっていたのかはよくわからないのですが、国際学会に何度か参加して感じた雰囲気や相性だったり日本の学士課程を修了するまでに色々感じていたものが合わさってそのような気持ちが徐々に作られたんじゃないかなと思います。高校生の時からなんとなく海外への興味はあって学位留学の存在やそのために必要な準備はある程度知っていたこと*1今のところの研究分野の情勢(主要な研究者がほとんど欧米にいる)も影響している気がします。

博士課程を通じて、自分が楽しいと思っていることをもっと楽しめるようになりたいです。具体的には、基礎知識を固めたり扱える領域を広げてもっと自分が「これは面白いだろう」と思える文章を書けるようになりたいです。また複数の領域や立場(研究者と実践者など)の人と関わることで、分野間や立場間にはびこるまだ誰も語っていないギャップのようなものを掘り出していきたいです。さらに長期的にはそのような楽しい仕事が続けられるポジションを得たいと思っています。過去数年が結構目まぐるしかったので次の数年で全然違うことを言っている可能性も大いにありますが、留学に至る経緯(?)はそんなところです。

出願に対する考え方

上記のようにふわっとした経緯で自然と留学する流れや考えになっていたので、そもそも大学院出願を一大イベントだとは思っていませんでした。これから粛々と書き連ねることになりますが、書類の準備やフォームの入力、スコアの確保やその他諸々の管理など、出願準備自体は無機質であまり楽しいものではありません。よって、「全ての項目において完璧を目指すというよりも、自分の気持ちにあらがいすぎない範囲で、ただ受かって欲しいところにはちゃんと受かるよう要所を押さえる」というのが大学院出願に対する私の臨み方だったのだろうと思います。また折角時間を使って準備するので、出願それ自体のためというよりも、合格した後にも繋がっていると私が思えるような期間にできたらなと思っていました。その意味ではあまり気持ちの起伏なく出願過程を過ごせましたし、完璧ではないにせよ合格したかったところには合格できたので、ある程度うまくいったのかなと思っています。一方で、抜け目なく準備してできるだけ多くの大学院に合格し、選択肢を増やしたいといった方にはあまり参考になる情報は提供できないかもしれません...

出願過程

それっぽい導入を終えたところで、具体的な話を始めます。もうよく知られたものだと思いますが、米国大学院の出願過程は日本のものとは大きく異なり、研究実績や推薦状、GPA、面接などをもとに、総合的に評価され合否が決まります。評価の仕方は大学によって異なり、あらゆる観点から総合的に判断されるらしいですが、基本こちらから中身は見えません。

ここからは、それぞれの要素についての簡単な説明や私個人の経験と結果、対策などをまとめます。他のリソースと比較すると、「研究実績/CV」「事前コンタクト」「面接」あたりを特に詳しく書いたつもりです。また次章の「進学先を決めるまで」も他と比べて充実させたつもりです。逆にそれ以外の要素については、あまり新たな情報はないかもしれませんが、スコアなど赤裸々に書いているので、後半でまとめる合否一覧と合わせて一つのケースとして参考になるかと思います。

TOEFL/GRE

日本からアメリカの大学院に出願する場合、残念ながら英語の能力証明が必要です。IELTSを選択できる場合もありますが、私は大学2年生の時に1度受験したことがあったTOEFL iBTを選択しました*2。私の場合、複数の研究を並行して進めていたり、4年生になっても卒業要件が満たされておらず授業をいくつかとりながらだったので、特段TOEFL向けの対策はせず(できず)、目標の100点が取れるまで受験を続ける力技で凌ぐつもりでいました。コロナの影響もあってTOEFL iBTは自宅受験が可能になっており、試験場に移動することなく自分の好きな時間に受験できたのが、個人的には助かりました。結果、2回目の受験で100点を超えることができ、これで足切りされることは無くなったので、TOEFLの受験を終了しました。

受験日 Reading Listening Speaking Writing 合計
2020/6/16 29 24 23 21 97
2020/9/29 29 29 23 24 105

元々大学受験の時に力を入れて勉強していたReadingとListeningの点数をしっかり取った上で、SpeakingとWritingは出たとこ勝負という作戦でした*3。後述する奨学金出願の時期とTOEFL受験が被ってちょっぴり大変だったので、受験する年の春頃までに点数を取り終えているととても楽だと思います。

GREは、

  • Verbal Reasoning (TOEFLのReadingみたいなやつ)
  • Quantitative Reasoning (算数)
  • Analytical Writing (TOEFLのWritingみたいなやつ)

という3つのパートで構成される試験です。こちらもコロナの影響から自宅受験が可能でした。過去の受験体験記などを見てみてもあまり重要ではないとの記述が多かったため、私自身も重要視していませんでした。1回試しに受けてみて悲惨な点数で面白くなかったことと、コロナの影響から出願したすべての大学でGREの提出が必須ではなくoptionalとなっていたことから、結局GREのスコアは提出しませんでした(Caltechはそもそも提出欄がありませんでした)。次の年からどのような扱いになるのかよくわかりませんが、提出すらしなくても問題なくことが進むようです。もしGREに時間を割く余裕があり、何かしらの対策をしたい方は、最後に並べる関連記事を参考にするのが良いでしょう。

GPA

大学での学業成績です。私の場合、最初の2年間くらいは真面目に授業をこなしていて、GPAは3.7/4.0くらいあったのですが、その後所属学科とは関係のない研究を始めそちらに力を注ぐようになってしまったため、大学の講義にはあまり時間が取れず、最終的に専門科目のGPAは3.1/4.0という大学院留学を目指すものとしてはなかなか悲惨なものになっていました*4。特に卒業直近の2年間のGPAは2点台前半に急降下していました(よくこの適当さ加減で合格できたものです)。 多くの人は大学生活の前半で悪かった成績を専門科目で取り返して受験に臨むようなのですが、私の成績は全く逆の挙動になっています。研究実績や推薦状などに比べるとGPAは重要ではないと思いますが、落とされた大学についてはGPAが悪さをしていたのかもしれません。GPAが高いに越したことはないのでしょうが、あまりやる気が出ないのに無理に頑張る必要もないと私は思うので、自分が置かれた状況や気持ちに応じて適度に取捨選択するのが良いのでしょう。私のように研究実績やコネクションの部分に力を入れていれば、受かるところには受かるらしいので、GPAが低いからといって気にし過ぎる必要はないと思います。自分が得意で好きな部分に思いっきり取り組むのが、精神的な意味でも健全でしょう。

研究実績/CV (履歴書)

コンピュータサイエンス(CS)の特に機械学習に関連する領域では、出願時の研究実績・経験が重要な要素になっているようです。年々出願者の研究実績が(少なくとも見た目上は)インフレ傾向にあることが囁かれており、研究実績で周りと差別化することは中々に難しい状況にあります。そんな状況の中で私は、主に研究実績に絞って力を注ぎました。これは、大学院出願のみに最適化しようと思った場合は筋が悪い行為なんだろうと思います。しかし、

  • 元々自分が納得のいく研究や発表ができるようになるための通過点として出願を捉えていたので、出願準備期間も研究関連の時間をできるだけ減らしたくなかった
  • 単純に楽しいこと以外やりたくないということで、自分が精神的に苦にならずに頑張れる部分のみに力を使いたかった
  • GPAやGREなどの点数を確保するタイプの要素にはもっぱら興味ややる気が見出せなかった
  • 出願先の先生に(良い意味で)目をつけてもらうことで、入学後の研究や評価に弾みをつけたかった
  • 学部生としては映える研究実績を作れる見込みがあった

などの理由から、割り切って研究に注力し、その結果としてなるべく自然な形かつ出願先の先生方に好印象を残すという、先に活きる(と自分が思える)内容で合格することを目指しました。

大学院留学が自然な進路となる前の2018年(大学3年次)の夏頃からアルバイトで研究を始めていたこともあり、その流れに乗ってしばらくずっと研究していました。その間、大学の授業を無視して卒業が若干危うくなってきていたことからは目を背け、2019年度は1年間休学して、徐々に共著者の輪を広げながら論文執筆に力を入れていました。そんなこんなで運良く学部生の研究としてちょうど良い難易度かつ比較的競争が激しくない領域を見つけることができ、大学院出願時までには、名の通った国際会議の本会議で計8本の論文を発表できました*5。ただし注意が必要なのは、私の実績はWSDMやRecSysなど機械学習の応用系の学会での発表がほとんどだったということです。一方で、出願先の大学や研究室は、ICMLやNeurIPS、AISTATSなどのより一般的な機械学習の学会を主な論文発表の場とする、理論や方法論の雰囲気が強いところが多かったです。したがって、学部生としては一見研究実績があるように見えるかもしれませんが、実際のところ見た目ほどアドバンテージはなかったように思います。

さて機械学習分野は、特別な実験器具などが必要になることも少なく(良いのか悪いのかはよく分かりませんが)比較的早く論文執筆に入りやすい分野だと思います。私は最初論文の書き方などを指導してくれる人がいなかったのですが、arXivで公開されている有名な研究者や多く引用されている論文などの書き方や構成をいくらか真似しつつ、自分がすんなり読めるまで文章を何十回も修正するという地道な方法で、なんとか実績を作ることができました。私みたいにそもそもCS専攻ではなく、周りに関連の研究をしている人がいない状況でも自分の心の持ち用や工夫次第でどうにかできるようなのでとりあえずは自分なりに動いてみることが大事だと思います。また最近だと国内でも企業の研究所でコンスタントに国際会議で発表を繰り返しているところもあります。私も長らくお世話になっているCyberAgent AI Labはその最たる例でしょう。もちろん他大学の先生にコンタクトを取ったり、交換留学の機会を活用することもできると思います。ただし、連絡を取る先や留学先の研究室が本当に「自分が狙っている会議やジャーナルに論文を出版しているかどうか」は事前にチェックすべきでしょう。またいくつかの大学は、学部生のためのサマーリサーチプログラムを開催していたりするので、それもコネ作りの意味も込めて活用できるかもしれません。例えば、CaltechSummer Undergraduate Research Fellowships (SURF)StanfordSummer Sessionなどは、準備は大変そうですが、検討の価値はあると思います。他の主要大学も探せば似たプログラムを開催していることでしょう。

また個人的な経験として、途中で1年休学したのは結果的にとても良い選択だったなと思います。1年間他のことに時間を取られることなく研究に集中できた一方で、途中で休学していても基本的には学部からの出願として受け取られていた気がするので、研究実績を溜めたりコネクションを築いたりする時間を確保しながら選考過程での比較対象が学部生になるという良いとこ取りができたのではないかと思っています。分野などにも大きく依存すると思いますが、修士に進んで研究実績を積もうとする場合、選考においては修士学生としての比較的高めのハードルで見られてしまうことがあるかもしれないので、進学が効果的かは場合によりけりでしょう。まだ学部3年生で、海外大学院の博士課程への留学を考えていたり迷っていたりする人にとっては、積極的に検討してみても良い選択肢のひとつなのではないでしょうか*6

さてここまでは、研究実績や論文の"量"的な側面に触れてきましたが、それと同等以上に重要なのが、自信を持って紹介・プレゼンできる代表的な研究を1つ持っておくことです。と言うのも、いくら論文実績を持っていたとしても面接や学会などで先生に直接紹介できるのはそのうちほんの一握りであり、その研究の紹介でどれだけインパクトを残せるかでその後の成り行きが大きく変わってくるからです。会議に採択されるか否かのボーダーラインを攻めた結果採択されたといった論文をたくさん持っていたところで、1-on-1で教授に研究内容のプレゼンをする機会が舞い降りてきても、大きなインパクトを残せない可能性があります。逆に、論文の数はそれほど多くなくても、ドデカい仕事を1つでもしていればそれだけで教授の心を鷲掴みにできることもあるでしょう。

私の場合は、2019年の11月頃から本記事執筆現在まで継続して取り組んでいるOpen Bandit Projectが、大学院出願時における代表作の位置付けを担っていました(とはいえあくまで出願時のレベルでの代表作であり改善点は山積みで、国際会議の採択有無に関係なくしばらくは注力し続けるつもりのテーマです)*7

さてこの研究プロジェクトに関する論文は、出願時にはまだどの国際会議にも採択されていなかったので、特に論文の実績として加算されるものではありませんでした。にもかかわらず、この研究プロジェクトの存在は、いくつかの大学院への合格をかなり後押ししてくれました。というのも国際会議のワークショップや面接などでこのプロジェクトの内容について発表したときに、必ずといって良いほどとても好意的な反応を得ることができ、その後の議論が盛り上がったり継続的なコンタクトに繋がったからです。特に象徴的だったのが、RecSys'20という国際会議に併設されたREVEALワークショップでの口頭発表です。この発表には、志望度合いが高かった大学の先生が聴きに来ていたのですが、以下の通り当初は予期していなかったインパクトや印象を残すことに成功しました。

その時のワークショップでの発表の様子がYouTubeに上がっているので、参考までに貼っておきます。

youtu.be

また面接における先生方への研究紹介もこの発表を改編する形で行っていました。例えばこんな感じで、毎回ショートプレゼンを行っていました。

特にワークショップの発表の方は、今見るともうちょっと練習して、スライドも詰めた上で発表しろよと突っ込みたくなる出来ではありますが、発表が終わった数分後に発表を聴いていた志望先の先生から直々にメールを貰うことができ、そのポジティブな内容も相まって驚いた記憶があります。この発表のことはその後も何度かメールのやり取りで話題に上がっていたので(少なくともその先生には)良いインパクトを残せたようです。こういう状況に持っていければこっちのもので、その後は先生がAdmission Committeeに色々と働きかけてくれ、思った以上にすんなりと事が進み合格できました。

この経験は、大学院合格に繋がっただけではなく、たった1つの発表が周りの自分に対する評価や印象、その他諸々の潮目を大きく変える可能性があることに気づかせてくれました。これ以降、論文の数やaccept or rejectの連絡などそれまで気にしていたことは、ほとんど気にならなくなりました。また会議に論文が採択されたら終わりなのではなくて、学会や勉強会で発表するまでが研究の一環であるという認識を持てるようになりました。

さて話がそれましたが、研究実績やその他の客観的なアピールポイントは、Curriculum Vitae (CV)といういわゆる履歴書にまとめて出願時に提出します。それだけではなくて、事前コンタクトの際に先生に送ったり普段の研究生活でも必要なものになるので、まだ整備していない方はできるだけ早く作ってしまい、定期的に更新するのが良いでしょう。

私が出願したときに用いたCVはこんな感じで、overleafで管理していました。今でもこのフォーマットは気に入っており、その後も継続して使っています。CVには特に凝るポイントはなく、事実を淡々と書くものだと思います。ほとんどの研究者の個別ページにはCVへのリンクが貼ってあるので、自分が知っている研究者のCVを参考にすることもできます。

Statement of Purpose (SoP)

いわゆるエッセイ・志望動機書です。SoPの重要度については諸説あるようですが、後述するように面接で話した先生方は基本的にSoPに目を通しているようだったので、最低限ポイントを押さえておくと安心です。 位置付けとしては、CVでは研究実績など事実を客観的に記す一方、SoPにはもう少し主観的で感情的な、熱意が伝わる要素を入れ込むと良いという話を聞きました。すでに奨学金を獲得していたら、それを書くことも忘れてはいけません。私は大雑把に以下の5段階構成で、2ページに収まるようtexで作文しました*8

  1. 導入として博士課程に進学したい旨や研究興味
  2. これまでの研究経験
  3. 博士課程で行いたい研究テーマ
  4. なぜその大学なのか
  5. 博士課程を修了後の進路

「なぜその大学なのか」は大学ごとに内容を変更し、1大学あたり約2名の先生の名前を入れました。それ以外の箇所は基本的にどの大学も同じ内容を用いました。2番目のこれまでの研究経験の部分では、それぞれの研究プロジェクトにおける自分の貢献を明確にすることを意識しました。特に学部生が書いている共著の論文だと、「共著者のお陰で論文が書けただけ」と思われるかもしれないので、それを少しでも解消できるように自身の貢献を明確化したり、専門知識をさりげなくアピールすることを心掛けました。一通り文章が書けた段階でEssay Edgeを使って、英文校正を行いました。私の場合は11月に入ってから執筆を始め、2,3人の方に意見をもらいながら英文校正を行い、11月末頃には完成していました。多くの人にレビューしてもらいクオリティを高めたい人は、もう少し早めに取り組むのが良いでしょう。SoPを書き始めるにあたっては、検索したら出てくる過去のSoPに加えて、

などをあらかじめ覗いておくのが良いでしょう。さらに秋ごろになると多くの大学でapplication support programなるものが立ち上がります。大学によって内容は異なると思いますが、現役の学生に出願に関連する質問ができたり、SoPの添削をしてもらえたりするようです。例えば、Brown / CMU / Cornellあたりのapplication support programが、私の調べではすぐに出てきました。「application support underrepresented students + 希望の大学名」などで検索すると、自分の志望する大学の学生が運営するapplication support programが見つかるかもしれないので、探してみると助けになることでしょう。

推薦状

推薦状は、選考において非常に重要視されると多くの人が話している要素だと思います。最も重要だと断言している方もいらっしゃいます。私の出願先の先生の中にも、推薦状がかなり重要だと言っている方がいました。推薦状は、基本的に3通書いてもらう必要があります。もっとたくさん書いてもらえる場合は、6通くらいまでオプションで提出できる大学もありました。論文を一緒に書いたことがあるなど、自分のことをよく知っていて具体的に評価してくれる人に頼むことが大事であると聞いたので(その上で可能であれば分野の権威などに書いてもらえると尚良い)、それに従い共著で論文を書いた経験などがあった3人の先生にお願いしました*9奨学金の出願の際にも推薦状を書いていただく必要があるので、その締切に合わせて6~7月頃には推薦状執筆のお願いをし、その後出願校が定まってきたりCVにアップデートがあればその旨を伝えていました。しかしそれ以上については基本的に先生方に任せっきりにしてしまっていたので、残念ながらあまりここで書けるtipsはありません。今思うと、もう少し具体的に書いていただきたい項目や簡単な下書きを用意した上でお願いした方が、意思の疎通が図りやすかったなと反省しています。可能ならSoPも早めに仕上げて共有すれば良かったです。以下の記事の該当箇所に詳しくまとめられているように、入念な準備ができると万全なんだと思います...

akaria.hatenablog.com

ちなみに推薦状の提出は、大学ごとの出願フォームに推薦者の情報を登録したのち、推薦者宛に推薦状を提出するためのフォームが送信される仕組みになっています。できるだけ早めに推薦者の登録を行い、余裕を持って推薦状の提出をしていただくための準備を進めましょう*10。推薦状を提出してもらえているかどうかは、出願フォームから確認可能なので、それをもとに適度にリマインドすると良いでしょう。

奨学金

出願時点で外部の奨学金を確保していることは、推薦状や研究実績と並んで最重要要素の一つであると紹介されることが多いです。これは外部の資金援助があることで、指導教員の研究資金への負担が軽減されたり、奨学金を持っていることがその学生の能力の証明になるためだと言われています。また入学後に資金援助をしていただけるのは、TAなどに時間を割くことなく好きな研究に集中できるという意味でとても大きなことです。

私は、次の3つの財団の奨学金に応募しました。

これらの奨学金は、他の大学院留学体験記でも紹介されていて元から知っていたこと、応募書類を手書きする必要がないこと、応募書類に書く文章の内容がそこそこ似ていることなどから、応募することにしました。これらの奨学金は競争率が高いため、もう少し多く応募する人もいるようです。もちろん多くの奨学金に応募した方が、そのうちどれかに採択される可能性は高くなるでしょうが、その分書類作成等が大変になるので、自分の置かれている状況や気持ちに合ったバランスを見極める必要があります。

奨学金の応募書類では、専門的な研究計画を審査員の方々に伝わるようわかりやすく書く必要があるので、その辺の按配は公開されている科研費の概要の文章をここから探して参考にしました。またそれに追加して、もう少し自分の熱意や分野に興味を持ったきっかけなどを入れるようにしました。結果としては、上記3つのうち2つの奨学金に採択していただきました(もう1つは選考途中で辞退)。最終的には、支援が手厚くかつ財団生の交流が充実している船井情報科学振興財団の奨学金をいただくことにしました。

他の奨学金については、

XPLANE_学位留学奨学金一覧 - Google スプレッドシート

にとてもよくまとまっています。奨学金の応募は、大学院に出願する年の7~9月に設定されていることが多いです。よって、早くからアンテナを張ってどの奨学金に応募するのかを決めておく必要があります。

事前コンタクト

事前コンタクトは、他の要素とは性質が異なり大学から要求されるものではなく、自ら能動的に行うものです。私の場合は、事前コンタクトの有無および度合いが、合否にかなり効いていたのではないかと思っています。重要度は人や分野によってまちまちなのでしょうが、多くの人が事前コンタクトの重要性を説いている印象があります。奨学金の出願書類に事前コンタクトの進捗度合いを書く欄がある事実からも、事前コンタクトの具合が重要そうだということが伺えます*11

私の場合は、基本的には以下の2段階でメールによるコンタクトを取りました。1段階目ではその時点で出願の可能性があった研究室の先生方10人強に、2段階目では1段階目で反応があった人を中心にメールを送りました。過去の事例では数十件のコンタクトメールを送っていた人もいるみたいですが、私の場合はある程度興味分野が定まっていたことやメールのやり取り・管理にも結構な労力がかかることなどから、比較的事前コンタクトの数は控えめでした。

  1. (7~8月)自己紹介や大学院に出願する事を伝えたり、可能ならCommitteeに推薦して欲しい旨を伝える
  2. (11~12月)具体的に出願する旨や奨学金獲得・論文執筆などのアップデートを報告する

メールを送信する際には『海外大学院の教授に英文メールを書く』などの記事を読んで、事前に基本的な作法を押さえておくとより安心かもしれません(この辺は英語でも情報を探しましょう)。

さて私の場合、1段階目では単に自己紹介を一方的にしただけだったのですが、その中である1人の教授から「君に興味があるのでぜひ1度話をしてみたい」との返信をいただいたことがありました。結果的に、その面談の中でそれまでに行っていた研究テーマの紹介をしたところ興味を強めてもらうことができ、以後継続的に連絡を取り続けられただけではなく、最終的にその先生がいる大学に合格できました。夏の時点である程度志望度合いの高い先生が固まっていたら、その先生方には自己紹介や出願する旨の報告に留まらず、短い時間でも面談できないか打診してみると良いと思います。

なお先生方にコンタクトするにあたっては、事前にその先生のホームページを細かくチェックすることをお勧めします。というのも、「〇〇の場合についてのみコンタクトして欲しい」「そもそもメールでのコンタクトはしないで欲しい」などの注意事項が書かれている場合が結構あるからです*12。私も、こういった記載事項をよく確認せずにメールを送った後で言及すべき点に言及していなかったことに気づき、結局返信を貰えなかったことがありました。このように注意事項を無視してしまうと反応をもらえないどころか返って印象を悪くしてしまうことにも繋がりかねないので、十分に注意する必要があります。

出願

さて上記の出願書類が全部揃ったらいよいよ出願です... と言いたいところですが、出願書類が整う前から出願フォームの入力は進めるようにしましょう。ほとんどの大学では9月頃から出願のためのアカウントを作成できるようになり、また出願フォームについては入力内容を一時保存しておくことができます。出願校がある程度の数になってくると、比例して出願フォームの入力にかかる時間も長くなってきます。出願締切の2ヶ月前である10月上旬くらいには一通り出願のためのアカウントを作ってしまい、隙間時間を見つけて埋められるところから埋めていくのが良いかと思います。また、フォームをあらかじめ眺めておくことで主要な必要書類以外に必要な細かい情報や作業を先んじて把握することができます。私は、出願フォームを確認してからTOEFL(やGRE)のスコアレポートを大学に(ETSを通して)送付する必要があることに気付き、若干焦りました。特に大事に至ることはなかったですが、もう少し余裕を持って出願の作業を進めておいた方が安心だったなと思います。

面接

12月の上旬から中旬にかけて出願を終えたあとしばらくは何もないのですが、1月の中旬くらいからちらほらと面接を行いたいという内容のメールが届くようになります。私は、面接については特に凝った準備することなく挑みました(こちらからする質問くらいは用意していましたが)。MITの面接だけ長々といろんな話を聞かれたので、その中で英語で詰まる場面がありましたが、面接が決まってから準備したからといってどうこうできる内容ではなかったかなと思います。それ以外の大学の面接については、時間が比較的短かったこともあり、特に問題なく終了したはずです。覚えている範囲で、面接の内容をまとめます。

大学 面接オファーメールの受信日 面接日 面接官 所要時間 内容
Caltech 1/11 1/14 SoPに書いた研究室のポスドク 約20分 雑談
Cornell 1/12 1/15 SoPに書いた教授 約30分 雑談
MIT 1/21 1/22 SoPに書いていない教授 約75分 研究について突っ込んだ質問を多数
Stanford 1/27 2/2 SoPに書いた教授 約20分 雑談
UCSB 1/31 2/2 SoPに書いた教授 約45分 雑談

雑談はおおよそ、

  • 教授が行ってきた研究の紹介
  • 自分が行ってきた研究・博士課程で行いたい研究
  • こちらから教授への質問

という構成でした。「教授が行ってきた研究の紹介」は、基本的に相手の話を聞くだけです。たまに進行中で未発表の研究内容をさらっと話してくれることがあったので、それについては興味本意でいくつかこちらから質問していました。その後は、「自分が行ってきた研究・博士課程で行いたい研究」について聞かれることが多かったです。SoPに書いたことをベースにしつつ、それに補足を入れたり学会用に作成していたスライドを織り交ぜて話しました。先生方は基本的にSoPやCVに目を通しているようだったので、研究テーマに興味を持った具体的なエピソードや今後取り組みたい研究アイデアなど追加の情報を面接で伝えられると良いのではないかと思います。最後にだいたい「何か質問はあるか?」と聞かれます。3つくらいは事前に質問を用意していると、オドオドしなくて済むでしょう。

さて表からわかるように、MITの面接だけは他の雑談ベースの短い面接とは異なる形式でした(大学というよりは面接を担当する人によるものだとは思いますが)。この面接では、上記の雑談ベースの内容に加えて、

  • 仮に無限の研究リソースを持っていたとしたら、どんな研究がしたいか
  • 共変量シフトの問題を具体例を混えて説明せよ
  • 学部時代の講義で最も面白かったものは何か

など色々聞かれました。MITよりも前に行った面接が軽めのものだったので少々虚を突かれた感じでしたが、事前に想定できる質問でもないので、英語での研究議論の練習だと思ってなんとかこなしました。

CornellやStanfordについては、面接の中で私自身のことを褒めてもらったり、何も突っ込んだ質問をされずあっさり終わったことから、ある程度合格に傾いているのかなと思っていました。がしかし、Cornellからは無事に合格をもらえたものの、Stanfordは不合格になってしまいました。これは、教授から高い評価を得ていたとしても最終的な合否は専攻のAdmission Committeeが決定するためだと思われます(少なくともCSでは)。思い返すと事前コンタクトを取っていた中でも、「君を推薦しようと思うが、最終的にはCommitteeが合否を決定するため保証はできない」と注意書きがされていることが多かったなと思います。教授から気に入ってもらうのは重要だと思いますが、気に入ってもらったからと言って必ず合格するとは限らないようです。

出願結果のまとめ

最後に出願結果をまとめます。まずは、出願時のスペックです。

項目 内容
GPA 教養: 3.73/4.0 専門: 3.15/4.0 総合 3.43/4.0
TOEFL 105点 (R: 29 L: 29 S: 23 W: 24)
GRE 未提出
奨学金 船井情報科学振興財団
研究実績 国際会議主著8本 (機械学習の応用系の学会が中心)

全体的にはあまり見栄えがよくない気がします。研究実績及び志望度合いと研究テーマのマッチ度合いが高い先生とのコネクションという、モチベーションを保つことができ、今後にもつながりそうな項目のみに力を注いだ結果、良くも悪くもこうなりました。研究実績の部分に目につけていただく事が結構あるのですが、出願先によっては内容的にそこまでアドバンテージにならないこともあったので、万人受けするものではなく、ピンポイントで効果的だったというのが実際のところだったかと思います。

次に大学ごとの合否です。

大学名(出願時の志望順) 学科 事前コンタクト*13 面接 結果通知日 合否
Cornell CS あり あり 2/3 合格
Caltech CMS あり あり 3/2 合格
Stanford CS あり あり 2/11 不合格
MIT EECS なし あり 3/11 補欠合格
UC Berkeley EECS なし なし 2/20 不合格
UCSB CS あり あり 2/25 合格
UCSD CS あり なし 1/28 合格
UIUC CS なし なし 3/16 不合格
CMU ML なし なし 2/16 不合格

結果として、4校(+補欠1)からオファーをいただく事ができました*14。特にCornell / Caltech / Stanfordが本命だったので、そのうちCornellとCaltechからオファーをもらえたのは良かったです。この2つの大学については、学会や事前コンタクトで先生に好印象を持ってもらっていたことや単純に研究テーマのマッチ度合いが高かったことが効いたのではないかと思っています。 一方で、効果的なコンタクトが取れていなかった大学には基本受かりませんでした。研究実績は事前コンタクトと相まって初めて威力を発揮するのかなと思います。また全部で9校に出願していましたが、私の場合5~6校の出願に留めておけば十分だったのではないかと今では思います。本命以外の大学に合格したからといって進学したい気持ちになっていたかというと、正直微妙だと思うからです。Cornell / Caltech / Stanfordの内どこからも合格がもらえなかったとしたら、1年後に再挑戦することも視野に入れていたと思います。大学院の出願は基本的にフォームの入力作業なので、出願数が増えれば増えるほど入力それ自体や管理に時間をとられ、その期間に本業の研究等に割ける時間が少なくなってしまいます。もちろん出願校が多いと、推薦状を執筆してくれる方々にも相応の手間をかけてしまいます。とはいえそれらはある程度うまくことが進んだ後だから言える贅沢な結果論ではあるので、とりあえず合格できて一安心です。

出願過程全体のまとめ

出願全体を振り返って、私自身が思う良かった点と悪かった点を簡単に整理します。

良かった点

  • 合格不合格に一喜一憂せず、また準備に躍起になることなく、一定以上の研究コミットを終始保ちながら志望度合いの高い大学に合格できたこと
  • 何人かの先生について、出願過程を通じて今後の研究に繋がるコネクションや印象を残せたこと

悪かった点

  • TOEFL受験や出願フォーム入力など、怠け癖が発動して手をつけ始めるのが遅くなってしまったこと
  • なんとなくの不安にかられ、少々出願しすぎてしまったこと
  • 推薦状の執筆について、推薦者の方々に丸投げしすぎてしまった(こちらの事前準備が足りなかった)こと
  • 出願先の大学の教員を調べ上げ切れていなかったこと(特に助教の先生など)
  • 仮に入学できた場合にどのようなコースワークが待っているか確認していなかったこと

基本的にはこれまでに述べてきたことをまとめただけです。補足するならば、いくつかの大学において出願が終わった後に、事前コンタクトを取ったりSoPに名前を書いておけばよかったなと思う先生が新たに見つかることがありました。出願時点ですでに知っている先生に絞って考えるのではなくて、facultyのリストを網羅的に眺めておけば良かったです。また基本的にはCS専攻に出願していたのですが、私は学部でCSの教育を受けておらず、特に自習もしていないので、合格した後にコースワークの内容を知って「おっとこれは思った以上にヤバいのでは...」と思いました。例えば、CornellのOperations Research専攻Statistics&Data Science専攻などへの出願も考えておけば良かったなと思いました。またMITのSocial & Engineering Systems専攻もちゃんと調べるとCSよりも私にfitしていそうでした。私と似たような分野や境遇で出願を考えている方は、少し視野を広げて調べてみると良いでしょう。

総合的には、多くの方の直接的・間接的なご協力のおかげもあり、概ね狙い通りの出願準備期間を過ごせました。多少研究に割ける時間が少なくなった時期もありましたが、あまり重大なものではなかった気がします。また特段精神的な辛さなどは感じることなく、結果的には完璧ではないにせよ狙ったところに合格できましたし、だからと言って浮かれることなく、この部分の文章を書いている2月中旬も普段と変わらず研究開発や諸々の執筆に取り組めています。細かい反省点もあるにはありますがおそらく人生で1度しかない&すでに終わったことに対してあれこれ言ってもさして意味がないのでしょうから、あまり気にしていません。ただ、これから似た道を目指す人には、効率よく関門を突破できるよううまく情報を活用してもらえたらなと思っていますし、そういう気持ちでこの記事を書いてみました。

進学先を決めるまで

情報収集

さて運良く4校からオファーをいただいたのですが、最後にその中から進学先を決めなければなりません。これが中々大変でした。というのも出願時には、研究内容のマッチ度合いなどからCornellが明確な第一志望だったのですが、先生や学生と話したりより詳しく調べるなどする中で、Caltechへの興味もかなり強まってきていたからです。他の2校の先生や学生とも話をさせていただいたのですが、やはりCornellとCaltechのどちらに進学するかという選択で最終的には悩みました(本当に贅沢な悩みです)。とりあえず私は最終的な決定に役立てるため、2月下旬から4月頭にかけて以下に並べる色々なことを行いました。

  1. 希望する研究室のmtgに参加し、自分の研究発表をさせてもらう
  2. 希望する研究室の先生および学生と1-on-1で雑談させてもらう
  3. 大学の学部が開催するvirtual visitに参加する
  4. 希望する研究室の先生が教える授業を聴講したり、動画を見る
  5. コースワークなど進学した場合に待ち受ける要件を詳細に確認する
  6. 身近な人や先輩の意見を聞く

まずは、希望する研究室の先生に連絡をとって、mtgで研究室のメンバーに対して自分の研究発表をさせてもらえないか頼みました。単純にメンバーや研究室mtgの雰囲気を知りたいというのもあったのですが、せっかくなので今後に繋がるよう自分や自分の研究についての印象を残すために、自ら話題を持ち込む機会を作ろうとしました。どちらの大学を選んだとしても、もう片方の研究室とも今後一緒に研究させていただく可能性があったので、自分のことを相手方の記憶に確実に残しておいてもらいたかったです。このように自分から発表機会を強引に作ることは普段中々できないことなので、いつもは全く持ち合わせていない積極性をここぞとばかりに発揮しました。結果的に相手方のご協力のおかげで、Cornellで2回、Caltechで1回の約1時間の内部発表を行うことができました。3月はありがたいことに他でも招待講演のお話をいただいていたりしたので体力的に大変でしたが、やってよかったです。出願を出願過程としてだけではなくて、今後に繋げられそうな部分はなんでも積極的に活用すると、あとで予期せぬ幸運に繋がってくるのでしょう。さらに個別に博士学生に連絡して、zoomで雑談させてもらう時間を作りました。こちらは研究の話もしつつ、かなりフランクに普段の生活の話やお互いのバックグラウンドの話、先生には直接聞きにくい話などをしました。また3月に各大学が合格した学生向けのオンライン説明会(virtual visit)を開催していたので覗いていました。本当ならon-campusのvisitがありそこで友達もできるらしいので、それに比べると得られるものは少なかったかなと思いますが、コロナの影響なので仕方ないですね。最後に進学した後のコースワークにどのような要件があるのかもちゃんと調べました。ちなみにCornellだとこのページCaltechだとこの資料を参照しました。

これらを通じて、最終的には4月15日までにどこに進学するかを決める必要があります*15。できれば大学のキャンパスや住むことになる街(CornellならIthaca/NY、CaltechならPasadena/CA)に足を運びたかったのですが、それは残念ながら叶いませんでした。

進学先決定の背景

とあれこれしながら悩んでいたのですが、最終的にはCornellに進学することに決めました。

私を含む多くの人が重視するであろう先生との研究テーマのマッチ度合いや先生の人柄、研究室の方針などについてはCornellとCaltechのどちらも遜色なく魅力的な場所に思えました。例えば研究室の方針については、

  • 期待されるpublicationのペースはあるか(大学院では少数の研究に集中したかったので)
  • group meeting以外に研究室で拘束される時間があるか(自分が好きな時間に活動したいので)
  • もう一方の大学と比べてそれぞれの大学の強みは何か(2校で迷っている現状を正直に伝えた上で)

などを先生および数人の学生にそれぞれ確認しましたが、どちらの大学も私の今の考えや性格から外れていないようでした。

一方で、気候を含む生活環境には大きな違いがありました。Caltechのキャンパスが位置するPasadenaはLA近郊の高級住宅街で日本食にも簡単にあり付け、気候も抜群に良いようです。一方でCornellが位置するIthacaはニューヨーク州と言いつつニューヨーク市から車で4~5時間離れた小さな街で、冬は結構寒いようです*16。街を訪問して雰囲気を確認できていたら安心だったのですが、向こう5年以上住む可能性があることを考えると生活環境面でCornellは少しリスキーでした*17

その他の小さな違いとしては、CornellはCS専攻からの合格だったため現状知識もモチベーションもさして持ち合わせていないコースワークに時間を割かねばならない問題がありました。一方Caltechは、CSとは少し違う学際的な専攻に合格していたこともあり、コースワークが比較的自分の興味に合うものでした。基本的に私はその時々で気の向かないものは(一般に取り組んだ方が良いとされているらしくても)意図的に目を背けていて*18、やる気が出るものだけに存分に取り組むようにしているですが、その考えに基づくと最重要ではないにしろコースワークの内容は進学先を迷わせる要因の一つでした。

この迷っている状況を両大学の先生に連絡・相談したところ、Cornellの先生から面談でもメールでも「君には是非Cornellに来て欲しい(粗い要約)」という熱意のこもった勧誘を受けました。一方でCaltechの先生は、とても中立的な立場で進学先決定やキャリアに関するアドバイスをくれました。それはそれでとてもありがたかったのですが、やはりCornellの先生からの言葉の方に心が動きました。この点では、大学全体でみるとCornellの方がCaltechよりも規模が大きいものの、少なくとも自分が進学を考えていた研究室単位で考えるとCornellの先生の研究チームの方が少人数であったことも判断に影響しました。Cornellの先生は私の分野でかなり著名な方だったのですが、その先生に付きっきりに近い環境で共に研究できるのは他のトップ大学でも中々得にくい貴重な環境です。またコースワークにあまり興味がないこともCornellの先生に正直に相談したところ、私の研究分野に関連がある授業を追加で取ることで要件を満たしたことにできないか学科に掛け合ってもらえることになりました。最終的には、仮にその大学を選ばなかったときに失うものの大きさを考え、Cornellへの進学を自信を持って決断しました。

一方で、Caltechのユニークな雰囲気や研究内容にとても強い興味を抱いていたのは紛れもない事実で、いつかCaltechの先生方ともインターンポスドクで一緒に研究させてもらいたいなと思っています。このことはCaltechの先生方にちゃんと伝えさせてもらい、今後も継続して連絡を取らせてもらうことになりました。この辺は積極的に先生と話したり、mtgで自分の研究を発表させてもらえたことで、自分自身の印象をある程度残せたことが良かったのではないかと思っています。

これまでの振り返りとこれから

さてここまで書いてきたように、私としてはかなり思い通りの結果や内容を得ることができました。研究実績や事前コンタクトなど、具体的にどの部分を効果的に進めることができたのかについてはすでに書いた通りです。ただし、もう少し根底として何が良かったのか振り返ってみると「良い結果も悪い結果も全て自分のせいだと捉え、環境やその他の要因のせいにしない」という姿勢を(完璧ではないにせよ)貫けたことなのかなと思っています。「理想的とは思えない環境にいたとしても、自分の行い次第でなんとでもなる」という前向きな気持ちを持ち続けることができたとの言い換えができるかもしれません。

これについて、ちょっとだけ昔話をさせてください。私は日本の端っこで生まれ、そこで高校卒業までの18年間を過ごしました。当時地元には2つの高校があり、その内頭が良い方に進学したのですが*19、それでも偏差値は50未満でした笑。残念ながら予備校などは通える範囲になく、どのくらいの成績の人がどの大学に合格しているのかという身近な指針がない状況です。そのような一見辛い状況下で私は大学受験を経験し、幸運にも現役で合格できました。いかにもよくある「劣悪な環境の田舎から難関大学に受かった私はすごい」的な話の流れですね。私も大学に入学した当初はそのような考えで、都会の進学校や予備校にどこか憧れや羨ましさ、妬みを感じていました。しかし実は今では、大きな町の進学校を選ばずに地元の高校に進む選択をして良かったなと結構本気で思っています。これは単なる私の肌感覚ですが、いわゆる進学校や予備校などに通ってしまうと良くも悪くも手厚いアシストが受けられてしまうために、自力で試行錯誤を繰り返して活路を見出したり、1人で何を信じるべきか決めなければならない場面に遭遇しにくいのかなと周りを見て思うことがあります。一方で私が高校生だった時は、受験に関して頼れる人は周りにおらず、もちろん教科書やセンター試験の範囲なんか授業では終わりません(かと言って予備校もありません笑)。とはいえ環境に文句を言ったところで何も返ってこない状況だったので、結局のところ「どんな結果になったとしてもそれは全て自分自身のこれまでの行いの末に生まれた結果」なのだと自分に言い聞かせて、独力でなんとかしてやるんだという気持ちを持ち続けるしかなかったのです。結果として受験がうまく進んだこともあり、「一見どんなに辛い環境だったとしても、自分自身の行い次第で望ましい結果を得ることができる」という考えが自然と身に付いていたのだと思います。

周りに似た境遇の人がいなかったり、研究ではなく就職志向の人が多く頑張ったら頑張った分だけどこか浮いてしまうような環境の中でも、自分なりのやり方で一応最後までやり遂げた大学院受験の経験は、偶然にも大学受験の時と似ているなと思います。かと言って今更高校の時の厳しい環境に身を投じたいとは自分からは思えないので、強制的にそのようなトレーニングが積める環境に生まれることができたのはかなりの幸運だったなと思いますし、あの時の経験が今となっては大切な財産になっています。

さてこれから進学先でどんな研究をするのかについてうっすらした考えがなくはないのですが、そもそも今の研究分野の勉強を偶然に始めてから3年ほどしか経っておらず、向こう5年ほどで具体的にどんな研究をするのかについては正直あまり深く計画していません。ただ具体的に何に取り組むことになったとしても、これまでと同様、自分の経験や過去の選択、周囲の環境はポジティブな方向で捉え続けたいし、肯定的な経験として発信し続けたいなと思います。これはもちろん自己暗示の意味もありますし、私のささやかな発信や作文がきっかけで誰かが何かをポジティブに捉えられるきっかけになれば嬉しいなという想いもあります。研究に取り組んでいるととどうしても体力的、時には精神的に負荷がかかる場面があるからか、私の周囲でも自分ではどうしようもない事柄に対してどちらかというとネガティブな感情が飛び交っている状況を目にすることがあります。私もそういう感情を抱いてしまうことはあるのですが、せっかく私はこれまでに稀有な経験をさせてもらっているので、これからもそんな"一見ネガティブな環境や状況"に反抗し続けたいなと思っているところです。

さいごに

最後になりました、ここまで脱線しまくりの文章にお付き合いいただきありがとうございます。最近は多くの方が博士課程への出願過程での体験を書き残されており、説明会の動画が公開されることも増えてきました。とてもありがたいことだと思いますし、私も非常に助けられました。ただ、これら既存の情報源の多くは、博士課程の出願が体力的・精神的に厳しいものであることを説いています。もちろんそれはそれぞれにとって正しい話なのだとは思うのですが、厳しい話ばかりだとこれから出願を目指す人のハードルが必要以上に上がってしまったり、気負い過ぎてしまう場合もあるのかなと思います。その中で、出願をもう少し気楽に、またもっと先に繋がる通過点として捉えたポジティブなストーリーが1つくらい存在していても良いんじゃないかと思い、そういうテイストの記事を書きたいと前々から思っていました。そんなポジティブで精神的に辛くない、建設的な出願過程を自分にとって正しい経験にした上で、この記事を書き残すことができて良かったなと思っています。この文章を書くのもとても楽しかったです。あとは皆さんが自分にとってしっくりくる情報源を選択的に参考にしつつ、それぞれの臨み方で準備に励むことになるのでしょう。私の出願に対する臨み方が自分には合わないなと感じた方は、別の情報源を参考にするのが良いのだと思います。とは言いつつ、多くの人に部分的にでも参考にしてもらえたら嬉しいです。

さて冒頭でも少し触れたように、私は今のところその時々で楽しいと思えることに気ままに取り組んでいるだけで、あまり明確な将来のプランとかは持っていません。こんな感じなので数年後に自分がどんな状況に置かれているのか、どんな研究をしているのか、全く予想ができない分とても楽しみです。とりあえずは世界屈指の研究教育機関に属する機会を手にできたので、その中で適度に揉まれつつ、もうちょっと自分が納得して面白いと思える研究や文章や解釈や発表を産み出してみたいものです。

参考リンク

留学に関する具体的な情報は、本記事よりも以下に並べる記事等の方が詳しい場合も多いと思うので、色々見てみると良いでしょう。とはいえ分野ごとに事情が異なる部分があったり人それぞれの経験によって言っていることが違ったりすることが多々あります。結局のところ何が正しいのかは状況によりけりだと思うので、自分の分野と近い分野の方の体験談を参考にしつつ、自分の感覚に合っているものを選んで参考にすれば良いのではないかと思います。ちなみに日本語の情報だけでなく、英語も活用するとより多くの情報にありつけると思います。特に最初に並べているGrad School Resourcesというサイトには、英語で書かれた有用な情報源がまとめられているので、とても便利だと思います。その他英語の情報は実際にadmissionに関わっている先生が書いているものがあり一度目を通しておくと良いでしょう。日本語の記事では特にAkari AsaiさんとKeidai Iiyamaさんの記事がおすすめです。お二方とも受験先の先生方から直接情報を集めるなどしてかなり豊富に客観情報を公開されています。

英語による情報

情報科学

その他

  • 船井情報科学振興財団奨学生の皆さんの報告書: 私もお世話になっている船井情報科学振興財団奨学生の皆さんの留学報告書。皆さん1回目の報告書は受験体験記のような内容になっており参考になります。またその後は大学院での研究や生活面の話が色々綴られており、進学後の情報収集としても役立ちます。
  • 海外大学院受験体験記: 私と同じ2021年度に、Stanford UniversityのAeronautics & Astronautics専攻に合格されたIiyamaさんのブログ。先のAsaiさんの記事同様、単に受け身で出願しただけだと得られないと思われる貴重な情報が掲載されています。私自身受験が終わった後に読ませていただいたのですが、それでも新しい発見がありました。こちらも分野に限らず一度読んでみるべき記事だと思います。
  • アメリカ大学院受験ノウハウ: UCLAChemistry専攻のPhDに進学された方のブログ記事。受験における失敗談や国内大学院の併願に関する内容などが赤裸々に書かれており、他の記事とはまた違った角度の情報が得られます。

また何か良さげな情報源を見つけたら追記するかもしれません。

*1:その頃から具体的に進学を考えていたわけではないですが、ぼんやりとした興味や海外スポーツの観戦が趣味だったことなどから高校生の時は留学ジャーナルなどを興味本位で眺めていた記憶があります。大学1年生の頃からは、船井財団の報告書を読んだり(単純に勉強のモチベーションになりました)大学で開催されていた説明会(ちょうど私が参加した2016年度の動画がありました)に参加してみたりしていました。ということで意識的に情報を集めなければならないことはあまりなく、出願するに当たって最低限必要な知識は常識としてあらかじめ知っている状態ではありました。とは言いつつそんなに昔からTOEFLの準備など具体的な動きをしていたわけではありません。

*2:大学2年時にお試しで受験した時の点数は89点だったと思います。内訳はどこかに消えました。

*3:個人的には1回目と2回目であまり手応えが変わらなかったのにもかかわらず点数に大きな開きがあるため、試験中の出来はあまり気にせず最後まで集中して解いてみることが点数確保の上では大事なのではないかと思います。

*4:東工大はなぜか4.5満点でGPAが付くため、90-100点を4、80-89点を3などとした上で、それを単位数で重み付け平均し、4.0満点のスケールに変換しています。出願時にも同様の変換を適用しました。

*5:それ以外に国際会議に併設されているワークショップでもいくつか論文を発表していましたが、本会議に採択されることとワークショップに採択されることでは難易度や査読の質的にかなり意味が異なってくるので、ワークショップでの発表は実績作りというよりも研究や自分自身の宣伝の意味合いが強かったです。本会議よりも小規模に行われることが多いので、格好のコネクション作りの場として捉えることもできるでしょう。

*6:出願過程で同世代のCVをいくつか見ましたが、学部を卒業した後に何かしらで時間を置いてからPh.Dをスタートしている人がちらほらいました。例えば、他の大学でvisiting scholarとして研究経験を積んだり1年だけインダストリーでエンジニアをしたり、といった具合です。経済学界隈では、postdocならぬpredocという制度もあるらしいです。

*7:最近これで「日本イノベーション大賞・内閣総理大臣賞」という賞を受賞しました。

*8:googleで「statement of purpose machine learning pdf」や「statement of purpose computer science pdf」などと検索すると過去のSoPがいくつか出てきたので、それらの構成をある程度参考にしました。

*9:所属大学の先生、国内他大学の先生、海外大学の先生(日本人、海外PhD)の3人にお願いしました。

*10:またいくつかの大学については、推薦状提出のためのフォームが迷惑メールに入ってしまうことがありました。推薦状を書いていただく方に、ちゃんと出願校全てのフォームが届いているか確認してもらい、届いていない場合は迷惑メールに分類されていないかチェックしてもらうと安心です

*11:奨学金は大学院に合格しそうな人を採択するので、事前コンタクトの進捗度合いを書類で聞いているということは、経験的にそれが最終的な大学院合格と相関しているということなのでしょう。

*12:例えば、こんな感じのページです。

*13:メールを送ってかつ返信が1度以上返ってきたものを「あり」としています。

*14:コロナの影響からか、今年は各大学オファーを出した数が例年と比べて少ない傾向にあったという話を風の噂で耳にしたので、それにしてはかなりうまくいった方なんじゃないかなと。

*15:たいていの場合、合格を伝えるメールに進学するか否かを大学に伝えるためのフォームが含まれます。そのフォームに最終的な決定を記入する期限が(おそらく)どこの大学も4月15日になっています。

*16:北海道出身なので寒さに強い&慣れてるでしょと言われることがありますが、自分から飛び込みたいとは思いません...

*17:生活環境面についてはCaltechとCornellの両方に在学する船井財団の先輩にお話を伺って確認しました。

*18:例えば「GREもoptionalなら別に提出しなくていいや」というのもこの意味で私にとっては割と自然な行動でした。

*19:現在2つの高校は合併し、地元には1つの高校しかないらしいです。少子化というやつですね。

因果推論で検索システムを問い直す(2)

はじめに

ランキング学習のシリーズ記事の第二弾です*1.

前回の記事ではUnbiased Learning-to-Rankと呼ばれる, clickというimplicit feedbackを用いて relevanceに対して最適なスコアリング関数を学習するための損失関数を設計する方法について議論しました. その中で紹介したのがexamination parameter  \theta_kの逆数によって損失を重み付けするInverse Propensity Weighting (IPW)と呼ばれる方法でした.

IPWはclickデータのみから真の損失関数を不偏推定することができるという嬉しさがあった反面, 肝心のexamination parameterの推定方法に関しては Result Randomizationの紹介のみに留まっていました.

本記事では, ユーザー体験を著しく害したり, KPIに大きな打撃をもたらすため実務的にはなかなか行うことができないRandomizaitonではなくて offlineのclickデータからexamination parameterを推定する方法を2つ紹介します.

目次

Unbiased Learning-to-Rankのおさらい

Notationの導入の意味も込めて, 簡単にUnbiased LTRの定式化とIPW損失のおさらいをします. 前回記事を読んでいただいている方は流していただいて大丈夫かと思います.

 \mathcal{L}_{U}=\{(q, d, r) \}を各queryとdocumentにrelevance labelが付与されたデータ集合とします. また, あるqueryとデータ集合において共起しているdocumentの集合を \Omega_{q}=\left\{d |(q, d) \in \mathcal{L}_{U} \right\}で表しておきます.

ここで, ランキングアルゴリズムが最小化したい理想的な損失は次の通りでした.


\begin{aligned}
M=\sum_{(q, d, r) \in \mathcal{L}_{U}} r \cdot f\left(q, d, \Omega_{q}\right)
\end{aligned}


ここで,  fはランキングに関連する関数で, 例えばARPやDCGが用いられます. しかし, 通常はrelevance labelが得られないので, 代わりにより安価に手に入るclickを用いて損失を設計することを考えます.

Position-Based Modelに基づくとrelevanceとclickの関係はexaminationという変数を媒介する形で次のように表せます.


\begin{aligned} 
(1) \quad & C =E \cdot R \\ \\
(2) \quad & \underbrace{ \mathbb{P}(C=1 | q, d, k)}_{Click} =\underbrace{ \mathbb{P}(E=1 | k)}_{Examination} \cdot \underbrace{ \mathbb{P}(R=1 | q, d)}_{Relevance} = \theta_{k} \cdot \gamma_{q, d}
\end{aligned}


ここで, 両辺をexamination parameter  \theta_kで割ることによって右辺にrelevance parameter  \gamma_{q, d}が分離されることを利用して IPW損失は次のように定義されます.


\begin{aligned}
\hat{M}_{I P W} &=\sum_{(q, d, k, c) \in \mathcal{L}} \frac{c}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right)
=\sum_{(q, d, k, c=1) \in \mathcal{L}} \frac{1}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right)
\end{aligned}


IPWに基づいた損失関数 ( \hat{M}_{IPW})は真の損失に対してunbiasedであることが示されるため, 真の損失の代替として正当性を持つという話をしました.

EM Algorithm

 \theta_{k}を推定するための一つ目のアプローチは,  \theta_k \gamma_{q, d}を潜在変数と見てEMアルゴリズムでパラメータを推定するというアプローチです.

Naive EM

まず, パラメータ推定に際して最大化したい対数尤度は次のように表されます.


\begin{aligned}
\log P(\mathcal{L})=\sum_{(q, d, k, c) \in \mathcal{L}} c \log \theta_{k} \gamma_{q, d}+(1-c) \log \left(1-\theta_{k} \gamma_{q, d}\right)
\end{aligned}


 \theta_k \cdot \gamma_{q, d}がclick確率を表すというPBMを思い出せば直感的なはずです.

このまま愚直にE-step, M-stepを書き下すと次のようになります.

E-step: その時点までに得られているパラメータを用いてclickが発生する・しない場合のrelevanceとexaminationの条件付き確率を推定します.


\begin{aligned}
& \mathbb{P}(E=1, R=1 | C=1, q, d, k)=1 \\ 
& \mathbb{P}(E=1, R=0 | C=0, q, d, k)=\frac{\theta_{k}^{(t)}\left(1-\gamma_{q, d}^{(t)}\right)}{1-\theta_{k}^{(t)} \gamma_{q, d}^{(t)}} \\ 
& \mathbb{P}(E=0, R=1 | C=0, q, d, k)=\frac{\left(1-\theta_{k}^{(t)}\right) \gamma_{q, d}^{(t)}}{1-\theta_{k}^{(t)} \gamma_{q, d}^{(t)}}  \\ 
& \mathbb{P}(E=0, R=0 | C=0, q, d, k) = \frac{\left(1-\theta_{k}^{(t)} \right) \left(1-\gamma_{q, d}^{(t)}\right)}{1-\theta_{k}^{(t)} \gamma_{q, d}^{(t)}}
\end{aligned}


M-step: E-stepで推定された条件付き確率を用いて, パラメータを更新します.


\begin{aligned}
& \theta_{k}^{(t+1)}=\frac{\sum_{c, q, d, k^{\prime}} \mathbb{I}_{k^{\prime}=k} \cdot(c+(1-c) P(E=1 | c, q, d, k))}{\sum_{c, q, d, k^{\prime}} \mathbb{I}_{k^{\prime}=k}} \\ \\
& \gamma_{q, d}^{(t+1)}=\frac{\sum_{c, q^{\prime}, d^{\prime}, k} \mathbb{I}_{q^{\prime}=q, d^{\prime}=d} \cdot(c+(1-c) P(R=1 | c, q, d, k))}{\sum_{c, q^{\prime}, d^{\prime}, k} \mathbb{I}_{q^{\prime}=q, d^{\prime}=d}}
\end{aligned}


とEMの更新式を書き下しましたが, 最後の \gamma_{q, d}の更新式で問題が発生します. この更新は, 同じqueryとdocumentのペアについてのデータが一定数存在しないとうまくいきませんが, データ数の少ないペアが大半で更新はあまりうまくいかないと考えられます. また, プライバシーの問題であるqueryについてどのdocumentをclickしたかの情報が手に入らないこともあるらしいです (論文にそう書いてありました.).

Regression-based EM

この \gamma_{q, d}はqueryとdocumentの組み合わせ分だけ存在し, M-stepでの更新がうまくいかない問題に対し, Wang et al. (2018) はRegression-EMと呼ばれるテクニックでこの問題を解消しました.

Regression-EMは, M-stepでのrelevance parameterの推定を一つの学習器で行ってしまおうというアイデアです. 手順の理解には, 擬似コードを見るのが良いと思います.

f:id:usaito:20190525070334p:plain
[Wang et al. (2018)]のAlgorithm 1

擬似コード中の重要な手順の説明をします.

  • (1). 学習器  F(\cdot)を初期化
  • (3). E-step: それまでに得られている \{ \theta_k \}  \{ \gamma_{q, d} \}を用いて条件付きclick確率を推定
  • (4)-(8). E-stepで得られた条件付き確率を用いてrelevance labelをサンプリングし, relevance推定器の学習用のデータを生成
  • (9). 一回前の推定結果とcontextをinputとして, サンプリングしたrelevance labelに対してfit
  • (10)-(11).  \theta_kはNaive EMと同じ式で更新,  \gamma_{q, d}は予測器の出力によって更新

このようにRegression-based EMでは, M-stepにおけるqueryとdocumentの膨大な組み合わせのパラメータ更新式を一つの学習器(論文では, GBDT)で代替することで解決を図っています. 事実, このRegression-based EMを用いることにより前回紹介したResult Randomizationを用いた時よりも良い検索ランキングを提示できるようになったという実験結果が出ました ([Wang et al. (2018)]).

Dual Learning Algorithm

Examination parameter  \theta_kをofflineで推定するもう一つの方法に, Dual Learning Algorithm (DLA)と呼ばれる手法があります. これは, IPWと同じようなアイデアによってExamination parameterの推定のためのunbiasedな損失をclickデータから作れるというアイデアに基づいています.

PBMの仮定のもとで, IPWは次のように両辺を \theta_kで割った形を活用していました.


\begin{aligned}
\frac{\mathbb{P}(C=1 | q, d, k)}{\mathbb{P}(E=1 | k)} = \underbrace{\mathbb{P}(R=1 | q, d)}_{Relevance}
\end{aligned}


[Ai et al. (2018) ]では, これと同じことが両辺を \gamma_{q, d}で割った形にも活用できるよね, というアイデアIRW (Inverse Relevance Weighting)と名付けました.


\begin{aligned}
\frac{\mathbb{P}(C=1 | q, d, k)}{\mathbb{P}(R=1 | q, d)} = \underbrace{\mathbb{P}(E=1 | k)}_{Examination}
\end{aligned}

この操作により, 右辺にexamination parameterを分離できています. 今, examination推定のための真の損失を次のように設定するとします.


\begin{aligned}
M=\sum_{(q, d, e) \in \mathcal{L}_{U}} e \cdot f\left(q, d, \Omega_{q}\right)
\end{aligned}


しかし, ユーザーがdocumentをexamineしたかどうかなんてデータに残っておらず e (Examinationの実現値) がわからないため, この損失は計算不可能です. ここで, 先のIRWを用いると, clickしたかどうかの情報から, Examination parameter推定のための損失に対する不偏推定量を作ることができます.


\begin{aligned}
\hat{M}_{I R W}=\sum_{(q, d, k, c) \in \mathcal{L}_{U}} \frac{c}{\gamma_{q, d}} \cdot f\left(q, d, \Omega_{q}\right)
\end{aligned}


実際, IPWの時と同様にして,


\begin{aligned} 
\mathbb{E}\left[ \hat{M}_{I R W}\right] 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \frac{\mathbb{E} [C ]}{\gamma_{q, d}} \cdot f\left(q, d, \Omega_{q}\right) \\ 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \frac{\theta_{k} \cdot \gamma_{q, d}}{\gamma_{q, d}} \cdot f\left(q, d, \Omega_{q}\right) \\ 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \theta_{k} \cdot f\left(q, d, \Omega_{q}\right) \\ 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \mathbb{P}(E=1 | k) \cdot f\left(q, d, \Omega_{q}\right)
= \mathbb{E}_{E} \left[ M \right] 
\end{aligned}


であることから不偏性が確かめられます.

さて, DLAはこの事実を活用して次のlist-wiseな損失関数をもつ2つの関数 f_{\phi}, \, g_{\psi}を学習します.


\begin{aligned} 
\hat{M}_{I P W}
 & =-\sum_{(q, d, k, c=1) \in \mathcal{L}_{U}} \frac{1}{\theta_{k}} \cdot \log \frac{e^{f_{\phi}\left(x_{q, d}\right)}}{\sum_{d' \in \Omega_{q}} e^{f_{\phi}\left(x_{q, d'}\right)}} \\
\hat{M}_{I R W}
 & =-\sum_{(q, d, k, c=1) \in \mathcal{L}_{U}} \frac{1}{\gamma_{q, d}} \cdot \log \frac{e^{g_{\psi}(k)}}{\sum_{k'} e^{g_{\psi}(k')}}
\end{aligned}


これらの損失を最小化することで,  f_{\phi}, \, g_{\psi}をソフトマックス関数に通すことで, 各パラメータを推定するように学習してほしいという気持ちが込められています.


\begin{aligned} 
\gamma_{q, d}
  \approx \frac{e^{f_{\phi}\left(x_{q, d}\right)}}{\sum_{d' \in \Omega_{q}} e^{f_{\phi}\left(x_{q, d'}\right)}}, \;
\theta_{k}
  \approx \frac{e^{g_{\psi}(k)}}{\sum_{k'} e^{g_{\psi}(k')}}
\end{aligned}


したがって,  f_{\phi}, \, g_{\psi}はお互いの損失の重み付け部分がお互いに依存する形の損失を持っています ( fの損失は \theta_kに依存しており,  gの損失は,  \gamma_{q, d}に依存していますね). これを同時に最適化することにより, end-to-endにExamination parameterの推定と検索ランキング提示のためのスコアリング関数を学習することが可能になります. (ただし, かなり初期値依存が激しそうな印象を持っています)

Dual Learning Algorithmについては以前勉強会(MLPRP)で発表させていただきました. その時のスライドを貼っておきます. 擬似コードや実験結果についてはこちらの資料に掲載してあるので, 参考にしていただけたらと思います.

speakerdeck.com

まとめ

今回は, IPWによって損失を補正するために必要なexamination parameterをofflineで推定する方法を紹介しました. Regression EMなどは推定したいパラメータ数が多い別の問題にも応用できそうな気がしています. 次回は, Position-Based Modelをより現実的なモデル化に拡張した研究について紹介しようと思っています.

参考

[Joachims et al. (2017)]: Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. 2017. Unbiased learning-to-rank with biased feedback. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining (WSDM ’17).
[Wang et al. (2018)]: Xuanhui Wang, Nadav Golbandi, Michael Bendersky, Donald Metzler, and Marc Najork. 2018. Position Bias Estimation for Unbiased Learning to Rank in Personal Search. In Proceedings of the 11th ACM International Conference on Web Search and Data Mining (WSDM ’18).
[Ai et al. (2018)]: Qingyao Ai, Keping Bi, Cheng Luo, Jiafeng Guo, and W. Bruce Croft. Unbiased learning to rank with unbiased propensity estimation. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR’18).

*1:たぶん第三弾まである.

因果推論で検索システムを問い直す(1)

はじめに

ランキング学習のシリーズ記事の第一弾です.

検索システムで達成したいのは, あるqueryに対してよりrelevantなdocumentを上位に提示することです. queryとdocumentのペアに対して, relevanceが大きければ大きいほど, 大きいスコアをつけるような関数を学習することができれば, 効果的にdocumentを並べることができるでしょう. このような関数を学習するためのアルゴリズムがRanking SVMやLambdaMARTなどのランキングアルゴリズムです.

これらのランキングアルゴリズムは, 当然ながら教師ラベルとしてrelevanceを必要とします. 推薦システム的に言えばexplicit feedbackを必要とします. しかし, 学習のたびにannotationするのは高コストなので, clickというimplict feedbackからどうにかスコアリング関数を学習したいというお決まりの動機が湧き上がります. 本記事では, 因果推論で使われる手法を用いてclick情報からrelevance情報を抜き出しつつスコアリング関数を学習する研究を紹介します.

目次

ランキング学習の定式化

さて, ランキング学習を定式化します.  qをquery,  dをdocumentとした時に,  \mathcal{L}_{U}=\{(q, d, r) \}を各queryとdocumentにrelevance labelとして rが付与されたデータ集合とします. このデータ集合は, explicit feedbackとしてrelevanceラベルが得られているのでランキング学習を行うための理想的なデータセットです. また, 便宜上あるqueryとデータ集合において共起しているdocumentの集合を \Omega_{q}=\left\{d |(q, d) \in \mathcal{L}_{U} \right\}で表しておきます.

ここで, Ranking SVMやLambdaMARTなどのランキングアルゴリズムは次の損失関数を最小化することを目指して設計されています.


\begin{aligned}
M=\sum_{(q, d, r) \in \mathcal{L}_{U}} r \cdot f\left(q, d, \Omega_{q}\right)
\end{aligned}


ここで,  fはランキングに関連する関数で, 具体的には次のような損失が用いられることが多いと思います.


\begin{aligned}
A R P &=\sum_{(q, d, r) \in \mathcal{L}_{U}} r \cdot \operatorname{rank}\left(q, d, \Omega_{q}\right) \\ 
D C G &=\sum_{(q, d, r) \in \mathcal{L}_{U}} r \cdot \frac{1}{\operatorname{rank}\left(q, d, \Omega_{q}\right)} 
\end{aligned}


ここで,  \operatorname{rank}\left(q, d, \Omega_{q}\right)は,  d \Omega_qにおける順位を表しています. ARP (Average Relevance Position)は, relevantなdocumentのランキングの総和が小さくなってほしい, DCG (Discounted Cumulative Gain)は, relevantなdocumentのランキングの逆数の総和が小さくなってほしい, という気持ちを反映させています.

これらの損失を具体的にデータから計算できるならば, 最先端のアルゴリズムを用いて効率的にスコアリング関数を学習することができるでしょう. しかし普通そんな理想的な状況*1 はあり得ないので, 次章以降ではより現実的な損失関数の設計方法に関して議論します.

Position-Based Model (PBM)

さて, 現実的には先に定義した \mathcal{L}_{U}のようなexplicit feedbackに基づくデータは得られないはずです. よって, ここからはより現実的なimplicit feedback (click情報) に基づいたデータ集合 \mathcal{L}=\{(q, d, k, c) \}を用いた損失関数の設計方法を考えます. ここで,  k qに対して dを提示した時のpositionを表し,  cはその時にclickが発生したか否かを表します.

さて, ナイーブに考えると既存のアルゴリズムを用いるために, 次のようなrelevanceをclickに入れ替えただけの損失関数を用いることが選択肢の一つとして思いつきます.


\begin{aligned}
\hat{M}_{naive}=\sum_{(q, d, k, c) \in \mathcal{L}} c \cdot f\left(q, d, \Omega_{q}\right)
\end{aligned}


前章で定義した損失関数 Mにおけるrelevanceをclickに入れ替えただけです. しかし, このようなNaive損失をランキングアルゴリズムで最適化してもrelevanceについて最適なランキングを出力するスコアリング関数を得ることはできません. この事実を, 最も単純なclick生成モデルの一つであるPosition-Based Model (PBM)を引き合いに出して説明します.

PBMでは, clickとrelevanceの間に次のような関係性を仮定します.


\begin{aligned} 
(1) \quad & C =E \cdot R \\ \\
(2) \quad & \underbrace{ \mathbb{P}(C=1 | q, d, k)}_{Click} =\underbrace{ \mathbb{P}(E=1 | k)}_{Examination} \cdot \underbrace{ \mathbb{P}(R=1 | q, d)}_{Relevance} = \theta_{k} \cdot \gamma_{q, d}
\end{aligned}


ここで,  Eはexaminationを表す2値確率変数です. このモデル化により, 私たちは次の3つの仮定を置いたことになります.

  1. Queryとdocumentがrelevantかつexaminedのときにのみ, またその時は必ずclickが発生
  2. Relevanceはqueryとdocumentのみに依存し, positionには依存しない
  3. Examinationはpositionのみに依存し, queryとdocumentには依存しない

非常にきつい仮定のように思う一方で, ある程度現実を反映しているかつ単純であるがゆえに思考の整理を助けるモデル化だと思います. このモデル化によって起こる事象を視覚的に説明したのが次の図になります.

f:id:usaito:20190521051747p:plain

この例によると, 1と2番目に提示されたdocumentはexamineされているので, clickはすなわちrelevanceを表しています. 一方で, 9と10番目に提示されたdocumentはもはやexamineされないので, clickはrelevanceを意味しません. つまり, clickされていなくてもrelevantなqueryとdocumentのペアは存在するはずで, 先ほどのナイーブな損失の設計ではそのようなペアの存在を無視してしまうのです.

(この状況ではclickしなかったとしてもそれはirrelevanceを意味しないので, まさにimplicit feedbackといっていい状況でしょう.)

Inverse Propensity Weighting (IPW)

さて, PBMに基づいた議論によりNaive損失を最適化していても, 私たちが本当に得たいスコアリング関数を得ることはできないことがわかりました. しかし, 因果推論の文脈で多用されるInverse Propensity Weighting (IPW)と呼ばれる方法で損失関数を補正することで, 使用可能なデータから真の損失関数をよりよく近似することが可能になります.

IPWに基づいた損失関数は次のように定義されます.


\begin{aligned}
\hat{M}_{I P W} &=\sum_{(q, d, k, c) \in \mathcal{L}} \frac{c}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right)
=\sum_{(q, d, k, c=1) \in \mathcal{L}} \frac{1}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right)
\end{aligned}


つまり, 各データに対する局所損失をそのデータのexamination parameter ( \theta_k)の逆数で重み付けすることで得られる損失関数のことです. また, 損失の最後の表現を見ると,  c=1についてsummationを取っているためimplict feedbackに基づくデータ集合から計算可能であることがわかります. さて, IPWに基づいた損失関数 ( \hat{M}_{IPW})は次のように真の損失に対してunbiasedであることが示されます.


\begin{aligned} 
\mathbb{E}\left[ \hat{M}_{I P W}\right] 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \frac{\mathbb{E} [C ]}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right) \\ 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \frac{\theta_{k} \cdot \gamma_{q, d}}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right) \\ 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \gamma_{q, d} \cdot f\left(q, d, \Omega_{q}\right) \\ 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \mathbb{P}(R=1 | q, d) \cdot f\left(q, d, \Omega_{q}\right)
= \mathbb{E}_{R} \left[ M \right] 
\end{aligned}


よって, IPW損失は少なくともbiasの意味でナイーブな損失を用いるよりも真の損失をよく近似するということがわかります.

補足
試しに, Naive損失の期待値を取ってみると,


\begin{aligned} 
\mathbb{E}\left[ \hat{M}_{naive}\right] 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \mathbb{E} [C ] \cdot f\left(q, d, \Omega_{q}\right) \\ 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \theta_{k} \cdot \gamma_{q, d} \cdot f\left(q, d, \Omega_{q}\right) \\ 
&=\sum_{(q, d, k, c) \in \mathcal{L}} \; \underbrace{ \mathbb{P}(E=1 | k)}_{(a)} \cdot \mathbb{P}(R=1 | q, d) \cdot f\left(q, d, \Omega_{q}\right)
\end{aligned}


ここで, (a)の部分は過去のデータのexamination parameterでrelevance最適化を考える上では不要な重みと言えます. そして, この重みは過去のランキング方策に依存します. なぜなら, examinaiton parameterはdocumentの提示positionのみに依存し, positionはデータが集められたときに走っていたランキング方策によって決められているからです. したがって, Naive損失を用いることはすなわち暗黙のうちに過去のランキング方策に似せるような重みを含んだ損失を最適化していることになります.

Examination Parameterの推定方法

前章では, IPW損失を用いることでNaive損失よりも良い損失関数を設計できることを示しました. しかし, IPW損失を計算するためには,  \theta_kが必要です. そして, このパラメータは残念ながら未知です*2. よって, データから推定する必要があります. 本記事では一番率直な方法として, Result Randomizationと呼ばれる方法を紹介します.

ここで,  \mathcal{R}_kを上位N番目までの提示結果をランダムにしたときに得られた k (\leqq N)番目のpositionのqueryとdocumentの集合とします. このとき,


\begin{aligned} 
\mathbb{E} \left[ C \, | \, k \right] 
&=\int_{q, d \in \mathcal{R}_{k}} \mathbb{E} \left[ C | q, d, k \right]  \, P(q, d) \\ 
&=\int_{q, d \in \mathcal{R}_{k}} \theta_{k} \cdot \gamma_{q, d} \, P(q, d) \\ 
&=\theta_{k} \cdot \int_{q, d \in \mathcal{R}_{k}} \gamma_{q, d} \, P(q, d) \\ 
& \propto \theta_{k} \end{aligned}


したがって, randomizationによって得られたデータにおいてk番目のpositionのclick確率はexamination確率に比例します. よって, IPW損失を計算する前段でResult Randomizationによって得られたデータのclick確率からexamination parameterの比がわかるのでそれを重みづけに使用すれば良いということになります.

補足
とは言え, Result Randomizationなんかできないよ, という方がほとんどだと思います. この点に関しては,

  1. 近日中に, Result Randomizationを経ていないデータからexamination parameterを推定する方法について記事を書く予定です.
  2. 何もやらないよりも, 例えば過去のデータにおいてclickが発生したポジションの逆数でNaive損失を補正するだけでも結果が変わってくると思います. 過去のランキング方策が提示したポジションを保存しましょう!

実験結果

補正がうまくいった結果の例を一つ掲載しておきます. 詳しくは[Joachims et al. (2017)]をお読みください. WSDM2017のBest Paper Awardを受賞した論文です. この論文では, PBMに従う人工データを生成し, Naive損失とIPW損失をそれぞれRanking SVMで最適化したときに得られたスコアリング関数の性能をテストデータにおけるARPで評価しました. 結果は次の通りです.

f:id:usaito:20190521050153p:plain
[Joachims et al. (2017)]のFigure 2

横軸が大きな値をとるほど, Positionごとのexamination確率の変化が激しくなっています. 赤線がIPWによる補正を用いた時のARPですので, 特にexamination確率の変化が激しいときにNaive損失を用いたbaselineを大きく上回っていることがわかります. 実験的にもIPWによる補正は効果的であることがわかる例となっています.

まとめ

本記事では, 因果推論的なアプローチでclickしか得られていないimplicit feedbackデータからrelevanceに対して最適化されたスコアリング関数を得るための損失を設計する方法について書きました. 記事中にも書きましたが, 近日中に補正に必要なexaminaiton parameterをデータから推定する方法についての記事を書こうと思っています. また, 記事中に何か変なことを書いていたらご指摘いただけると幸いです.

参考

[Joachims et al. (2017)]: Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. 2017. Unbiased learning-to-rank with biased feedback. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining (WSDM ’17).
[Wang et al. (2018)]: Xuanhui Wang, Nadav Golbandi, Michael Bendersky, Donald Metzler, and Marc Najork. 2018. Position Bias Estimation for Unbiased Learning to Rank in Personal Search. In Proceedings of the 11th ACM International Conference on Web Search and Data Mining (WSDM ’18).
[Agarwal et al. (2019)]: Aman Agarwal, Xuanhui Wang, Cheng Li, Mike Bendersky, and Marc Najork. 2019. Addressing Trust Bias for Unbiased Learning-to-Rank. In Proceedings of the 2019 World Wide Web Conference (WWW ’19)

*1:全てのqueryとdocumentのペアについてrelevanceが得られている状況

*2:あるポジションに提示したdocumentは何%の確率でexamineされるかを知ることはできません, よね.

統計的学習理論(Rademacher Complexityを用いた期待損失の導出)

はじめに

前回の記事では, 仮説集合 \mathcal{H}が有限である場合の, 仮説 h \in \mathcal{H}の予測損失の上界をHoeffding's ineqを用いて導きました. しかし, 無限仮説集合に対しては同様の方法で実用的な上界を得ることは不可能でした. したがって, 今回は無限仮説集合に対応する方法の一つであるRademacher Complexityを用いて予測損失の上界を導いてみようと思います.

目次

定式化のおさらい

統計的学習理論のモチベーションをおさらいします. 前回記事をお読みいただいている方は読み飛ばしていただいても結構です.

入力空間 \mathcal{X}に値をとる確率変数を X, 入力空間から出力空間 \mathcal{Y}への写像 f: \mathcal{X} \rightarrow \mathcal{Y}としてlabeling functionと呼びます. また, 入力が従う確率分布を Dとします ( X \sim D). 損失関数として \ell: \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}_+を用いるとします. このとき, ある仮説 h: \mathcal{X} \rightarrow \mathcal{Y}の予測損失は次のように定義されます.


\begin{aligned}
R (h) = \mathbb{E}_{ X \sim D } \left[  \ell \left( h(X), f(X) \right) \right]
\end{aligned}


つまり, 分布 Dにおける予測値 h(X)の損失の期待値です.  R(h)をできるだけ小さくするような仮説 hを見つけ出すことが機械学習の目標です.

ここで, データの真の分布 Dは未知であることが問題であり, 有限の観測データから, 予測損失をできるだけ小さくする仮説を導く必要がありました. 予測損失を観測データから評価する上で最も大きな手がかりは経験損失です. データ  \left\{  X_i  \right\}_{i=1}^n が観測されたときの経験損失は次のように定義されます.


\begin{aligned}
\hat{R} (h) = \mathbb{E}_{ X \sim \hat{D} } \left[  \ell \left( h(X), f(X) \right) \right] = \frac{1}{n} \sum_{i=1}^n \ell  \left( h(X_i), f(X_i) \right)
\end{aligned}


ここで,  \hat{D}はデータの経験分布です.

また, 仮説集合 \mathcal{H}に含まれる仮説の中で予測損失と経験損失を最小化するような仮説をそれぞれ  h^* \in \arg \min_{h \in \mathcal{H}} R (h),  \hat{h} \in \arg \min_{h \in \mathcal{H}} \hat{R} (h)と表していました.

ここで私たちが導きたいのは, 観測データから計算できる経験損失を最小化する基準で得られる仮説 \hat{h}の期待損失 R ( \hat{h}) と 仮説集合 \mathcal{H}を用いたときに達成され得る最小の期待損失 R(h ^*)の差を次のように評価することです.


少なくとも 1 - \deltaの確率で次の不等式が成り立つ.


\begin{aligned}
R (\hat{h} ) \leqq   R (h^* ) + complexity \left( \mathcal{H} \right) + confidence ( \delta )
\end{aligned}



以降の目標は, 仮説集合 \mathcal{H}のcomplexity項と \deltaに依存するconfidence項を具体的に求めることです.

Rademacher Complexity

Rademacher Complexityの導入

何度か名前が出てきていますが, 実数値関数の集合の複雑さの指標として解釈されるEmpirical Rademacher ComplexityRademacher Complexityを定義します.

Empirical Rademacher Complexity: 空間 \mathcal{Z}上の実数値関数からなる集合を \mathcal{G} \subset \{ g: \mathcal{Z} \rightarrow \mathbb{R} \}とする. また, 入力点の集合を \mathcal{S} = \{ z_1, ..., z_n \}としする. さらに, 同数の+1と-1を等確率でとる独立な確率変数 (Rademacher variables)を \boldsymbol {\sigma} = \{ \sigma_1, ..., \sigma_n \}とする. このとき, 集合 \mathcal{G}のEmpirical Rademacher Complexityは次のように定義される.


\begin{aligned}
\hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G}) =  \mathbb{E}_{ \boldsymbol {\sigma} } \left[ \sup_{g \in \mathcal{G}} \frac{1}{n} \sum_{i=1}^n \sigma_i g(z_i)  \right]
\end{aligned}


さらに, それぞれのサンプル z_iはある分布 Dに独立に従う( \mathcal{S} \sim D^{n}) とき, 次のRademacher Complexityを定義します.

Rademacher Complexity: 入力点 z_iがある分布 Dに従う確率変数であるとする. また, ある入力点のサンプル集合 \mathcal{S} = \{ z_1, ..., z_n \}が与えられたとする. このとき, 集合 \mathcal{G}のRademacher Complexityは次のように定義される.


\begin{aligned}
\mathfrak{R}_{n } (\mathcal{G}) 
& =  \mathbb{E}_{ S \sim D^n } \mathbb{E}_{ \boldsymbol {\sigma} } \left[ \sup_{g \in \mathcal{G}} \frac{1}{n} \sum_{i=1}^n \sigma_i g(z_i)  \right] \\
& =  \mathbb{E}_{ S \sim D^n }  \left [ \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G})   \right]
\end{aligned}


Rademacher variables  \boldsymbol{ \sigma } \mathcal{S}とは独立にサンプルされます. よって, 入力点とそれに対するランダムなラベル付け (z_1, \sigma_1), ..., (z_n, \sigma_n)を 最大でどれくらい予測できてしまう関数を含むか?を測っていると解釈できます. 入力集合 \mathcal{S}とはなんら無関係なランダムノイズの組みに対してよくfittingできてしまうほど,  \mathcal{G}は複雑である, ということです.

Rademacher Complexityの推定

さて, 定義よりRademacher ComplexityはEmpirical Rademacher Complaxityをデータ集合について期待値をとったものでした. しかし, ある入力点のサンプル集合 \mathcal{S}が与えられたとき, Empirical Rademacher Complexityは必ずしもRademacher Complexityに一致するとは限りません. よって, Rademacher Complexityの推定誤差の裾確率を評価することで, 誤差の大きさを見積もってみようと思います.

Rademacher Complexity vs Empirical Rademacher Complexity: 入力空間 \mathcal{Z}上の実数値関数の集合を \mathcal{G} \subset \{ g: \mathcal{Z} \rightarrow [0, M ] \} とする. このとき, 少なくとも 1 - \delta / 2 ( \delta > 0)の確率で次の不等式が成り立つ.


\begin{aligned}
\mathfrak{R}_{n } (\mathcal{G})  \leqq  \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G}) + M \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  }
\end{aligned}


導出
 g(z_1, ..., z_n) = \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G}) =  \mathbb{E}_{ \boldsymbol {\sigma} } \left[ \sup_{g \in \mathcal{G}} \frac{1}{n} \sum_{i=1}^n \sigma_i g(z_i)  \right]とおきます. このとき,


\begin{aligned}
& | g(z_1, ..., z_i, .., z_n) - g(z_1, ..., z'_i, .., z_n) | \\
& =\mathbb{E}_{ \boldsymbol {\sigma} } \left[ \sup_{g \in \mathcal{G}} \left( \frac{1}{n} \sum_{j=1}^n \sigma_j g(z_j) \right) 
-  \sup_{g \in \mathcal{G}} \left( \frac{1}{n} \sum_{j=1}^n \sigma_j g(z_j) - \frac{1}{n} \sigma_i g(z_i) + \frac{1}{n} \sigma_{i} g(z_i') \right) \right]  \\
& \leqq  \mathbb{E}_{ \boldsymbol {\sigma} } \left[ \sup_{g \in \mathcal{G}} \left( \frac{1}{n} \sum_{j=1}^n \sigma_j g(z_j) \right) 
-  \sup_{g \in \mathcal{G}} \left( \frac{1}{n} \sum_{j=1}^n \sigma_j g(z_j) \right)  + \sup_{g \in \mathcal{G}} \frac{1}{n} |  \sigma_i g(z_i) - \sigma_{i} g(z_i') |   \right]  \\
& =  \mathbb{E}_{ \boldsymbol {\sigma} } \left[ \sup_{g \in \mathcal{G}} \frac{1}{n} |  \sigma_i g(z_i) - \sigma_{i} g(z_i') |   \right]
\leqq \frac{M}{n}
\end{aligned}


ここでは, 関数 gの値域が [0, M]であることとと,  \sigma \in \{-1, +1\}であることを用いました. これにて, 関数 gこちらの記事で導出したMacDiamid's ineqのboundedness conditonを満たすことがわかります. したがって, MacDiamid's ineqで c_i = M / nとおくと, 任意の \epsilon > 0に対して, 次の不等式が成り立つことがわかります.


\begin{aligned}
\mathbb{P} \left(  \mathbb{E} \left [ g ( \mathcal{S} ) \right] -   g ( \mathcal{S} ) \geqq \epsilon  \right) \Leftrightarrow
\mathbb{P} \left(  \mathfrak{R}_{n } (\mathcal{G}) -   \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G}) \geqq \epsilon  \right) \leqq \exp \left( - \frac{ 2 n \epsilon^2 }{M^2} \right)
\end{aligned}


ここで, 左辺を \delta / 2とおくと,


\begin{aligned}
\exp \left( - \frac{ 2 n \epsilon^2 }{M^2} \right) = \frac{\delta}{2} \:  \Leftrightarrow  \: M \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  }
\end{aligned}


です. よって,


\begin{aligned}
\mathbb{P} \left(  \mathfrak{R}_{n } (\mathcal{G}) -   \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G}) \leqq  M \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  } \right) 
>  1 - \frac{\delta}{2}
\end{aligned}


ですので, 所望の不等式を得ます.

Uniform law of large numbers

さて, 前章でRademacher Complexityを導入しました. 本章では, これを用いて次のUniform law of large numbersを導きます.

Uniform law of large numbers: 入力空間 \mathcal{Z}上の実数値関数の集合を \mathcal{G} \subset \{ g: \mathcal{Z} \rightarrow [0, M ] \} とする. また, ある入力点のサンプル集合を \mathcal{S} = \{ z_1, ..., z_n \}とし, 一つ一つのサンプルは独立に zと同じ分布 Dに従うとする. このとき, 少なくとも 1 - \delta ( \delta > 0)の確率で次の不等式が成り立つ.


\begin{aligned}
\mathbb{E} [g (z) ]  \leqq \frac{1}{n} \sum_{i=1}^n g (z_i) + 2  \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G}) + 3 M \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  }
\end{aligned}



導出
まず,


\begin{aligned}
\varphi( z_1, ..., z_n)  = \sup_{g \in \mathcal{G}}  \left( \mathbb{E} [g (z) ]  - \frac{1}{n} \sum_{i=1}^n g (z_i)  \right)
\end{aligned}


と置きます. ここで先ほど同様に \varphi( z_1, ..., z_n)  に対してMacDiamid's ineqを適用します.


\begin{aligned}
\varphi( z_1, ..., z_i, ..., z_n)  - \varphi( z_1, ..., z'_i, ..., z_n)  \leqq   \sup_{g \in \mathcal{G}} \frac{g(z_i) - g(z_i') }{n}  \leqq \frac{M}{n}
\end{aligned}


より,  \varphi( z_1, ..., z_n)はboundedness conditionを満たすので, 少なくとも 1 - \delta / 2の確率で, 次の不等式が成り立ちます.


\begin{aligned}
\varphi( \mathcal{S} )  \leqq \mathbb{E}_{S \sim D^n} \left[  \varphi( \mathcal{S} ) \right] + M \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  }
\end{aligned}


ここで,  \varphi( z_1, ..., z_n) = \varphi( \mathcal{S} ) としました.

次に, 今導いた不等式の右辺の第1項をRademacher Complexityを用いて評価します.


\begin{aligned}
 \mathbb{E}_{S} \left[  \varphi( \mathcal{S} ) \right]  
& =  \mathbb{E}_{S} \left[ \sup_{g \in \mathcal{G}}  \left( \mathbb{E} [g (z) ]  - \frac{1}{n} \sum_{i=1}^n g (z_i)  \right)  \right]   \\
& =  \mathbb{E}_{S} \left[ \sup_{g \in \mathcal{G}}  \left( \mathbb{E}_{S'} \left [ \frac{1}{n} \sum_{i=1}^n g (z'_i)  \right ]  - \frac{1}{n} \sum_{i=1}^n g (z_i)  \right)  \right] \\
& =  \mathbb{E}_{S} \left[ \sup_{g \in \mathcal{G}}  \left( \mathbb{E}_{S'} \left[ \frac{1}{n} \sum_{i=1}^n g (z'_i)   - \frac{1}{n} \sum_{i=1}^n g (z_i)  \right ] \right)   \right] \\
& \leqq \mathbb{E}_{S, S'} \left[ \sup_{g \in \mathcal{G}}  \frac{1}{n} \sum_{i=1}^n (g (z'_i)   -  g (z_i) )    \right] 
\end{aligned}


ここで,  z_i z'_iは同一分布 Dに従います. また,  \sigma_iは+1と-1を等確率でとるRademacher variableです. このとき,  (g (z'_i)   -  g (z_i) )   \sigma_i (g (z'_i)   -  g (z_i) )  は同一分布に従います. よって,


\begin{aligned}
& \mathbb{E}_{S, S'} \left[ \sup_{g \in \mathcal{G}}  \frac{1}{n} \sum_{i=1}^n (g (z'_i)   -  g (z_i) )    \right]  \\
&= \mathbb{E}_{ \boldsymbol{\sigma}, S, S'} \left[ \sup_{g \in \mathcal{G}}  \frac{1}{n} \sum_{i=1}^n \sigma_i (g (z'_i)   -  g (z_i) )    \right] \\
& \leqq \mathbb{E}_{ \boldsymbol{\sigma}, S, S'} \left[ \sup_{g \in \mathcal{G}}  \frac{1}{n} \sum_{i=1}^n \sigma_i g (z'_i)    \right] 
+ \mathbb{E}_{ \boldsymbol{\sigma}, S, S'} \left[ \sup_{g \in \mathcal{G}}  \frac{1}{n} \sum_{i=1}^n - \sigma_i g (z_i)    \right] \\
& = \mathbb{E}_{ \boldsymbol{\sigma}, S} \left[ \sup_{g \in \mathcal{G}}  \frac{1}{n} \sum_{i=1}^n \sigma_i g (z_i)    \right] 
+ \mathbb{E}_{ \boldsymbol{\sigma}, S} \left[ \sup_{g \in \mathcal{G}}  \frac{1}{n} \sum_{i=1}^n  \sigma_i g (z_i)    \right] \\
& = 2 \mathfrak{R}_{n } (\mathcal{G})
\end{aligned}


これらの結果を合わせると, 少なくとも 1 - \delta / 2の確率で次の不等式が成り立ちます.


\begin{aligned}
\sup_{g \in \mathcal{G}}  \left( \mathbb{E} [g (z) ]  - \frac{1}{n} \sum_{i=1}^n g (z_i)  \right) =  \varphi( z_1, ..., z_n)  \leqq 2 \mathfrak{R}_{n } (\mathcal{G}) + M \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  }
\end{aligned}


さらに, 前章の (Rademacher Complexity vs Empirical Rademacher Complexity) の結果を用いると, 少なくとも 1 - \delta / 2の確率で次の不等式が成り立ちます.


\begin{aligned}
 2 \mathfrak{R}_{n } (\mathcal{G}) \leqq 2 \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G})  + 2M \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  }
\end{aligned}


以上の結果を統合し, union boundを用いることで, 少なくとも 1 - \deltaの確率で次の不等式が成り立つことを得ます.


\begin{aligned}
\mathbb{E} [g (z) ]  \leqq \frac{1}{n} \sum_{i=1}^n g (z_i) + 2  \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G}) + 3 M \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  }
\end{aligned}


 L_p損失を用いた時の予測損失の上界

さてようやく本題です. ここでは, 次にように表される L_p損失を用いたときの, 予測損失の確率的上界を導出します.  p \geqq 1で, また損失は定数 M^{p}でboundされるとします.


\begin{aligned}
R (h) = \mathbb{E}_{ X \sim D } \left[  \ell_{p} \left( h(X), f(X) \right) \right] = \mathbb{E}_{ X \sim D } \left[ \left| h(X) -  f(X) \right|^p \right] 
\end{aligned}


ここで,  L_p損失と仮説の合成関数の集合 \mathcal{H}_p = \left\{ x \rightarrow | h(x) - f(x) |^p : h \in \mathcal{H} \right\}のEmpirical Rademacher Complexityを仮説集合 \mathcal{H}のEmpirical Rademacher Complexityで評価します.

まず, 先ほどの集合 \mathcal{H}_pを関数 \phi_p: x \rightarrow |x|^pと集合 \mathcal{H}' = \{x \rightarrow h(x) - f(x): h \in \mathcal{H} \}を用いて,  \mathcal{H}_p = \{ \phi_p \circ  \mathcal{H}' \}と表しておきます. 関数 \phi_pは,  pM^{p-1}-Lipschitzなので, Talagrand's lemma*1を用いると,


\begin{aligned}
 \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{H}_p) \leqq  pM^{p-1}  \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{H}')
\end{aligned}


が成り立ちます. また,


\begin{aligned}
 \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{H}') 
& = \mathbb{E}_{ \boldsymbol {\sigma} } \left[ \sup_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \sigma_i (h(x_i) - f(x_i))  \right] \\
& \leqq \mathbb{E}_{ \boldsymbol {\sigma} } \left[ \sup_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \sigma_i h(x_i)   \right] 
+ \underbrace{ \mathbb{E}_{ \boldsymbol {\sigma} } \left[ \sup_{h \in \mathcal{H}} \frac{1}{n} \sum_{i=1}^n \sigma_i f(x_i)   \right]}_{= 0} \\
& =  \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{H}) 
\end{aligned}


したがって, 結局のところ


\begin{aligned}
 \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{H}_p) \leqq  pM^{p-1}  \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{H})
\end{aligned}


なので,  L_p損失と仮説集合の合成関数の集合のEmpirical Rademacher Complexityは, 仮説集合のEmpirical Rademacher Complexityで上から評価できます. この事実と, Uniform law of large numbersにおいて,  \mathcal{G} \mathcal{H}_pとすれば, 任意の仮説 h \in \mathcal{H}に対して, 少なくとも 1 - \deltaの確率で次の不等式が成り立ちます.


\begin{aligned}
R (h) -  \hat{R} (h) = & \mathbb{E}_{X \sim D} [ \ell_{p} (h(X),  f(X ))  ] - \frac{1}{n} \sum_{i=1}^n \ell_{p} (h(X_i),  f(X_i)) \\
&  \leqq   2pM^{p-1}  \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{G}) + 3 M^p \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  }
\end{aligned}


この不等式を用いれば, 少なくとも 1 - \deltaの確率で次の不等式が成り立つことを導くことができます.


\begin{aligned}
R (\hat{h} ) -   R (h^* ) 
& =  R (\hat{h} ) -   \hat{R} (\hat{h} ) + \underbrace{ \hat{R} (\hat{h} )  - \hat{R} (h^* ) }_{ \leqq 0 } + \hat{R} (h^*) -  R (h^* )  \\
& \leqq R (\hat{h} ) -   \hat{R} (\hat{h} ) +  \hat{R} (h^*) -  R (h^* )  \\
& \leqq 2 \sup_{h \in \mathcal{H}} \left| \hat{R} (h) -  R (h) \right| \\
& \leqq 2 \left(  2pM^{p-1}  \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{H}) + 3 M^p \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  }  \right)
\end{aligned}


したがって, 所望の確率的上界を次のように得ることができました.


\begin{aligned}
R (\hat{h} )  \leqq  R (h^* )  + \underbrace{ 4 pM^{p-1}  \hat{\mathfrak{R}}_{ \mathcal{S} } (\mathcal{H})}_{complexity}
+   \underbrace{ 6 M^p \sqrt {  \frac{ \log \frac{2}{ \delta } }{ 2n }  } }_{confidence}
\end{aligned}


さいごに

本記事では,  L_p損失を用いた場合の予測損失の確率的上界をRademacher Complexityを用いて導出してみました. 相変わらず, 私の誤解で誤った記述をしている可能性が大いにありますので, 見つけた場合はご指摘いただけたら幸いです.

参考

[金森 (2015)] 金森敬文. 2015. 統計的学習理論. 講談社 機械学習プロフェッショナルシリーズ.
[Mohri et al. (2012)] Mohri, M.; Rostamizadeh, A.; and Talwalkar, A. 2012. Foundations of Machine Learning. MIT Press.

*1:Mohri et al. (2012)のlemma 4.2

統計的学習理論(有限仮説集合の場合の予測損失の上界)

はじめに

最近自身の研究で使うため統計的学習理論の勉強をしています. 2回に渡って基本的な内容をまとめてみます.

目次

定式化

まず, 統計的学習理論のモチベーションを述べます. 入力空間 \mathcal{X}に値をとる確率変数を X, 入力空間から出力空間 \mathcal{Y}への写像 f: \mathcal{X} \rightarrow \mathcal{Y}としてlabeling functionと呼ぶことにします. また, 入力が従う確率分布を Dとします ( X \sim D). 損失関数として \ell: \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}_+を用いるとします. このとき, ある仮説 h: \mathcal{X} \rightarrow \mathcal{Y}の予測損失は次のように定義されます.


\begin{aligned}
R (h) = \mathbb{E}_{ X \sim D } \left[  \ell \left( h(X), f(X) \right) \right]
\end{aligned}


つまり, 分布 Dにおける予測値 h(X)の損失の期待値です.  R(h)をできるだけ小さくするような仮説 hを見つけ出すことが目標です.

ここで, 予測損失 R(h)がわかっていれば, 問題は随分簡単になるのですが, 残念ながらデータの真の分布 Dは未知です. よって, 有限の観測データから, 予測損失をできるだけ小さくする仮説を導く必要があります. 予測損失を観測データから評価する上で最も大きな手がかりは経験損失です. データ  \left\{ X_i \right\}_{i=1}^n が観測されたときの経験損失は次のように定義されます.


\begin{aligned}
\hat{R} (h) = \mathbb{E}_{ X \sim \hat{D} } \left[  \ell \left( h(X), f(X) \right) \right] = \frac{1}{n} \sum_{i=1}^n \ell  \left( h(X_i), f(X_i) \right)
\end{aligned}


ここで,  \hat{D}をデータの経験分布としました. これは, データ数が nのときに, 確率 1 / nで各観測データ X_iの値をとるような分布のことです.

 \mathcal{H} = \{h_1, h_2, ..., h_{} \}をある有限な仮説集合とします. このとき, この仮説集合に含まれる仮説の中で予測損失と経験損失を最小化するような仮説をそれぞれ h^*, \hat{h}と表しておきます.


\begin{aligned}
h^* \in \arg \min_{h \in \mathcal{H}} R (h), \quad \hat{h} & \in \arg \min_{h \in \mathcal{H}} \hat{R} (h)
\end{aligned}


 \hat{h}は, Empirical Risk Minimizerと呼んだりもします.  h^*, \hat{h}について, 定義より次の2つの不等式が成り立ちます.


\begin{aligned}
R (h^* )  \leqq R( \hat{h} ), \quad \hat{R} (\hat{h})  \leqq  \hat{R} (h^*)
\end{aligned}


ここで私たちが導きたいのは, 観測データから計算できる経験損失を最小化する基準で得られる仮説 \hat{h}の期待損失 R ( \hat{h}) と 仮説集合 \mathcal{H}を用いたときに達成され得る最小の期待損失 R(h ^*)の差を次のように評価することです.


少なくとも 1 - \deltaの確率で次の不等式が成り立つ.


\begin{aligned}
R (\hat{h} ) \leqq   R (h^* ) + [extra \: term]
\end{aligned}



次章では, 仮説集合 \mathcal{H} \deltaに依存する [extra term]を具体的に求めます.

有限仮説集合の場合の予測損失の上界の導出

さて, 本記事で考えている仮説集合 \mathcal{H}は有限でした. またここでは , 損失関数 \ellがある定数 Mで上からboundできるとします (例えば, 01-lossの場合は,  M=1). この場合, こちらの記事で紹介したHoeffding's ineqを用いて R (\hat{h} )  R (h^* )の差を評価することができます.

まず,


\begin{aligned}
R (\hat{h} ) -   R (h^* ) 
& =  R (\hat{h} ) -   \hat{R} (\hat{h} ) + \underbrace{ \hat{R} (\hat{h} )  - \hat{R} (h^* ) }_{ \leqq 0 } + \hat{R} (h^*) -  R (h^* )  \\
& \leqq R (\hat{h} ) -   \hat{R} (\hat{h} ) +  \hat{R} (h^*) -  R (h^* )  \\
& \leqq 2 \max_{h \in \mathcal{H}} \left| \hat{R} (h) -  R (h) \right|
\end{aligned}


ここで, 右辺の裾確率をunion boundとHoeffding's ineqを用いて次のように評価します. 途中で係数2が登場しているのは, 誤差の絶対値を評価するため両側の裾確率を考慮しているからです.


\begin{aligned}
& \mathbb{P} \left( 2 \max_{h \in \mathcal{H}} \left| \hat{R} (h) -  R (h) \right|  \geqq \epsilon  \right) \\
& \leqq \sum_{h \in \mathcal{H}} \mathbb{P} \left( \left| \hat{R} (h) -  R (h) \right| \geqq \epsilon / 2 \right) \\
&  \leqq  \sum_{h \in \mathcal{H}} 2 \exp \left( - \frac{n \epsilon^2} {2M^2} \right) \quad \because Hoeffding's \,  ineq \\
& = 2 | \mathcal{H} | \exp \left( - \frac{n \epsilon^2} {2M^2} \right)
\end{aligned}


右辺を \deltaと置いて \epsilonについて解けば,


\begin{aligned}
2 | \mathcal{H} | \exp \left( - \frac{n \epsilon^2} {2M^2} \right) = \delta \Leftrightarrow \epsilon = M \sqrt {  \frac{2}{n} \log \frac{2 | \mathcal{H}| }{ \delta}  }
\end{aligned}


よって,


\begin{aligned}
\mathbb{P} \left( 2 \max_{h \in \mathcal{H}} \left| \hat{R} (h) -  R (h) \right|  \geqq M \sqrt {  \frac{2}{n} \log \frac{2 | \mathcal{H}| }{ \delta}  }  \right)  \leqq  \delta
\end{aligned}


なので, 少なくとも 1 - \deltaの確率で次の不等式が成り立ちます.


\begin{aligned}
2 \max_{h \in \mathcal{H}} \left| \hat{R} (h) -  R (h) \right|  \leqq M \sqrt {  \frac{2}{n} \log \frac{2 | \mathcal{H}| }{ \delta}  }
\end{aligned}


以上の結果を統合すると, 最終的な目標であった次の不等式が少なくとも 1 - \deltaの確率で成り立つという結果を得ます.


\begin{aligned}
R (\hat{h} ) \leqq   R (h^* )  + M \sqrt {  \frac{2}{n} \log \frac{2 | \mathcal{H}| }{ \delta}  }
\end{aligned}


したがって, 仮説集合 \mathcal{H}が有限である場合,  R ( \hat{h} )  R (h^* )に 少なくとも \mathcal{O}_p \left( \sqrt{ \log | \mathcal{H} |  / n } \right) で収束することがわかります.

さいごに

今回は, 仮説集合が有限な場合の \hat{h}の予測損失の上界をHoeffding's ineqを用いて導出しました. しかし, 今回導いた上界は仮説集合が無限である場合 (i.e.,  |\mathcal{H}| = \infty) 実用的ではありません. (上界の第2項を見れば一目瞭然.) よって, 次はRademacher Complexityという仮説集合の複雑さの指標を用いて仮説集合が無限の場合も意味を成す期待損失の上界を導いてみます.

参考

[金森 (2015)] 金森敬文. 2015. 統計的学習理論. 講談社 機械学習プロフェッショナルシリーズ.
[Mohri et al. (2012)] Mohri, M.; Rostamizadeh, A.; and Talwalkar, A. 2012. Foundations of Machine Learning. MIT Press.

多腕バンディットアルゴリズムのリグレット解析

はじめに

活用と探索をいい具合にバランスしつつ, 報酬を最大化することを目標とする多腕バンディット問題は, web広告の最適化などへの応用が期待されることから大きな注目を集めています. この分野に関してはこれまでにいくつかの素晴らしい記事が存在しますが, その理論解析に踏み込んだものはありませんでした. 本記事では, 有名なアルゴリズムを例にして, バンディットアルゴリズムの理論解析の雰囲気をさらってみます.

目次

定式化

まずは(確率的)多腕バンディット問題を定式化します. 定式化に関しては, こちらの記事で非常にわかりやすくまとめられているため, ここでは簡単に記述します.

多腕バンディット問題では, playerに対してarmと呼ばれるいくつかの行動の選択肢が与えられます. 各armは報酬と呼ばれる未知の確率分布に従う確率変数と対応付けられています. playerは, 各時刻にいずれかのarmを選択してそのarmに紐づく報酬の実現値を観測します. このような試行を繰り返すうちに, 各armの報酬が従う確率分布のパラメータを推定(探索)しながら, 同時に得られる報酬を最大化すること(活用)がplayerの目標です.

今, armの集合を \mathcal{A} = \{1, ..., a , ..., K \}とし, ある時刻 tにあるarm  aから観測される報酬は, 区間 [0, 1]に値をとる確率変数 X_{a, t}に独立に従うとします. また, arm  aを選択することで得られる期待報酬を \mathbb{E} \left[ X_{a, t} \right] = \mu_{a} と表記します.

このとき, 多腕バンディット問題では次のように定義される期待累積リグレット(以降, リグレット)を考えます.


\begin{aligned}
R (T) 
& = \mathbb{E} \left[ \max_{a \in \mathcal{A}} \sum_{t = 1}^T  X_{a, t} - X_{a(t), t}  \right] \\
& =  \sum_{a = 1}^K \Delta_{a} \mathbb{E} \left[ T_a \right]
\end{aligned}


ここで, 総試行回数を T, 時刻 tにおいて選択されるarmを a(t), 最適なarmとの期待報酬のgapを \Delta_a , 全ての試行が終了した時点においてarm  aを選択した回数を T_aとしました. リグレットは, 最適な固定戦略  a^{*} = \arg \max_{ a \in \mathcal{A}} \mu_{a} を取ることで得られる期待累積報酬と playerの取る戦略  \{ a(t) : t = 1, 2, ..., T \} によって得られる期待累積報酬の差の合計だと解釈できます. これは, 達成し得た最大の報酬からの後悔の量と言えるのでリグレットと名付けられています.

playerはリグレット R(T)を最小化することを目指します. また, armの選択を出力するアルゴリズム (player) が達成するリグレットの上界を導出することが主要な理論的興味になります. ちなみにLai et al. (1985)によると, 期待リグレットの理論限界は \Omega (\log T)であることが知られており, アルゴリズムにはこの理論限界を達成していて欲しいということになります.

Upper Confidence Boundアルゴリズム

多腕バンディット問題の中でとてもよく知られたアルゴリズムに, Upper Confidence Bound (UCB) アルゴリズムというものがあります. これは, ある時刻においてそれまでに観測された報酬によって推定される期待報酬の上側信頼区間が最大になるarmを選択するアルゴリズムになります. 上側信頼区間を推定する際の有意水準は時刻 tに対して t^{- \alpha}程度に設定されることが多いので今回はそれに従います.

期待報酬の上側信頼区間が最大になるarmを選択するという方針の解釈は決して難しくないと思いますが, 具体的なアルゴリズムはどのように構成すれば良いのでしょうか? 実は, 以前の記事で紹介したHoeffding's ineqを活用することでこの方針を実現するアルゴリズムを導くことができます.

ここで, 時刻 tの試行が終了した時点においてarm  aを選択した回数を T_{a, t}として, 時刻 tにおける選択前までの観測報酬を用いて各armの期待報酬の推定量を次のように構築します. と言っても, ただ観測報酬を平均しているだけです.


\begin{aligned}
\hat{\mu}_{ a, T_{a, t - 1} } = \frac{1}{ T_{a, t - 1} } \sum_{s=1}^{t-1} \mathbb{I} \{ a(t) = a \} X_{a, s}
\end{aligned}


この推定量が真の期待報酬 \mu_aを大きく過小評価してしまう確率はHoeffding's ineqを用いて次のように評価できます.


\begin{aligned}
\mathbb{P} \left( \mu_a - \hat{\mu}_a \geqq \epsilon \right) \leqq  \exp \left( - 2 T_{a, t - 1} \epsilon^2 \right)
\end{aligned}


右辺を t^{-\alpha}とおいて変形を加えると,


\begin{aligned}
\mathbb{P} \left( \mu_a < \hat{\mu}_a +  \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t - 1}}  } \right) > 1 - t^{- \alpha}
\end{aligned}


よって, Hoeffding's ineqを用いることにより各armの有意水準 t^{- \alpha}での上側信頼区間の上界を得ることができました. これに従い, UCBアルゴリズムは次のように定義されるUCBスコアが最大になるようなarmを各時刻において選択するようなアルゴリズムになっています.


\begin{aligned}
UCB_{a, t} = \hat{\mu}_a +  \sqrt{ \frac{\alpha \log (t - 1)}{2 T_{a, t - 1}} }
\end{aligned}


擬似コードは次の通りです.

f:id:usaito:20190501053314p:plain

リグレット上界の導出

さて, 本章では前章で紹介したUCBアルゴリズムが達成するリグレットの上界を導きます. しかしここでは, UCBアルゴリズムが理論限界を達成することを示すため簡易なリグレット上界の導出を採用します.

以降一般性を失うことなく,  a^* = 1であるとします. armの期待報酬の推定が大きく外れる場合とそうでない場合に場合分けする方針をとります. まず, 次の2つの事象 A_t B_tを考えます.

  •  A_t:  \hat{\mu}_{ a, T_{a, t} } \leqq \mu_a +  \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} }
  •  B_t:  \hat{\mu}_{ 1, T_{1, t} } \geqq \mu_1 -  \sqrt{ \frac{\alpha \log (t)}{2 T_{1, t}} }

つまり,  A_tは時刻 tにおけるあるarmの期待報酬の推定がそこまで大きくならないという事象のこと.  B_tは時刻 tにおける最適なarmの期待報酬の推定がそこまで小さくならないという事象のことです. まず,  A_tの補事象が起こる確率を評価します.


\begin{aligned}
\mathbb{P} \left( A_t^c \right) 
& = \mathbb{P} \left(  \hat{\mu}_{ a, T_{a, t} } -  \mu_a  >   \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} } \right) \\
& \leqq t^{- \alpha} \quad \because Hoeffding's \: ineq 
\end{aligned}


同様に,  \mathbb{P} \left( B_t^{c} \right) \leqq  t^{- \alpha}  です. よってunion boundを用いれば,


\begin{aligned}
\sum_{t = 1}^T  \mathbb{E} \left[ \mathbb{I} \{ A_t^c \cup B_t^c \} \right]  
& \leqq \sum_{t = 1}^T \left(  \mathbb{E} \left[ \mathbb{I} \{ A_t^c \} \right] + \mathbb{E} \left[ \mathbb{I} \{ B_t^c \} \right]   \right) \\
& \leqq 2 \sum_{t = 1}^T t^{- \alpha} \\
& \leqq  2 \left( 1 + \int_1^{\infty} x^{-\alpha} dx \right)  \\
& = \frac{2 \alpha}{\alpha - 1}
\end{aligned}


です.

次に, 事象 A_t, B_tが共に成り立つ場合を考えます. まず, 最適ではないarmが選択されるのは, 次の不等式が成り立つ場合です.


\begin{aligned}
\hat{\mu}_a +  \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} } > \hat{\mu}_1 +  \sqrt{ \frac{\alpha \log (t)}{2 T_{1, t}} }
\end{aligned}


今, 事象 A_tが成り立っているので, 両辺に \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} }を足せば,


\begin{aligned}
\hat{\mu}_{ a, T_{a, t} } + \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} } \leqq \mu_a +  \sqrt{ \frac{2 \alpha \log (t)}{ T_{a, t}} }
\end{aligned}


です. これを用いれば,


\begin{aligned}
\mu_1 
&  \leqq \hat{\mu}_{ 1, T_{a, t} } +  \sqrt{ \frac{\alpha \log (t)}{2 T_{1, t}} } \quad \because B_t \\
& \leqq  \hat{\mu}_a +  \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} }  \\
& \leqq \mu_a +  \sqrt{ \frac{2 \alpha \log (t)}{ T_{a, t}} }
\end{aligned}


です.  T_{a, t}について整理すると,


\begin{aligned}
T_{a, t}  \leqq 2 \Delta_a^{-2} \log (t) \leqq  2 \Delta_a^{-2} \log (T) 
\end{aligned}


を得ます. 最終的には,


\begin{aligned}
\mathbb{E} \left[ T_a \right] 
& \leqq  2  \left (   \Delta_a^{-2} \log (T)  +  \frac{\alpha}{\alpha - 1}\right)
\end{aligned}


よって,


\begin{aligned}
R(T)
& = \sum_{a \neq 1} \Delta_{a} \mathbb{E} \left[ T_a \right] \\
&=  \sum_{a \neq 1} \Delta_{a} \left(  \mathbb{E} \left[ \mathbb{I} \{ A_t \cap B_t \} \right]   +  \mathbb{E} \left[ \mathbb{I} \{ A_t^c \cup B_t^c \} \right]  \right) \\
& \leqq  2 \sum_{a \neq 1}   \left (   \frac{ \log (T) }{\Delta_a } +  \frac{\alpha}{\alpha - 1} \Delta_a \right)
\end{aligned}


というリグレットの上界が導かれます. これによりUCBアルゴリズムのリグレット上界は悪くても \mathcal{O} (\log T)のオーダーです. Lai et al. (1985)における理論限界は \Omega(\log T)でしたので, UCBアルゴリズムは理論限界と同様のオーダーを達成することがわかりました.

さいごに

今回は, 単純にarmの報酬のみから次に選択するarmを出力するようなアルゴリズムを構成する問題を扱いました. しかし, 実際のweb広告などではuserやarmのcontextに報酬の確率分布のパラメータが依存すると考えるのが自然です. このようなcontextに依存するような問題設定を文脈付きバンディット問題などと呼びます. 文脈付きバンディット問題に関しては, 以前Qiitaに紹介記事を書きましたが, 理論解析には触れられていませんでした. 近いうちに本ブログで, 文脈付きバンディット問題の理論にも触れたいと思っています.

また毎度のことですが, 私の誤解で誤った記述をしてしまっている可能性が大いにあります. 誤りを見つけた場合はご指摘いただけると幸いです.

参考

[Jamison (2017)] Kevin Jamieson. Stochastic Multi-armed bandits, regret minimization. URL: https://courses.cs.washington.edu/courses/cse599i/18wi/resources/lecture3/lecture3.pdf
[Lai et al. (1985)] T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math., 6(1):4–22, March 1985.
[本多, 中村 (2016)] 本多淳也, 中村篤祥. バンディット問題の理論とアルゴリズム. 講談社 機械学習プロフェッショナルシリーズ, 2016.

有用な確率不等式のまとめ

はじめに

機械学習に関連する諸分野では何かしらの統計量(期待判別誤差やリグレットなど)を上から評価したい場面が多くあります. そのような場面で大活躍するのが確率不等式と呼ばれる不等式の数々です. 今後本ブログでもこれらの不等式を多用することが予想されるため, 一度まとめておきます. いくつかの不等式は証明もします. 証明は, MLPシリーズの『統計的学習理論』のAppendix Aを参考に, 自分なりに行間を埋めてみました.

目次

Jensen's inequality

まず, 凸関数の定義を確認します.

凸関数: 関数 f: \mathbb{R}^d \rightarrow (- \infty, \infty ] が, 任意の {\bf x}, {\bf y} \in \mathbb{R}^d と任意の \alpha \in [0, 1]に対して,


\begin{aligned}
f (\alpha {\bf x} + (1 - \alpha) {\bf y}) \leqq \alpha f ({\bf x}) + (1 - \alpha) f({\bf y})
\end{aligned}

を満たす時,  fを凸関数という.


ここで, 以降のHoeffding's ineqの証明などでも用いられる期待値演算にJensen's ineqを適用した形を紹介します.

Jensen's Inequality:  Xを有限な期待値を持つ確率変数とする.  f(x) Xの値域を含む区間において凸な関数とする. この時, 次の不等式が成り立つ.


\begin{aligned}
f \left( \mathbb{E} \left[ X \right] \right) \leqq \mathbb{E} \left[ f(X)  \right]
\end{aligned}

Markov's inequality / Chebyshev's inequality

ここでは, Markov's ineqとChebyshev's ineqを紹介します. これらは統計学の教科書にもだいたい掲載されていると思います.

Marcov's Inequality: 非負確率変数 Xと任意の \epsilon > 0, p > 0に対して, 次の不等式が成り立つ.

\begin{aligned}
\mathbb{P} \left( X \geqq \epsilon \right) \leqq \frac{ \mathbb{E} \left[  X^p \right] }{\epsilon^p}
\end{aligned}


導出


\begin{aligned}
\epsilon^p \mathbb{P} \left( X \geqq \epsilon \right) 
& = \epsilon^p \int_{ X \geqq \epsilon } f(x)dx\\
& =  \int_{ X \geqq \epsilon } \epsilon^p f(x)dx\\
& \leqq  \int_{ X \geqq \epsilon } X^p f(x)dx \\
& \leqq \mathbb{E} \left[  X^p \right]
\end{aligned}



特に,  X | Z - \mathbb{E} [ Z ] |,  p=2と置いた時の形をChebyshev's ineqと呼びます. この不等式は, 確率変数 Zがその期待値から大きく外れた値をとる確率を分散を用いて評価しています.

Chebyshev's inequality: 確率変数 Zと任意の \epsilon > 0に対して, 次の不等式が成り立つ.

 
\begin{aligned}
\mathbb{P} \left( |Z - \mathbb{E} [ Z ] | \geqq \epsilon \right) \leqq \frac{ \mathbb{V} \left[  Z \right] }{\epsilon^2}
\end{aligned}

Hoeffding's inequality

ここで紹介するHoeffding's ineqは機械学習の論文で頻出なので, かなり重要です. これを示す前に, 一つ補題 (Hoeffding's lemma) を示します.

Hoeffding's lemma: 確率変数 X \mathbb{E} [X ] = 0,  a \leqq X \leqq bを満たすとき, 任意の s > 0に対して, 次の不等式が成り立つ.


\begin{aligned}
\mathbb{E} \left[ \exp (sX) \right] \leqq \mathbb{E} \left[ \exp \left( \frac{s^2 (b - a)^2}{8} \right) \right]
\end{aligned}


導出
 a \leqq x \leqq bを満たすような xについて,  0 \leqq \lambda \leqq 1を次のように置きます.


\begin{aligned}
\lambda = \frac{b - x}{b - a}
\end{aligned}


これを変形すると,  sx = s \lambda a + (1 - \lambda)bです.  \exp(\cdot)は凸関数なので,


\begin{aligned}
e^{sx} = e^{s \lambda a + (1 - \lambda)b} \leqq \lambda e^{sa} + (1 - \lambda) e^{sb} = \frac{b - x}{b - a} e^{sa} + \frac{x - a}{b - a} e^{sb}
\end{aligned}


両辺の期待値をとると,


\begin{aligned}
\mathbb{E} \left[ e^{sX} \right] = \mathbb{E} \left[ \frac{b - X}{b - a} e^{sa} + \frac{X - a}{b - a} e^{sb} \right] = \frac{b }{b - a} e^{sa} - \frac{a}{b - a} e^{sb}
\end{aligned}


 Xの期待値が0であることを用いました. ここで,  p = - a / (b - a)と置くと,  1 - p = b / (b-a)なので,


\begin{aligned}
\frac{b }{b - a} e^{sa} - \frac{a}{b - a} e^{sb} = (1 - p) e^{sa} + p e^{sb}
\end{aligned}

と表されます. また,  u = s(b - a)と置き,  uについての関数 \phi (u)を次のように定義しておきます.


\begin{aligned}
 & (1 - p) e^{sa} + p e^{sb}  = pe^{(1 - p)u} + (1 - p)e^{-pu} \\
& \phi (u)  = \log \left( pe^{(1 - p)u} + (1 - p)e^{-pu} \right)
\end{aligned}


このとき,


\begin{aligned}
\phi(0)  & = \log \left(p - (1 - p) \right) =  0 \\
\phi'(0) & = 0 \quad \left( \phi'(u) = -p + \frac{p e^u}{1 - p + p e^u}  \right) \\
\phi'' (u) & = \frac{1 - p}{1 - p + pe^u} \cdot \frac{pe^u}{1 - p + pe^u}  \\
& = \frac{1 - p}{1 - p + pe^u} \cdot \left( 1 - \frac{1 - p}{1 - p + pe^u} \right) \leqq \frac{1}{4}
\end{aligned}



したがって, テイラーの定理より,  0 \leqq v \leqq uとなる vが存在して,


\begin{aligned}
\phi(u) = \phi(0) + u \phi'(0) + \frac{u^2}{2} \phi'' (0) \leqq  \frac{u^2}{8}
\end{aligned}


 u = s(b - a)だったことを思い出すと,


\begin{aligned}
\phi(u) = \log \left( \mathbb{E} \left[ e^{sX} \right] \right) \leqq \frac{  s^2(b - a)^2}{8}
\Leftrightarrow  \mathbb{E} \left[  \exp \left( sX \right)  \right] \leqq  \exp \left( \frac{s^2 (a-b)^2}{8} \right)
\end{aligned}


これにて, Hoeffding's lemmaを得ました.



このHoeffding's lemmaを用いて, Hoeffding's ineqを導出します.

Hoeffding's Inequality: 確率変数 X_1, ..., X_nは独立でかつそれぞれが有界区間 [ a_i, b_i ]に値をとるとする. この時, 任意の \epsilon > 0に対して次の不等式が成り立つ.


\begin{aligned}
\mathbb{P} \left( \frac{1}{n} \sum_{i=1}^n X_i - \frac{1}{n} \sum_{i=1}^n \mathbb{E} \left[  X_i \right] \geqq \epsilon \right) \leqq \exp \left( - \frac{2 n^2 \epsilon^2}{ \sum_{i=1}^n (b_i - a_i) } \right) 
\end{aligned}


導出
まず,  Z_i = X_i - \mathbb{E} [ X_i ]と置く. このとき,  \mathbb{E} [Z_i ] = 0であり,  a_i \leqq Z_i \leqq b_iが成り立つので, 確率変数 Z_iはHoeffding's lemmaの仮定を満たす. ここで,


\begin{aligned}
& \mathbb{P} \left( \sum_{i=1}^n Z_i \geqq \epsilon  \right)  \\
& = \mathbb{P} \left(  \exp \left(  s \sum_{i=1}^n Z_i  \right) \geqq \exp(s \epsilon ) \right) \\
& \leqq   \exp \left( -s \epsilon \right)  \mathbb{E} \left[ \prod_{i=1}^n \exp (s Z_i) \right]  \quad \because Marcov's \: ineq \\
& =  \exp \left( -s \epsilon \right) \prod_{i=1}^n  \mathbb{E} \left[ \exp (s Z_i) \right] \quad \because independency  \\
& \leqq \exp \left( -s \epsilon \right) \prod_{i=1}^n  \exp \left( \frac{s^2 (b_i - a_i)^2} {8} \right) \quad \because Hoeffding's \: lemma \\
& = \exp \underbrace{  \left( \frac{s^2}{8} \sum_{i=1}^n (b_i - a_i)^2 - s \epsilon  \right)}_{(1)}
\end{aligned}

よりtightなboundを得るため, (1)を最小化する s =   4  \epsilon / \sum_{i=1}^{n} (b_i - a_i)^{2} を代入すると,


\begin{aligned}
\mathbb{P} \left(  \sum_{i=1}^n Z_i \geqq \epsilon  \right) \leqq  \exp \left( \frac{-2 \epsilon ^2} { \sum_{i=1}^n (b_i - a_i)^2 } \right)
\end{aligned}


ここで,  Z_i = X_i - \mathbb{E} [ X_i ] を代入し, 両辺を nで割ることで, Hoeffding's ineqを得ます.



Hoeffding's ineqは, 有限仮説集合の汎化誤差解析やバンディット問題におけるリグレット解析など至る所で出てくる印象です. 定理自体,  X_1, ..., X_nが独立であれば成り立ちますが, 実際はiidが仮定されていることが多いと思います. (iidの仮定がある場合,  \frac{1}{n} \sum_{i=1}^n \mathbb{E} \left[  X_i \right] の部分が単に \mathbb{E} \left[  X_i \right]となります.)

McDiarmid's inequality

最後に, McDiarmid ineqを紹介します. これは, 後に紹介する予定のRademacher Complexityに関連する不等式を導くときなどに役立ちます. これを示す前に, 一つ補題 (Azuma's ineq) を示します.

Azuma's inequality: 確率変数 X_i, Z_i, V_i: i=1, ..., nに対して,  V_i X_i, ..., X_iの関数でありかつ \mathbb{E} [V_i | X_i, ..., X_{i-1} ] =0 が成り立つとする. また,  Z_iは,  X_1, ..., X_{i-1}の関数として表すことができ,  i = 1, ..., nについて Z_i \leqq V_i \leqq Z_i + c_iを満たすような定数 c_iが存在するとします. このとき, 任意の \epsilon > 0に対して, 次の不等式が成り立つ.


\begin{aligned}
\mathbb{P} \left(  \sum_{i=1}^n V_i \geqq \epsilon  \right) \leqq \exp \left(  - \frac{2 \epsilon^2}{\sum_{i=1}^m c_i^2 } \right) 
\end{aligned}


導出
まず V_iについての部分和を S_k = \sum_{i=1}^k V_iとしておきます. ここで t > 0を用いて,


\begin{aligned}
& \mathbb{P}\left(  \sum_{i=1}^n V_i \geqq \epsilon  \right) \\ 
& =  \mathbb{P} \left(  S_n \geqq \epsilon  \right)  \\
& = \mathbb{P} \left( \exp \left( t S_n \right) \geqq \exp (t \epsilon ) \right) \\
& \leqq \exp (- t \epsilon ) \mathbb{E} \left[ \exp \left( t S_n \right) \right] \quad \because Marcov's \, ineq  \\
& = \exp (-t \epsilon ) \mathbb{E}_{ X_1, ..., X_{n - 1} } \left[ \exp (t S_n)  \mathbb{E}_{X_n} \left[  \exp(t V_n) | X_1, ..., X_{n-1} \right]  \right] \\
& \leqq  \exp (-t \epsilon ) \mathbb{E}_{ X_1, ..., X_{n - 1} } \left[ \exp (t S_n) \right ] \exp \left( \frac{t^2 c_n^2}{8} \right)  \quad  \because  Hoeffding's \, lemma \\
&  \leqq  \exp  \underbrace{ \left( \frac{t^2}{8} \sum_{i=1}^n c_i^2  - t \epsilon \right) }_{(2)} 
\end{aligned}


Hoeffding's lemmaの部分は, 仮定より X_1, ..., X_{n-1}で条件付けたとき V_iの期待値が0であることからlemmaの仮定を満たします. 最後の不等式は, Hoeffding's lemmaを繰り返し用いることで得ます. 最後に, (2)を最小化する t = 4 \epsilon / \sum_{i=1}^{n} c_i^{2}を代入することで,


\begin{aligned}
\mathbb{P} \left(  \sum_{i=1}^n V_i \geqq \epsilon  \right) \leqq \exp \left(  - \frac{2 \epsilon^2}{\sum_{i=1}^m c_i^2 } \right) 
\end{aligned}


を得ます.



さて, これを用いてMcDiarmid's ineqを示します.

McDiarmid's inequality: ある集合 \mathcal{X}に値をとる独立な確率変数を X_1, ..., X_nとする. また, 関数 f: \mathcal{X}^n \rightarrow \mathbb{R}と任意の x_1, ..., x_n, x_i' \in \mathcal{X}について, 次の条件 (boundedness condition) を満たすような定数 c_1, ..., c_nが存在するとする.


\begin{aligned}
| f(x_1, ..., x_i, ..., x_n) - f(x_1, ..., x'_i, ..., x_n)  | \leqq c_i, \quad \forall i \in \{1, 2, .., n \}
\end{aligned}

この時, 任意の \epsilon > 0に対して, 次の不等式が成り立つ.


\begin{aligned}
\mathbb{P} \left(  f(X_1, ..., X_n) -  \mathbb{E} \left[ f(X_1, ..., X_n) \right] \geqq \epsilon \right)   \leqq  \exp \left(  - \frac{2 \epsilon^2}{\sum_{i=1}^n c_i^2} \right)
\end{aligned}


導出
最初に f (X_1, ..., X_n) f (S)と表しておきます. また,  V_1, ..., V_n


\begin{aligned}
V_k = \mathbb{E} \left[ f(S) | X_1, ..., X_k \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right]
\end{aligned}


とします ( V_1 = \mathbb{E} \left[ f(S) | X_1 \right] - \mathbb{E} \left[ f(S) \right]). ここで, 今定義した V_kAzuma's ineqの仮定を満たすことを確認します. まず,  V_kの第1項は X_1, ..., X_kで条件付けた時の期待値なので, これらの確率変数の関数です. さらに,


\begin{aligned}
\mathbb{E} [ V_k  |  X_1, ..., X_{k-1} ] 
& = \mathbb{E}_{X_k, ..., X_n} \left[ f(S) | X_1, ..., X_k \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] \\
& = \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] \\
& = 0
\end{aligned}


ここで, boundedness conditionより


\begin{aligned}
\sup_{x, x'} \{\mathbb{E} \left[ f(S) | X_1, ..., X_{k-1}, x \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1}, x' \right]   \}  \leqq c_i
\end{aligned}


を満たします. ここで,  Z_k = \inf_x  \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1}, x \right] とすると,  X_k, V_k, Z_k: k=1, ..., nAzuma's ineqの仮定を満たします. 最後に,


\begin{aligned}
\sum_{i=1}^n V_i  
&  =   \left( \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] \right) \\
& \quad + \cdot \cdot \cdot +  \left(  \mathbb{E} \left[ f(S) | X_1 \right] - \mathbb{E} \left[ f(S) \right] \right) \\
& = f(X_1, ..., X_n) -  \mathbb{E} \left[ f(X_1, ..., X_n) \right]
\end{aligned}


と見て, これにAzuma's ineqを適用すれば, MacDiamid's ineqを得ます.



さいごに

さて, 本記事では機械学習の周辺分野でよく使われる確率不等式(特に, Hoeffding's inequalityとMacDiamid's inequality)を導出してみました. 一見どのように役立つかわからないかもしれませんが, 今後本ブログで記事にするつもり内容と密接な関連があります.
なお, 導出部分で私が勘違いして誤った記述をしている可能性が大いにあります. 誤りを見つけた場合, ご指摘いただけたら幸いです.

参考

[金森 (2015)] 金森敬文. 2015. 統計的学習理論. 講談社 機械学習プロフェッショナルシリーズ.
[Duchi] John Duchi. Probability Bounds. URL: http://www.cs.berkeley.edu/~jduchi/projects/probability_bounds.pdf.