THINKING MEGANE

ペパボに入って12年が経った。気付けば博士になっていた

先月、博士(情報科学)の学位を取得した。

12年前、福岡 おもしろい it 会社と検索をして、株式会社paperboy&co.(現GMOペパボ株式会社)に運用開発エンジニアとして転職した時1からすると、予想だにしなかった状態である。 転機は2017年1月だった。 ペパボで切磋琢磨できる仲間に恵まれ、OSS活動や登壇を通したアウトプット、社内での成果を自負する一方で、社内でもレベルの高いエンジニアとの仕事の機会を通して、自分の限界も感じ始めていた。 そんな折、研究所の所長から研究職への打診があった。 確か、当時進めていたログ活用基盤の構築とその内容の研究所のコンセプトへの親和性からだったように記憶している。 感じていた限界を「コンピュータサイエンス」ってやつや「研究的アプローチ」ってやつで突破できるかもしれない、研究って何もわからないけれども何とかなるだろう、渡りに船だとばかりにこの誘いに乗ることにした。

結果、丸々二年間、滑稽なぐらい迷走した2。 「研究」をするぞと意気込みは空回りし、研究所の同僚からのアドバイスも虚しく、納得する成果を出せずに時間だけが過ぎ、短時間で効果が出るものを求め悪循環が始まった。 元来の己の精神的な弱さ、四十歳前後という年齢特有の焦り、人生最高潮に達したあらゆるものに対する固執が目を曇らせ、足を引っ張った。 長く暗い時期だったが、ほんとうにほんとうにありがたいことに、さまざまな人に支えられ、何度も内省を進めることでかろうじて持ち直していった。 研究所の同僚、エンジニアと研究者が集うWSA研3、研究者の先輩方、そして家族には感謝の念が尽きることはない。 それでも距離をおくことを選択した縁もあり、たくさん迷惑をかけてしまった。

「研究」は難しい。 これは高度という意味での難しさではなく、ソフトウェアによる課題解決とは目的が違うことに起因する難しさについてである。 博士課程を終えて、研究とは「人類が新たに学べる領域を作り出すこと」であると考えるようになった。 すなわち、ソフトウェアによる課題解決は、目的に連なる目標のうちの一つであり、その解決も含めて、新たに学べる状態に仕上げねばならない。 そして、後進が学べる状態であるには、どこがこれまでの方法と異なるのか、どれぐらいの効果があるのか、それらが主張とその裏付けという形で明確に述べられたかといった要件に落とし込まれる。 これは、論文における「新規性」「有用性」「了解性」の観点に対応し、論文を記述する際には、これらの観点を満たすための様々なサーベイやライティング手法を駆使して臨むことになる。 そのような過程を経ることで初めてそのアウトプットは、未来の誰かの手による学べる領域の更なる拡大を支えていくことができる。 落とし穴は、ソフトウェアによる課題解決を目標ではなく目的に据えてしまうことである。 ここに陥ると、課題の解決こそが研究であり、課題解決のみで研究であるためには、大層な水準の課題を解決せねばならないとなりかねない。 自分が最初に躓いたのはここではないかと思う。

この頃の自身の振り返りを読むと、感情との付き合い方4の他に、研究とは何かを手探りで模索している様子が見て取れる5 6 7。 解決したことを伝えていかないといけないのだな、そのためにはたくさんの根拠を示さないといけないのだな、だから一朝一夕じゃ無理で時間をかけて向き合うことが必要なんだな、程度の理解度ではあるものの、この辺りから前に進み出したのだろうと思う。 2020年6月に初めてジャーナルの採録通知を受け取り8、10月には社会人学生として九州大学大学院システム情報科学府博士後期課程へ社会人学生として進学した9。 進学の後押しも研究所の所長だったと思う。 これまでの経緯もあり、及び腰だった自分に「研究職続けるなら博士号はあった方がいいし、いずれは取るのだから最短で効果が出せることをやったらいいんじゃないですか」と言われ、それもそうだなと挑戦を決めた。 暗中模索の中でも進めていた十本弱の研究報告やジャーナルの実績をもって修士を飛ばしての出願と入学が認められたこともあり、積み重ねは無駄じゃなかったなあ、ようしやるぞとここからは順風満帆。 といかないのがいかにも自分らしくて思い出しても苦笑してしまうのだが。

博士課程の修了には一定数の実績が必要となる。 自分の場合は、在学中に国内ジャーナル論文をもう一本、一定水準以上の国際会議での採択が一回が最低基準であった。 国内ジャーナルこそなんとか通せたものの、国際会議については、2021年5月の初投稿から丸二年、七回目の挑戦にしてようやくの採択となり長い我慢の時期を過ごした10。 そんな中、指導教官は一貫して、研究という最短ルートはない道程において、同じ道を回ることなく、常に何かしらの前進という成果を得るためのアドバイスを与えてくれたと思う。 それは例えば「難しいものと認識した上でそれに挑戦する喜び」であったり「ダメだった場合は改善してただ次に行くだけ」であったり、「自分で決めて悔いのないように進む」こと、そして「結果に対して本質的な面白さを見出して言語化し、これまでの取り組みと有機的に関連づけていくこと」などである。 博士課程という自分の研究の型を体得していく中で、指導教官の存在は本当にありがたいものであった。 指導教官は、分野の専門性が重なっていることが望ましいが、それ以上に相性があると思うので、できれば共著を先に一度執筆するなどコミュニケーションを取れると良いと思う。 幸い、自分の場合は、進学前の共同研究の際に知り合うことができたのでこの点でも恵まれていたと思う。

とはいえ、博士課程は、自身で主体的に研究を推進しなければならない。 これは、博士課程が「人類が新たに学べる領域を作り出すこと」という研究を達成する、「その方法論を、特定の研究テーマに基づく実践を通して身につける課程」だからだと思われる。 新たに学べる領域を作り上げているのであるから、指導教官にとってもわからない部分を切り開いていくのであり、そしてその開拓の方法は、自身でやり方を模索していかなければならない。 主体性については、能動的に動くことが前提の社会人であれば特段問題にならないかと思う。 博士課程での大変さは、この研究を推し進めるやり方の模索に対するフィードバックが、アウトプットに対してのみ得られるという点だったと思う。 それは主に査読結果や、国際会議での発表に対する議論の形を取るが、いずれにせよ論文の形にまとめる必要がある。 これは研究を学ぶには研究をしなければならないという構造であり、研究テーマ自体も発展させなければならないことも相まって、随分鍛えられたと感じている。 幸い、指導教官のアドバイスはこれに即したものであり、博士論文に着手する前の三年間で研究報告や不採択のものも含めると十六本、おおよそ二、三ヶ月に一本は何かしら研究成果を出して論文執筆していたことになる。 成長が遅いのは仕方ないとはいえ、研究開発員として、事業への貢献も求められる中でも諦めずに課程を継続したことは自分を褒めてあげたい。

2024年4月には、追加でもう一つ国際会議に採択され、最終的に、入学前のジャーナル論文と合わせて計四本の実績をもとに、学位申請のための博士論文を執筆した11。 博論の執筆では、これまでの実績を「人類が新たに学べる領域」として再構成する。 四本の論文の整合性を取りながら、領域の世界観の確立も必要で、非常に難易度の高い執筆であり、実績達成以上にまだ大変な工程が残っているのかと驚いた。 しかしながら、この工程を通して初めて、ボトムアップな進め方であった自身の研究テーマに対し、トップダウンからの位置付けを与えることができたように思える。 実際に、自身の研究観である「人類が新たに学べる領域を作り出すこと」というのもこの段階を経て感じるようになった。 これまで各論文においても「新規性」「有用性」「了解性」の観点を満たせるよう突き詰めてきたが、複数論文をまとめる中で、それぞれの点が関連し、補い合う形で(まだ非常に狭いながら)初めて領域として形をなしていったように思う。 なお、世界観の確立については、ペパボ研究所のコンセプトである「なめらかなシステム」についての、所長との数年間に渡るディスカッションが非常に役立った。 このようなハイコンセプトな思考だけでなく実践的にも抽象的にも自在に観点を行き来しながら多面的に研究を見直す機会があるのがペパボ研究所の長所だと思う。 博士課程を考えている方はぜひ検討してほしい。 その後、公聴会を経て、2024年9月25日付けで博士(情報科学)の学位を授与された。 在学は四年間。 標準年度の三年には間に合わなかったが、なんとか修了に漕ぎ着けることができて安堵している。

さて、ここまでして博士課程を終了する必要はあったのか。そしてこれからも研究をする必要はあるのか。 サンクコストを差し引いたとしても、自分自身としては「はい」と答えたい。 「課題解決」と「研究(新たに学べる領域を作り出すこと)」は相補的な関係であり、それぞれの存在がお互いを必要としていると思う。 また、特にソフトウェアやエンジニアリングの分野においては、それぞれは明確に分離している訳でもないと思う。 研究的なアプローチによって、同じ課題に対しても体系化・一般化・言語化・比較整理などを通して、多面的に捉え直し、新しい観点からちょっと面白い発想が出るかもしれない。 研究による成果物によって、ある課題に対してある状況において有用な方式を広く適用できるかもしれない。 その方式がうまくいかない場合も、理論的な裏付けもしくは再現可能な部分評価を元に、そこから学んで最短で適用できる改善を思いつけるかもしれない。 学べる状態にするのは手間がかかる。 それでもどこかの誰かの巨人の肩になるのだと信じて、研究というのを仕事にする人がいても良いのではないかと思う。

もちろん、企業研究所に所属する研究員としては、より実践的に、博士課程で得たスキルを早速活用していきたい。 改めて、博士号を取得したということは、不確実で混沌とした課題領域においても、比較・体系化・言語化を通して、誰もがその課題を共有し、時間をかけることなく効果のある対策を講じられる基盤を整えられるスキルを持つ、すなわち、学べる領域を作り出せる人材であることが期待されるようになったのだと思う。 今後は、自身の研究テーマの推進はもちろんのこと、さまざまな施策において、所属する研究所のミッションである「研究開発により『事業を差別化できる技術』を生み出す」ことができるよう、さらに精進していきたい。 そして、これまで辛抱強く支えてくれたペパボに恩返ししていきたい。

ペパボに入社して十二年。 タイトルの「気付けば」も大袈裟ではなくて、特に研究職になってからは時間が飛ぶようにすぎていった。 それでも、いろんなことがあったけれども、誰かと比較してではなく、過去最高の自分に仕上がっているというのは四十三歳にしては悪くないのではないか。 これからも「虚仮の一念、岩をも通す」の精神で頑張っていきたい。

お知らせ

僕のキャリアを支援してくれたことからも分かるように、GMOペパボ株式会社はどうすればインターネットを面白くできるのか、これを真面目に考えてさまざまななやり方で取り組んでいます。 研究開発的なアプローチに対してでも良いですし、事業に対してでも大丈夫です。 こんなペパボに興味持たれた方、もっと雰囲気知りたい方、お気軽にお声がけください。

ペパボ研究所

参考


  1. ペパボに入って4年が経った ↩︎

  2. 2017年, 12月のライオン ↩︎

  3. WSA研 ↩︎

  4. 理性の人 ↩︎

  5. わかるとわからないの間 ↩︎

  6. 論文執筆の道しるべ ↩︎

  7. 2019 ↩︎

  8. ペパ研から研究をはじめてジャーナルでのアクセプトまでいけた日 ↩︎

  9. 九州大学大学院システム情報科学府博士後期課程に入学します ↩︎

  10. 社会人大学院生の七転び八起き国際会議奮闘記 ↩︎

  11. 博士後期課程を修了し、博士(情報科学)の学位を授与されました ↩︎

ターミナルフレンドリーなAIコマンド、afaを作った

Go言語で、AIモデルに対する推論をコマンドラインで実行するafaというツールを作りました。入出力としてテキストストリームを前提としており、パイプやリダイレクトを用いて他のコマンドと連携しやすいのが特徴です。

$ echo $ERROR_MESSAGE | afa new -p "What is happening?" /path/to/file1 /path/to/file2

与えるプロンプトやコンテキスト情報によってAIモデルが柔軟に振る舞いを変えてくれるので、これまでの個別ツールでは対応が難しかった用途における自動化にも有用でしょう。 また、テキストストリームを扱えるリッチなTUIのコマンドafa-tuiも別途提供しているので、ターミナル上でのチャットも快適です。

デモ

リッチTUIによるチャット

快適なインタラクティブチャットのため、Markdownを装飾して描画しつつ、lessコマンド相当の操作感のページャーと、プロンプトの入力欄を持つViewerと連携できます。

Chat

Zsh Line Editor(ZLE)を用いたターミナル上でのコマンド提案

ZLEと連携すれば、コマンドライン上でのプロンプトをそのまま提案されたコマンドに置き換えて実行できます。

Command Suggestions

Vim上でのコード提案

Vimと連携すれば、選択範囲のコードを提案されたものに置換できます。使い慣れたエディタであればdiff表示や差分の部分反映もお手のものですね。

Code Suggestions

機能一覧

  • ターミナルフレンドリーなAIコマンドとして機能します。
  • リッチなターミナルユーザーインターフェース(TUI)を持つチャットクライアントとして機能します。
  • システムとユーザーのための文脈に応じたプロンプトをテンプレートを使用してサポートします。
  • プロンプト、標準入力、およびファイルパスを文脈として受け付けます。
  • セッションを管理し、resume サブコマンドを介して迅速に再開できるようにします。
  • 安全にエスケープされたJSONオプションで構造化された出力をサポートし、他のコマンドとの統合を容易にします。
  • コアアプリケーションはサードパーティライブラリに依存せずに独立して動作します。
  • AIモデルとしてOpenAIをサポートします(他のAIモデルのサポートは将来計画されています)。

なお、この文章は、英語で書かれたafaのREADMEのFeatures項目をコピーして、pbpaste | afa new -script -p "翻訳して" | pbcopyで貼り付けました。便利ですね。

基本的な使い方

Viewerを使用しないシンプルなチャットを起動する。

$ afa new

Viewerを使用してチャットを起動する。

$ afa new -V

コンテキスト情報を加えてチャットを起動する。コンテキスト情報には「標準入力」「プロンプトメッセージ(-pオプションによるもの)」、そして「ファイルパス」を与えることができる。 ただし、仕様上、標準入力を与えるとキーボードからの入力を継続できないため、インタラクティブなチャットはできない。この場合は、プロセス置換(<())をファイルパスとして与えることを検討されたい。

$ echo $ERROR_MESSAGE | afa new -p "What is happening?" /path/to/file1 /path/to/file2
# Please be cautious; when standard input is provided, interactive mode is disabled.
# Consider using process substitution.
#=> afa new -p "What is happening?" /path/to/file1 /path/to/file2 <( echo $ERROR_MESSAGE )

直近のセッションを再開する。

$ afa resume

指定したセッションを再開する。なお、afa listコマンドでセッション一覧を表示できる。

# The command `afa list` displays past sessions.
$ afa source -l SESSION_NAME

ユーザープロンプトを指定する。ユーザープロンプトは、Go言語のテンプレート形式であり、テンプレート内ではプリセットの値としてコンテキスト情報に対応する、MessageMessageStdin、そして NameContentをメンバとするFile構造体のリストであるFilesを以下のように呼べる。これにより動的なプロンプトの生成が可能となる。

# `Message`, `MessageStdin`, and `Files` that include `File` with `Name` and `Content` members can be used in the template file.
$ echo "Please explain the following.\n{{ (index .Files 0).Content }}" > CONFIG_PATH/templates/user/explain.tmpl
afa -u explain /path/to/file

スクリプトモードを指定して起動する。コマンドライン実行に適したモードのオプション設定を一括で行う-scriptオプションを指定することで、他のコマンドとの連携が容易になる。具体的には-I=false -H=false -S=false -V=false -L=falseが設定される。

pbpaste | afa new -script -p "Transrate this" | pbcopy

OpenAIの独自機能として提供されるStructured Output用のスキーマを指定できる。これは指定したJSON構造体に沿うような出力を強制する機能である。例えば、余分な説明が不要なコマンド提案などに適している。 クオート文字のエスケープを担う-Qオプションと合わせて使うことでjqによる整形が容易になるので活用されたい。

$ cat <<< EOS > CONFIG_PATH/schemas/command_suggestion.json
{
  "type": "object",
  "properties": {
    "suggested_command": {
      "type": "string"
    }
  },
  "additionalProperties": false,
  "required": [
    "suggested_command"
  ]
}
EOS

$ P="List Go files from the directory named 'internal' and print the first line of each file."
$ afa new -script -Q -j command_suggestion -p $P | jq '. | fromjson' | jq -r '.suggested_command'
#=> find internal -name '*.go' -exec head -n 1 {} \;

実践例

実践例を列挙します。 もし使いたい例があれば、GitHubのリポジトリのREADMEにプロンプトや設定例と共に載せているので参考にしてみてください。

  • Zsh Line Editor(ZLE)を用いたターミナル上でのコマンド提案
    • デモで紹介したものです
  • Vim上でのコード提案
    • これもデモで紹介したものです
  • ターミナルに表示されたエラーメッセージの分析
    • tmuxcapture-paneを使って直近の実行結果を分析できます。複数行にわたるエラーメッセージのコピペの手間が省けて便利ですね
  • GitHubのプルリクエストの自動生成
    • git diffgit logの情報を元にタイトルと要約を生成してプルリクエストを開きます。ZLEを想定しているので背景情報も踏まえて考えてもらえるようになっています。また、既存のテンプレートの上に要約を差し込む形にしているので、どのリポジトリでも使いやすいかなと思います。
  • pecoを用いたセッションの絞り込みと読み込み
    • インタラクティブな絞り込みで素早く過去のセッションにアクセスできます。

AFA

AFAはAI for Allの略で、あらゆるコマンドラインツールに対して連携可能($\forall x \in X , \exists \mathrm{AI}(x)$、つまりコマンドラインツールの集合Xの全ての要素xに対し、その結果を入力とするAI(x)な組み合わせが存在する)なAIコマンドになるといいなと思って付けた名前です。

現時点でもまだViewerの入力欄が不調になることがあったりWindowsでの動作確認ができていないなど課題はありますが、通常使う分には十分な品質になったと思うので公開しました。よく使うオプションセットをconfigに設定し、いくつかのユーザープロンプトを登録しておいてalias af='afa new'とするだけで、個人的には、調べ物やチャットを含め、ブラウザの利用頻度がかなり減ったことを実感しています。

Homebrewによるインストールbrew install monochromegane/tap/afa monochromegane/tap/afa-tuiも提供していますので、よければ使ってみてください。

将来的には、サーバー上での異常検知のような定式化の難易度が高いタスクでの適用も検討しています(サードパーティー製ライブラリへの非依存とViewerツールとの分離は、そのためでもあります)。AFAであれば、他のコマンドラインツールとの親和性を活かして、通知やロギングは従来の仕組みも活用できると考えています。適用例など共有してもらえたら嬉しいです。

社会人大学院生の七転び八起き国際会議奮闘記

2023年10月に初めてのアカデミックな国際会議での発表を終えました。 社会人博士課程に進学後、2021年5月の初投稿から丸2年、7回目の挑戦にしてようやくの採択ということで、自慢できるものではないのですが、同様に博士課程において日々挑戦している方々に何かの参考になればと思い、まとめておきます。

略歴と背景

2017年からペパボ研究所で研究開発職に従事しています。 情報システムの自律適応等の研究に取り組み、2020年10月に社会人博士課程に進学しました。 博士課程では、多様かつ継続的に変化する環境に適応する実用的な情報システムの実現に向けて、多腕バンディット方策を用いる機構の研究を進めています。

修士を飛ばした進学であったこともあり、進学時の実績としては国内ジャーナル論文1本のみでしたので、博士号取得に向けてはジャーナル論文をもう1本と、水準を満たす国際会議での採択1本を目指しての挑戦となりました。

年表

以下に挑戦した国際会議とその結果について時系列にまとめました。

RecSys2021 (Reject)

2021/05投稿。 提案手法において変化する環境への適応能力を向上させるべく進学後に試行錯誤した結果をまとめたものを投稿。

2021/07不採択通知。 Review結果は5点中、1点4点2点2点2点と散々でした。 総評としてはアイディアやアプローチの萌芽は理解できるが、それらを納得させるような位置付けや妥当性の説明が不十分であるというもの。 この時点では、国際会議に向けての集中的サーベイや、初めての英語論文を書き上げるのに精一杯で、論文としてまだ議論の土台に立てていなかったと思います。

WSDM2022 (Reject)

2021/08投稿。 前回のRecSys2021の指摘事項を踏まえ、記述を見直して投稿。 当初は前回投稿に対するレビュアーからの指摘事項を個別に反映しただけでしたが、指導教官より、研究の位置付けが明確になるよう全体を通した見直しはどうですかとアドバイスをいただき、導入や関連研究を中心に大幅にリライトして投稿。

2021/10不採択通知。 Review結果は、Weak rejectが3名、Rejectが1名でまだまだ採択には遠かったです。 それでも、総評には、サーベイの充実度や記述の了解性に対する前向きなコメントが多く、前進が感じられました。 なお、分野のexpertからは、提案の新規性や理論的な裏付け、もう一歩踏み込んだ評価の必要性などが指摘されています。

SAC2022 RS Track (Reject)

2021/10投稿。 前回のWSDM2022の指摘のうち、提案手法を維持したまま対応できる部分を記述面で更新して投稿。

2021/12不採択通知。 Review結果は、スコアが明記されていないもののReject寄りのコメントが2名、Accept寄りのコメントが1名でした。 採択に多少は近づいたように感じられるものの、総評としては前回とほぼ同様であり、次の提案方式の検討も進んでいたことから、この方式での国際会議への挑戦はここで一旦終えています。

なお、この方式については、国内の論文誌に投稿し、無事採択されました(2本目の国内ジャーナル論文の実績)。 その査読においても新規性・有用性に関しての議論は行われ、採録条件に応える中で、これらを向上させることができたと思います。

CIKM2022 (Reject)

2022/05投稿。 提案手法において変化する環境への適応能力とオンライン性能を両立させるための方式を検討したものを投稿。 先んじて国内研究会で途中経過をまとめる機会があったこと、前年の執筆経験が蓄積されていることもあり、同様に新規書き下ろしであったRecSys2021の時よりも短い期間で投稿できました。

2022/08不採択通知。 Review結果は、Weak rejectが1名、Weak acceptが2名で、メタの判断によっては採択されていたかもしれず、惜しいと感じました。 総評は、研究の位置付けやアプローチの妥当性、記述の了解性に対しては一定の水準を満たすものの、手法の有効性を示すための評価方法の改善を求める指摘が多くありました。 前年と比べて手法自体の新規性の観点では認められつつあるなと感じるものの、その有用性を示すための工夫をどうするべきか考えあぐねていた時期だったと思います。

AAMAS2023 (Reject)

2022/10投稿。 前回のCIKM2022の通知を待つ間に、提案手法に関連するサーベイが進んだこともあり、位置付けの補強を兼ねて、それらを盛り込み、イントロダクションと関連研究を中心にリライトして投稿。

2023/01不採択通知。 Review結果は、Weak paperが1名、Decent paperが2名。 総評としては、やや厳し目で、了解性や位置付けに関する指摘が再発してしまいました。 おそらく追加的なサーベイを自身で消化しきれておらず、結果的に解決したい課題に対して不要に広い議論となってしまったのではないかと考えています。 また、前回の有用性をどう示すかという指摘についても、具体的な解決策を検討できないまま、記述で頑張ろうとしてしまったのも不明瞭になった遠因かもしれません。

この時期は、なかなか国際会議に採択されないため、博論執筆に向けた実績を満たせないことに対する焦りが募っていきました。

PAKDD2023 (Reject)

2022/12投稿。 AAMAS2023への投稿と並行して、提案手法のもう一つの要素技術についてコンセプト的な実装と評価を進めていたものを投稿。

2023/02不採択通知。 Review結果は、Weak rejectが2名、Weak acceptが2名でした。 総評は、課題と提案の位置付けや妥当性は納得できるものの、提案の新規性に関する疑問があるとのことで、課題に対する提案手法の検討の甘さが見透かされたように思えます。

SMC2023 (Accept!)

2023/04投稿。 研究としてはAAMAS2023の手法とPAKDD2023の手法が二つ並行している状態でしたが、まずは提案として完成しているAAMAS2023の手法を着地させるべく投稿。 一度、PAKDD2023の研究で離れたことが功を奏したのか、改めて関連文献を読み込む機会を通して知識の再整理が進み、提案手法の課題設定と採用するアプローチにおいて無理なく接続できるような定式化と説明ができたと喜んだ記憶があります。 また、執筆中に最新のサーベイで類似手法が見つかって焦る場面もありましたが、提案手法との差異を検討する中で結果的に提案の新規性の主張が明確にできたのでよかったです。

2023/06採択通知。 Review結果は、スコアが明記されていないもののAccept寄りのコメントが3名、Reject寄りのコメントが1名でした。 総評では、研究や提案の位置付け、記述の明快さなどについて前向きなコメントがあり、新規性の多寡についての議論も若干ありました。 一方で、有用性や評価に関する不足のコメントがほぼ見られなかったのは興味深かったです。 これは定式化を進め、課題設定や解決する部分についての曖昧性が減少したことで、最小限の記述で過不足ない評価内容について、査読者と認識を揃えることができたためではないかと考えています。 この論文の執筆を通して、改めて、査読者のコメントを局所的に解釈するのではなく、その疑問が発生する根本について対局的にみて解決していくことの重要性を感じました。 これは2度目のWSDM2022への投稿時に指導教官からのアドバイスそのものであり、ようやく自分のものとすることができた時だったのかなと思えます。

まとめ

国際会議への長い挑戦を通して、研究を世界的な基準で議論できる水準まで押し上げていくのは一朝一夕にできるものではないのだなあと感じました。 自分の場合は、自身の研究の発展はもちろんのこと、研究を推し進めていく力を高めたいと考え、博士後期課程へ挑戦したこともあり、研究自体と研究力を同時に前進させる必要があり、特に時間がかかってしまっているのだろうと思います。 すぐ成果が出るものではないと頭では分かっているつもりでしたが、やはり2年間全く結果が出なかったというのは心理的な負担が大きかったです。 特に、研究開発員として、事業への貢献も求められる中、不採択による論文執筆期間の延長は、各種施策のスケジュールにも影響するため、とても心苦しい思いをしました。

そのような中でも、最初の国際会議の採択に漕ぎ着けることができたのは、ひとえに指導教官、研究所の仲間、そして会社の皆様の支援のおかげだと考えています。 本当にありがとうございます。

最後に、自分にとって研究は「自分の思い描く世界に至るための過程」であり、そのためには問題に向き合い続けることが大切だと考えています。 問題に向き合い続けるには、行き詰まらないよう多面的に見ることが重要です。 とは言え、博士課程の進学前は、多面的にあれこれ手を出すことはできていたものの、どこかでやりきれなかったり発散してしまっていたように思えます。 しかし、博士課程の進学後は、指導教官からの指導の中で、絶対に止まらない方法、収束させる方法というのを体得できているように感じます。 それは例えば、「難しいものと認識した上でそれに挑戦する喜び」であったり「ダメだった場合は改善してただ次に行くだけ」であったり、「自分で決めて悔いのないように進む」こと、そして「結果に対して本質的な面白さを見出して言語化し、これまでの取り組みと有機的に関連づけていくこと」などです。 これらはつまり、研究という最短ルートはない道程において、同じ道を回ることなく、常に何かしらの前進という成果を得るための能力です。 現在は、2回目の国際会議に向けてPAKDD2023に挑戦した時の手法を一層発展させたものを投稿中です。 この論文の取り組みは、国際会議の実績を得た後に更に取り組んだもので、継続的な研究が常態となったことを示すものなのかなと思っています。

来年はおそらく博論に着手できる状態ですので、4年目に突入してしまいましたが博士号を確実に取得できるよう精一杯頑張ります。 そして、このように時間をかけて体得してきた研究と研究力の、支えてくれた皆様への還元を始めていきたいです。

カーネルリッジ回帰 入門

基底関数を用いた線形回帰モデルのように入力に非線形な変換を施してモデルの表現力の向上を図る手法では、以下の2つの問題が発生する。

  1. 特徴ベクトルの次元数の増加に伴う計算量の増加
  2. 予測に有用な基底関数の選定

カーネルリッジ回帰は、カーネル関数を用いて上記の課題を解決する。 このエントリは、このカーネルリッジ回帰を最初に学んだ際の内容を自分なりにまとめたものである。

以下では、はじめに、記法の整理を兼ねて基本的な線形回帰モデルを説明する。 次に、カーネル法を用いた線形回帰であるカーネルリッジ回帰の説明を通して上記の課題の解決アプローチを学ぶ。 最後に、カーネル法における計算量の課題を解決するためのアプローチである、Random Fourier Featuresも紹介する。

1. 線形回帰モデル

線形回帰モデルの問題設定と解法について述べる。 いま、$N$個の入力$X=(\boldsymbol{x}_1,\ldots,\boldsymbol{x}_N)^{\top} \in \mathbb{R}^{N \times D}$と出力$\boldsymbol{y}=(y_1,\ldots,y_N)^{\top} \in \mathbb{R}^{N}$が与えられている。 このとき、$y$は$\boldsymbol{x}$を入力とした線形回帰モデル$\hat{y} = \boldsymbol{w}^{\top}\boldsymbol{\phi}(\boldsymbol{x})$の出力として得られると仮定する。 ここで、$\boldsymbol{\phi}(\boldsymbol{x}) = (\phi_1(\boldsymbol{x}),\ldots,\phi_F(\boldsymbol{x}))^{\top} \in \mathbb{R}^{F}$は$F$個の基底関数$\phi: \mathbb{R}^{D} \rightarrow \mathbb{R}$からなる特徴ベクトル、$\boldsymbol{w} \in \mathbb{R}^{F}$はこれに対応する係数ベクトルである。 このとき、この係数ベクトル$\boldsymbol{w}$を推定することが本問題の目標である。

推定には最小二乗法を用いる。 なお、実用上は汎化性能の考慮から正則化を施すことが多いと思われるので、これを適用したリッジ回帰を行う。 すなわち、$\Phi = (\boldsymbol{\phi}(\boldsymbol{x}_1),\ldots,\boldsymbol{\phi}(\boldsymbol{x}_N))^{\top} \in \mathbb{R}^{N \times F}$としたとき、学習データに対する誤差の二乗和(に正則化項を加えたもの)$E(\boldsymbol{w}) = \| \Phi \boldsymbol{w} - \boldsymbol{y} \|^2 + \lambda \| \boldsymbol{w} \|^2$を最小化する$\boldsymbol{w}$を求める。

このために、まず$E(\boldsymbol{w})$を次のように整理する。

\begin{align} \begin{split} E(\boldsymbol{w}) &= (\Phi \boldsymbol{w} - \boldsymbol{y})^{\top}(\Phi \boldsymbol{w} - \boldsymbol{y}) + \lambda\boldsymbol{w}^{\top}\boldsymbol{w} \\ &= ((\Phi \boldsymbol{w})^{\top} - \boldsymbol{y}^{\top})(\Phi \boldsymbol{w} - \boldsymbol{y}) + \lambda\boldsymbol{w}^{\top}\boldsymbol{w}\\ &= ( \boldsymbol{w}^{\top}\Phi^{\top} - \boldsymbol{y}^{\top})(\Phi \boldsymbol{w} - \boldsymbol{y}) + \lambda\boldsymbol{w}^{\top}\boldsymbol{w}\\ &= \boldsymbol{w}^{\top}\Phi^{\top}\Phi\boldsymbol{w} - \boldsymbol{w}^{\top}\Phi^{\top}\boldsymbol{y} - \boldsymbol{y}^{\top}\Phi\boldsymbol{w} + \boldsymbol{y}^{\top}\boldsymbol{y} + \lambda\boldsymbol{w}^{\top}\boldsymbol{w}\\ &= \boldsymbol{w}^{\top}\Phi^{\top}\Phi\boldsymbol{w} - \boldsymbol{w}^{\top}\Phi^{\top}\boldsymbol{y} - \boldsymbol{w}^{\top}\Phi^{\top}\boldsymbol{y} + \boldsymbol{y}^{\top}\boldsymbol{y} + \lambda\boldsymbol{w}^{\top}\boldsymbol{w}\\ &= \boldsymbol{w}^{\top}\Phi^{\top}\Phi\boldsymbol{w} - 2\boldsymbol{w}^{\top}\Phi^{\top}\boldsymbol{y} + \boldsymbol{y}^{\top}\boldsymbol{y} + \lambda\boldsymbol{w}^{\top}\boldsymbol{w}. \label{eq:ew} \end{split} \end{align}

整理には、行列の定理$(AB)^{\top}=B^{\top}A^{\top}$と、スカラーは転置しても値が同じであることを利用した($\boldsymbol{y}^{\top}\Phi\boldsymbol{w} = (\boldsymbol{y}^{\top}\Phi\boldsymbol{w})^{\top} = \boldsymbol{w}^{\top}\Phi^{\top}\boldsymbol{y}$)。

次に、$E(\boldsymbol{w})$を最小化する$\boldsymbol{w}$を求めるために$\boldsymbol{w}$について偏微分して0とおく。

\begin{align} \frac{\partial E(\boldsymbol{w})}{\partial \boldsymbol{w}} &= 2\Phi^{\top}\Phi\boldsymbol{w} -2\Phi^{\top}\boldsymbol{y} + 0 + 2\lambda\boldsymbol{w} = 0. \end{align}

偏微分には、対称行列($A=\Phi^{\top}\Phi=A^{\top}$)に対する二次形式($\boldsymbol{w}^{\top}A\boldsymbol{w}$)の$\boldsymbol{w}$の偏微分が$(A + A^{\top})\boldsymbol{w} = 2A\boldsymbol{w}$であること、$\boldsymbol{w}^{\top}\boldsymbol{a}, \boldsymbol{a}=\Phi^{\top}\boldsymbol{y}$としたときの$\boldsymbol{w}$の偏微分が$\boldsymbol{a}$であることを利用した。

最後に、$\boldsymbol{w}$について整理する。

\begin{align} \begin{split} 2\Phi^{\top}\Phi\boldsymbol{w} -2\Phi^{\top}\boldsymbol{y} + 2\lambda\boldsymbol{w} &= 0\\ 2\Phi^{\top}\Phi\boldsymbol{w} + 2\lambda\boldsymbol{w} &= 2\Phi^{\top}\boldsymbol{y}\\ \Phi^{\top}\Phi\boldsymbol{w} + \lambda\boldsymbol{w} &= \Phi^{\top}\boldsymbol{y}\\ (\Phi^{\top}\Phi + \lambda I_F)\boldsymbol{w} &= \Phi^{\top}\boldsymbol{y}\\ \boldsymbol{w} &= (\Phi^{\top}\Phi + \lambda I_F)^{-1}\Phi^{\top}\boldsymbol{y}. \label{eq:w} \end{split} \end{align}

ここでは、行列のサイズが$F \times F$の単位行列を$I_{F}$と表記した。

新しい入力$\boldsymbol{x}$に対する出力は推定した$\boldsymbol{w}$を用いて、$\hat{y} = \boldsymbol{w}^{\top}\boldsymbol{\phi}(\boldsymbol{x})$と予測できる。

2. カーネル法による線形回帰モデル

上述の線形回帰モデルを利用する際には、基底関数を増やし多くの特徴量の候補から予測に有用なものに重み付けできれば良いと考えられることから、特徴ベクトルの次元数$F$を増やすアプローチが検討される。 しかしながら、この場合、パラメータ$\boldsymbol{w}$の推定や出力$\hat{y}$の予測に必要な計算量も同時に増加してしまう。 そこで、カーネル法による線形回帰モデルでは、パラメータの次元数を$N$に抑えるようなアプローチをとる。 これは、学習データ数$N$が特徴ベクトルの次元数$F$よりも少ない場合に有効である。 また、線形回帰モデルにはもう一つ、予測に対して有用な基底関数の種類や数が明らかではないという課題がある。 これに対しカーネル法による線形回帰モデルは、カーネル関数を導入することで、基底関数の選定を省略することができる。

以下、上述のリッジ回帰にカーネル法を適用したカーネルリッジ回帰を説明する。

2.1. 線形回帰モデルの双対表現

パラメータの次元数を$N$に抑えるため、$F$次元の$\boldsymbol{w}$についての線形モデル$\hat{y} = \boldsymbol{w}^{\top}\boldsymbol{\phi}(\boldsymbol{x})$を、$N$個の学習データ$\Phi$に対応するパラメータ$\boldsymbol{\alpha} \in \mathbb{R}^{N}$で表現することを考える。

そのために、式\eqref{eq:w}の3行目以降の変形を以下のように進める。

\begin{align} \begin{split} \Phi^{\top}\Phi\boldsymbol{w} + \lambda\boldsymbol{w} &= \Phi^{\top}\boldsymbol{y}\\ \lambda\boldsymbol{w} &= - \Phi^{\top}\Phi\boldsymbol{w} + \Phi^{\top}\boldsymbol{y}\\ \lambda\boldsymbol{w} &= - \Phi^{\top}(\Phi\boldsymbol{w} - \boldsymbol{y})\\ \boldsymbol{w} &= - \frac{1}{\lambda} \Phi^{\top}(\Phi\boldsymbol{w} - \boldsymbol{y}). \end{split} \end{align}

ここで$\boldsymbol{\alpha} = - \frac{1}{\lambda}(\Phi\boldsymbol{w} - \boldsymbol{y})$とすると、$\boldsymbol{w} = \Phi^{\top}\boldsymbol{\alpha}$となる。 これにより、元の線形回帰モデルを$\hat{y} = (\Phi^{\top}\boldsymbol{\alpha})^{\top}\phi(\boldsymbol{x})$と、(右辺にも$\boldsymbol{w}$は含まれるが)見かけ上は$\boldsymbol{w}$を含まない形で表現できるようになった(双対表現)。

この双対表現の線形回帰モデルについて、最小二乗法を用いて$\boldsymbol{\alpha}$を推定する。 これは上述の$E(\boldsymbol{w})$を双対表現の線形回帰モデルで記述し、解を求めることと同等である。

このために、式\eqref{eq:ew}に$\boldsymbol{w} = \Phi^{\top}\boldsymbol{\alpha}$を代入し$\boldsymbol{\alpha}$についての関数$E(\boldsymbol{\alpha})$とした上で、以下のように整理する。

\begin{align} \begin{split} E(\boldsymbol{\alpha}) &= (\Phi^{\top}\boldsymbol{\alpha})^{\top}\Phi^{\top}\Phi(\Phi^{\top}\boldsymbol{\alpha}) - 2(\Phi^{\top}\boldsymbol{\alpha})^{\top}\Phi^{\top}\boldsymbol{y} + \boldsymbol{y}^{\top}\boldsymbol{y} + \lambda(\Phi^{\top}\boldsymbol{\alpha})^{\top}(\Phi^{\top}\boldsymbol{\alpha})\\ &= \boldsymbol{\alpha}^{\top}\Phi\Phi^{\top}\Phi\Phi^{\top}\boldsymbol{\alpha} - 2\boldsymbol{\alpha}^{\top}\Phi\Phi^{\top}\boldsymbol{y} + \boldsymbol{y}^{\top}\boldsymbol{y} + \lambda\boldsymbol{\alpha}^{\top}\Phi\Phi^{\top}\boldsymbol{\alpha}\\ &= \boldsymbol{\alpha}^{\top}KK\boldsymbol{\alpha} - 2\boldsymbol{\alpha}^{\top}K\boldsymbol{y} + \boldsymbol{y}^{\top}\boldsymbol{y} + \lambda\boldsymbol{\alpha}^{\top}K\boldsymbol{\alpha}. \end{split} \end{align}

なお、 \[ K = \Phi\Phi^{\top} = \begin{pmatrix} \boldsymbol{\phi}(\boldsymbol{x}_1)^{\top}\boldsymbol{\phi}(\boldsymbol{x}_1) & \ldots & \boldsymbol{\phi}(\boldsymbol{x}_1)^{\top}\boldsymbol{\phi}(\boldsymbol{x}_N) \\ \vdots & \ddots & \vdots \\ \boldsymbol{\phi}(\boldsymbol{x}_N)^{\top}\boldsymbol{\phi}(\boldsymbol{x}_1) & \ldots & \boldsymbol{\phi}(\boldsymbol{x}_N)^{\top}\boldsymbol{\phi}(\boldsymbol{x}_N) \end{pmatrix} = \begin{pmatrix} k(\boldsymbol{x}_1,\boldsymbol{x}_1) & \ldots & k(\boldsymbol{x}_1,\boldsymbol{x}_N) \\ \vdots & \ddots & \vdots \\ k(\boldsymbol{x}_N,\boldsymbol{x}_1) & \ldots & k(\boldsymbol{x}_N,\boldsymbol{x}_N) \end{pmatrix} \in \mathbb{R}^{N \times N} \] とした。 ここで、入力$\boldsymbol{p}$と$\boldsymbol{q}$を$\boldsymbol{\phi}$によって特徴ベクトルに変換し内積をとる操作である$k(\boldsymbol{p},\boldsymbol{q})$をカーネル関数と呼ぶ。 また、学習データ$X$に対する全ての組み合わせである$K$をグラム行列と呼ぶ。

次に、$E(\boldsymbol{\alpha})$を最小化する$\boldsymbol{\alpha}$を求めるために$\boldsymbol{\alpha}$について偏微分して0とおく。

\begin{align} \begin{split} \frac{\partial E(\boldsymbol{\alpha})}{\partial \boldsymbol{\alpha}} &= 2KK\boldsymbol{\alpha} - 2K\boldsymbol{y} + 0 + 2\lambda K\boldsymbol{\alpha}= 0. \end{split} \end{align}

最後に、$\boldsymbol{\alpha}$について整理する。

\begin{align} \begin{split} 2KK\boldsymbol{\alpha} - 2K\boldsymbol{y} + 2\lambda K\boldsymbol{\alpha} &= 0\\ KK\boldsymbol{\alpha} - K\boldsymbol{y} + \lambda K\boldsymbol{\alpha} &= 0\\ KK\boldsymbol{\alpha} + \lambda K\boldsymbol{\alpha} &= K\boldsymbol{y}\\ K\boldsymbol{\alpha} + \lambda \boldsymbol{\alpha} &= \boldsymbol{y}\\ (K + \lambda I_N)\boldsymbol{\alpha} &= \boldsymbol{y}\\ \boldsymbol{\alpha} &= (K + \lambda I_N)^{-1}\boldsymbol{y}. \label{eq:alpha} \end{split} \end{align}

新しい入力$\boldsymbol{x}$に対する出力は、推定した$\boldsymbol{\alpha}$を用いて以下のように予測できる。

\begin{align} \begin{split} \hat{y} &= (\Phi^{\top}\boldsymbol{\alpha})^{\top}\boldsymbol{\phi}(\boldsymbol{x}) \\ &= \boldsymbol{\alpha}^{\top}\Phi\boldsymbol{\phi}(\boldsymbol{x}) \\ &= \sum_{n=1}^{N} \alpha_n \boldsymbol{\phi}(\boldsymbol{x}_n)^{\top}\boldsymbol{\phi}(\boldsymbol{x}) \\ &= \sum_{n=1}^{N} \alpha_n k(\boldsymbol{x}_n, \boldsymbol{x}). \label{eq:yk} \end{split} \end{align}

すなわち、$F$次元の$\boldsymbol{w}$を用いず、学習データ数$N$を次元とする$\boldsymbol{\alpha}$で予測できるようになった。

2.2. カーネル関数の構成

ここまで、$F$個の基底関数$\phi$を用いた特徴ベクトルとしての$\boldsymbol{\phi}$同士の内積として、カーネル関数をボトムアップ的に定義した。

この場合、どのような基底関数を選定するかという線形回帰モデルのもう一つの課題が残る。 カーネル法を用いた線形回帰モデルでは、発想を逆転させ、カーネル関数をトップダウン的に先に直接定義することで、その内部の基底関数を陽に知らずにすませるというアプローチをとる。

ただし、この場合は定義したカーネル関数が正定値性を満たす必要がある。 すなわち、任意の$M$個の点から計算される、定義したカーネル関数による$M \times M$のグラム行列$K$の2次形式が常に非負(任意の$\boldsymbol{\mu} \in \mathbb{R}^M$に対して$\boldsymbol{\mu}^{\top}K\boldsymbol{\mu} \geq 0$)となる必要がある。

このような条件を満たすカーネル関数を直接定義できたならば、これはなんらかの特徴ベクトル同士の内積と考えることができる。 ありがたいことに、式\eqref{eq:yk}は基底関数$\phi$を使わず全てカーネル関数$k$で表現できているため、直接定義したカーネル関数があれば、基底関数の選定が不要となる(カーネルトリック)。

幸い、さまざまなカーネル関数が考案されているため、まずはそれらのカーネル関数を利用することとなる。 以下、多項式カーネルとガウスカーネルを紹介する。

多項式カーネル

多項式カーネルは$k(\boldsymbol{p}, \boldsymbol{q}) = (\boldsymbol{p}^{\top}\boldsymbol{q} + c)^{m}$の形をとるカーネル関数である。 上述のカーネルリッジ回帰を利用するにあたってはどのような特徴ベクトルが利用されているのかを陽に知る必要はないが、例えば$m=2,\boldsymbol{p},\boldsymbol{q} \in \mathbb{R}^2$であれば次のような特徴ベクトルが対応することが分かる。

対応する特徴ベクトルを調べるために、多項式カーネルを特徴ベクトルの内積$\boldsymbol{\phi}(\boldsymbol{p})^{\top}\boldsymbol{\phi}(\boldsymbol{q})$に変形する。

\begin{align} \begin{split} k(\boldsymbol{p}, \boldsymbol{q}) &= (\boldsymbol{p}^{\top}\boldsymbol{q} + c)^{2} \\ &= ((p_1, p_2)^{\top}(q_1, q_2) + c)^2 \\ &= (p_1q_1 + p_2q_2 + c)^2 \\ &= p_1^2q_1^2 + p_2^2q_2^2 + c^2 + 2p_1q_1p_2q_2 + 2cp_2q_2 + 2cp_1q_1\\ &= p_1^2q_1^2 + p_2^2q_2^2 + c^2 + 2p_1p_2q_1q_2 + 2cp_2q_2 + 2cp_1q_1\\ &= p_1^2q_1^2 + p_2^2q_2^2 + c^2 + \sqrt{2}p_1p_2\sqrt{2}q_1q_2 + \sqrt{2c}p_2\sqrt{2c}q_2 + \sqrt{2c}p_1\sqrt{2c}q_1\\ &= (p_1^2, p_2^2, c, \sqrt{2}p_1p_2, \sqrt{2c}p_2, \sqrt{2c}p_1)^{\top}(q_1^2, q_2^2, c, \sqrt{2}q_1q_2, \sqrt{2c}q_2, \sqrt{2c}q_1). \end{split} \end{align}

つまり、今回の例では、特徴ベクトルが$\boldsymbol{\phi}(\boldsymbol{x}) = (x_1^2, x_2^2, c, \sqrt{2}x_1x_2, \sqrt{2c}x_2, \sqrt{2c}x_1)$として扱われていたことが分かる。 言葉を返せば、多項式カーネルを用いると、このような変換を行う6つの基底関数を明示的に選定して地道に内積を取った場合と同様の結果を得られる。

なお、多項式カーネルの$m=1,c=0$の場合、これを線形カーネルと呼び、この時の特徴ベクトルは入力と等しい($\boldsymbol{\phi}(\boldsymbol{x}) = \boldsymbol{x}$)。

ガウスカーネル

ガウスカーネルは$k(\boldsymbol{p}, \boldsymbol{q}) = \exp(-\frac{\| \boldsymbol{p} - \boldsymbol{q}\|^2}{2\sigma^2})$の形をとるカーネル関数である。

以下では、ガウスカーネルにどのような特徴ベクトルが対応するかを確認する。 まず、ガウスカーネルを以下のように展開、変形する。

\begin{align} \begin{split} k(\boldsymbol{p}, \boldsymbol{q}) &= \exp(-\frac{\| \boldsymbol{p} - \boldsymbol{q}\|^2}{2\sigma^2}) \\ &= \exp(-\frac{(\boldsymbol{p} - \boldsymbol{q})^{\top}(\boldsymbol{p} - \boldsymbol{q})}{2\sigma^2}) \\ &= \exp(-\frac{(\boldsymbol{p}^{\top} - \boldsymbol{q}^{\top})(\boldsymbol{p} - \boldsymbol{q})}{2\sigma^2}) \\ &= \exp(-\frac{\boldsymbol{p}^{\top}\boldsymbol{p} - \boldsymbol{q}^{\top}\boldsymbol{p} - \boldsymbol{p}^{\top}\boldsymbol{q} + \boldsymbol{q}^{\top}\boldsymbol{q}}{2\sigma^2}) \\ &= \exp(-\frac{\boldsymbol{p}^{\top}\boldsymbol{p} - (\boldsymbol{q}^{\top}\boldsymbol{p})^{\top} - \boldsymbol{p}^{\top}\boldsymbol{q} + \boldsymbol{q}^{\top}\boldsymbol{q}}{2\sigma^2}) \\ &= \exp(-\frac{\boldsymbol{p}^{\top}\boldsymbol{p} - \boldsymbol{p}^{\top}\boldsymbol{q} - \boldsymbol{p}^{\top}\boldsymbol{q} + \boldsymbol{q}^{\top}\boldsymbol{q}}{2\sigma^2}) \\ &= \exp(-\frac{\boldsymbol{p}^{\top}\boldsymbol{p} - 2\boldsymbol{p}^{\top}\boldsymbol{q} + \boldsymbol{q}^{\top}\boldsymbol{q}}{2\sigma^2}) \\ &= \exp(\frac{-\boldsymbol{p}^{\top}\boldsymbol{p}}{2\sigma^2} + \frac{\boldsymbol{p}^{\top}\boldsymbol{q}}{\sigma^2} + \frac{-\boldsymbol{q}^{\top}\boldsymbol{q}}{2\sigma^2}) \\ &= \exp(\frac{-\boldsymbol{p}^{\top}\boldsymbol{p}}{2\sigma^2})\exp(\frac{\boldsymbol{p}^{\top}\boldsymbol{q}}{\sigma^2})\exp(\frac{-\boldsymbol{q}^{\top}\boldsymbol{q}}{2\sigma^2}) \\ &= \rho\exp(\frac{\boldsymbol{p}^{\top}\boldsymbol{q}}{\sigma^2})\psi \\ &= \rho\psi\exp(\frac{\boldsymbol{p}^{\top}\boldsymbol{q}}{\sigma^2}). \end{split} \end{align}

最後の2行では以降の展開を見やすくするため、$\rho=\exp(\frac{-\boldsymbol{p}^{\top}\boldsymbol{p}}{2\sigma^2}), \psi=\exp(\frac{-\boldsymbol{q}^{\top}\boldsymbol{q}}{2\sigma^2})$とおいた。

次に、$e^x$のマクローリン展開の公式($e^x = \sum_{i=0}^{\infty} \frac{x^i}{i!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \cdots$)を使い、特徴ベクトルの内積$\boldsymbol{\phi}(\boldsymbol{p})^{\top}\boldsymbol{\phi}(\boldsymbol{q})$に変形する。

簡単のため$\sigma=1$とすると、次のような式が得られる。

\begin{align} \begin{split} \rho\psi\exp(\boldsymbol{p}^{\top}\boldsymbol{q}) &= \rho\psi \left(1 + (\boldsymbol{p}^{\top}\boldsymbol{q})^1 + \frac{(\boldsymbol{p}^{\top}\boldsymbol{q})^2}{2} + \frac{(\boldsymbol{p}^{\top}\boldsymbol{q})^3}{6} + \ldots \right). \end{split} \end{align}

これは$c=0$の多項式カーネルを次数$m$を増やしながら無限回足したものである。 よって例えば、$\boldsymbol{p},\boldsymbol{q} \in \mathbb{R}^2$では、次のような無限次元の特徴ベクトルが対応することが分かる。

\begin{align} \begin{split} \rho\psi\exp(\boldsymbol{p}^{\top}\boldsymbol{q}) &= \rho\psi \left(1 + (\boldsymbol{p}^{\top}\boldsymbol{q})^1 + \frac{(\boldsymbol{p}^{\top}\boldsymbol{q})^2}{2} + \frac{(\boldsymbol{p}^{\top}\boldsymbol{q})^3}{6} + \ldots \right) \\ &= \rho\psi \left(1 + (p_1q_1 + p_2q_2) + \frac{p_1^2q_1^2 + p_2^2q_2^2 + \sqrt{2}p_1p_2\sqrt{2}q_1q_2}{2} + \frac{p_1^3q_1^3 + p_2^3q_2^3 + \sqrt{3}p_1^2p_2\sqrt{3}q_1^2q_2 + \sqrt{3}p_1p_2^2\sqrt{3}q_1q_2^2}{6} + \ldots \right) \\ &= \rho\left(1, p_1, p_2, \frac{p_1^2}{\sqrt{2}}, \frac{p_2^2}{\sqrt{2}}, \frac{\sqrt{2}p_1p_2}{\sqrt{2}}, \frac{p_1^3}{\sqrt{6}}, \frac{p_2^3}{\sqrt{6}}, \frac{\sqrt{3}p_1^2p_2}{\sqrt{6}}, \frac{\sqrt{3}p_1p_2^2}{\sqrt{6}}, \ldots \right)^{\top}\psi\left(1, q_1, q_2, \frac{q_1^2}{\sqrt{2}}, \frac{q_2^2}{\sqrt{2}}, \frac{\sqrt{2}q_1q_2}{\sqrt{2}}, \frac{q_1^3}{\sqrt{6}}, \frac{q_2^3}{\sqrt{6}}, \frac{\sqrt{3}q_1^2q_2}{\sqrt{6}}, \frac{\sqrt{3}q_1q_2^2}{\sqrt{6}},\ldots \right) \\ &= \rho\left(1, p_1, p_2, \frac{p_1^2}{\sqrt{2}}, \frac{p_2^2}{\sqrt{2}}, p_1p_2, \frac{p_1^3}{\sqrt{6}}, \frac{p_2^3}{\sqrt{6}}, \frac{p_1^2p_2}{\sqrt{2}}, \frac{p_1p_2^2}{\sqrt{2}}, \ldots \right)^{\top}\psi\left(1, q_1, q_2, \frac{q_1^2}{\sqrt{2}}, \frac{q_2^2}{\sqrt{2}}, q_1q_2, \frac{q_1^3}{\sqrt{6}}, \frac{q_2^3}{\sqrt{6}}, \frac{q_1^2q_2}{\sqrt{2}}, \frac{q_1q_2^2}{\sqrt{2}},\ldots \right). \end{split} \end{align}

ガウスカーネルでは、このような無限個の基底関数を用意して内積を地道に計算した結果が、$k(\boldsymbol{p}, \boldsymbol{q}) = \exp(-\frac{\| \boldsymbol{p} - \boldsymbol{q}\|^2}{2\sigma^2})$のみの計算から得られるとも考えられる。

3. Random Fourier Features(乱択化フーリエ特徴)

カーネルリッジ回帰による入力$\boldsymbol{x}$に対する予測は式\eqref{eq:alpha}\eqref{eq:yk}より、$\hat{y} = \sum_{n=1}^{N} \alpha_n k(\boldsymbol{x}_n, \boldsymbol{x}), \boldsymbol{\alpha} = (K + \lambda I_N)^{-1}\boldsymbol{y}$となるのであった。 カーネルリッジ回帰では、$F \gg N$となるような学習データ数$N$に対し十分大きい$F$個の基底関数を用いる場合に、双対表現によってパラメータ数を$N$に抑えつつ、カーネル関数の導入によって$F$次元の特徴ベクトルの直接的な算出を回避できた。

しかしながら、カーネルリッジ回帰は、学習データ数$N$に対して計算量が指数的に増加してしまう課題がある。 これは、グラム行列$K$のサイズが$N \times N$であるため、$\boldsymbol{\alpha}$の計算にあたって、必要なカーネル関数の計算が$N^2$のオーダーで増加することからも分かる。 また、逆行列の計算も$K$のサイズに応じて計算量が増加する。 加えて、$\hat{y}$の計算にあたっても、新しい入力$\boldsymbol{x}$に対して$N$回のカーネル関数の計算が都度必要となってしまう。

Random Fourier Featuresは、ある確率分布からのサンプリング結果でカーネル関数とグラム行列を近似することで、上述の課題を解決する、高速化のための手法である。

この手法では、$\mathbb{R}^D$上のカーネル関数$k(\boldsymbol{p},\boldsymbol{q})$が$\boldsymbol{p}$と$\boldsymbol{q}$の差の形($k(\boldsymbol{p}-\boldsymbol{q})$)で表せるとき、このカーネル関数が、ある確率密度関数$p(\boldsymbol{\omega})$のフーリエ変換で表せることを利用する。

\begin{align} \begin{split} k(\boldsymbol{p},\boldsymbol{q}) &= k(\boldsymbol{p} - \boldsymbol{q})\\ &= \int_{\mathbb{R}^{D}} p(\boldsymbol{\omega}) \exp(i \boldsymbol{\omega}^{\top}(\boldsymbol{p} - \boldsymbol{q}))d\boldsymbol{\omega} \\ &= \mathbb{E}_{\boldsymbol{\omega}}[\exp(i \boldsymbol{\omega}^{\top}(\boldsymbol{p} - \boldsymbol{q}))] \\ &= \mathbb{E}_{\boldsymbol{\omega}}[\cos(\boldsymbol{\omega}^{\top}(\boldsymbol{p} - \boldsymbol{q}))] \\ &= \mathbb{E}_{\boldsymbol{\omega},b}[\sqrt{2}\cos(\boldsymbol{\omega}^{\top}\boldsymbol{p} + b) \cdot \sqrt{2}\cos(\boldsymbol{\omega}^{\top}\boldsymbol{q} + b)] \\ &\approx \frac{1}{R} \sum_{r=1}^{R} \sqrt{2}\cos(\boldsymbol{\omega}_r^{\top}\boldsymbol{p} + b_r) \cdot \sqrt{2}\cos(\boldsymbol{\omega}_r^{\top}\boldsymbol{q} + b_r). \end{split} \end{align}

ここで、$\boldsymbol{\omega} \sim p(\boldsymbol{\omega}), b \sim \text{Uniform}(0, 2\pi)$である。 なお、$p(\boldsymbol{\omega})$は利用するカーネル関数によって異なるが、ガウスカーネルの場合、$\boldsymbol{w} = (w_d)^{1 \leq d \leq D}, w_d \sim \mathcal{N}(0, \sigma^2)$となる。

最後の行は、この確率分布の期待値($=$カーネル関数の結果)を$R$個のサンプリング結果の平均で近似することを示している。

すなわち、各サンプルから求めた結果を、$z_r(\boldsymbol{x}) = \cos(\boldsymbol{\omega}_{r}^{\top}\boldsymbol{x} + b_r)$、$R$個の$z_r$を$\boldsymbol{z}(\boldsymbol{x}) = \sqrt{\frac{2}{R}}(z_1(\boldsymbol{x}),\ldots,z_R(\boldsymbol{x}))^{\top}$とおくと、カーネル関数$k$の近似$\hat{k}$が$\hat{k}(\boldsymbol{p},\boldsymbol{q}) = \boldsymbol{z}(\boldsymbol{p})^{\top}\boldsymbol{z}(\boldsymbol{q})$のように得られる。 また、学習データ$X$に対する$\boldsymbol{z}$の集合を$Z = (\boldsymbol{z}(\boldsymbol{x}_1)^{\top}, \ldots, \boldsymbol{z}(\boldsymbol{x}_N)^{\top})^{\top} \in \mathbb{R}^{N \times R}$とすると、$\hat{K} = ZZ^{\top}$の操作によって$N \times N$行列の各要素がカーネル関数$k$の近似$\hat{k}(\boldsymbol{x}_i, \boldsymbol{x}_j) = \boldsymbol{z}(\boldsymbol{x}_i)^{\top}\boldsymbol{z}(\boldsymbol{x}_j)$となるグラム行列$K$の近似$\hat{K}$を得られる。

よって、これらの近似を用いたカーネルリッジ回帰のパラメータ$\boldsymbol{\alpha}$の近似$\hat{\boldsymbol{\alpha}}$は、$\hat{\boldsymbol{\alpha}} = (\hat{K} + \lambda I_{N})^{-1}\boldsymbol{y}$となる。 ただし、この手法では、$\hat{K} = ZZ^{\top}$であることを利用して、計算量を学習データ数$N$ではなくサンプリング数$R$のオーダーに変えることができる。 そのため、$R \ll N$であるならば、非常に効率よく予測が可能となる。

以下に、$\hat{K}$や$\hat{\boldsymbol{\alpha}}$を消去していく経過と合わせて、この手法における予測式を示す。

\begin{align} \begin{split} \hat{y} &= \sum_{n=1}^{N} \hat{\alpha}_n \hat{k}(\boldsymbol{x}_n, \boldsymbol{x}) \\ &= \sum_{n=1}^{N} \hat{\alpha}_n \hat{k}(\boldsymbol{x}, \boldsymbol{x}_n) \\ &= \sum_{n=1}^{N} \hat{\alpha}_n \boldsymbol{z}(\boldsymbol{x})^{\top}\boldsymbol{z}(\boldsymbol{x}_n) \\ &= \boldsymbol{z}(\boldsymbol{x})^{\top} \sum_{n=1}^{N} \hat{\alpha}_n \boldsymbol{z}(\boldsymbol{x}_n) \\ &= \boldsymbol{z}(\boldsymbol{x})^{\top} Z^{\top} \hat{\boldsymbol{\alpha}} \\ &= \boldsymbol{z}(\boldsymbol{x})^{\top} Z^{\top} (\hat{K} + \lambda I_{N})^{-1}\boldsymbol{y} \\ &= \boldsymbol{z}(\boldsymbol{x})^{\top} Z^{\top} (ZZ^{\top} + \lambda I_{N})^{-1}\boldsymbol{y} \\ &= \boldsymbol{z}(\boldsymbol{x})^{\top} (Z^{\top}Z + \lambda I_{R})^{-1}Z^{\top} \boldsymbol{y}. \end{split} \end{align}

よって、$A=(Z^{\top}Z + \lambda I_{R}) \in \mathbb{R}^{R \times R}$、$\boldsymbol{b} = (Z^{\top} \boldsymbol{y}) \in \mathbb{R}^{R}$、$\boldsymbol{\beta} = A^{-1}\boldsymbol{b}$として、$\hat{y} = \boldsymbol{z}(\boldsymbol{x})^{\top} \boldsymbol{\beta}$と予測できる。 $Z$は$N \times R$であるものの、逆行列のサイズは$R \times R$となること、$\hat{y}$の計算も、新しい入力$\boldsymbol{x}$に対して$R$回の計算で済む$\boldsymbol{z}(\boldsymbol{x})$のみで良いことから、計算量が抑えられることが分かる。

なお、最後の行では逆行列の補題($P(I_N + QP)^{-1} = (I_R +PQ)^{-1}P, P \in \mathbb{R}^{R \times N}, Q \in \mathbb{R}^{N \times R}$)を用いた。

参考

線形回帰モデル

カーネル法による線形回帰モデル

Random Fourier Features

gonum/matパッケージを直感的に操作するMatrix Adapterをつくった

gonum/matによる行列計算を幾分か直感的に扱える薄いラッパーを作りました。 具体的には、計算結果用に空の行列を予め用意するのではなく、計算結果を戻り値で受け取れるように統一します。

  • Matrix Adapter: Small adapter which provides method signatures that allow intuitive operation with fewer lines of code for gonum/mat.

背景と課題感

GonumプロジェクトのmatパッケージはGo言語での行列計算ライブラリを提供してくれています。 こういった正確さと速度の求められる数値計算の処理には、(趣味は別として)自作ではなく、多くの人に使われ実績のあるライブラリを採用したいことから、このパッケージを利用しています。

非常に便利に使わせていただいている一方で、自分の場合、スムーズに書けないことがありました。 理由としては、計算結果の受け取り方法に対する一貫性の崩れがあるだろうと考えています。

matパッケージでは、予め空の行列を用意し、これをレシーバーとして計算対象となる行列を引数で渡します。

var c mat.Dense
c.Product(a, b)

元の行列が維持されるこの設計は非常にありがたいです。 しかしながら、一部の関数(例えば Dense.T)は結果が戻り値として得られます。

ct := c.T()

この一貫性の崩れは不変と可変の混在にあるのではないかと考えています。 gonum/matパッケージでは、引数で渡す行列は計算操作に対して不変とされています。 これは、関数のパラメータの方が、mat.Matrixインターフェースであることからも読み取れます。 実際、このインターフェースには、Dims(), At()といった参照系かレシーバーを壊さないT()のみが用意されています。

一方で、このインターフェースを実装したmat.Denseなどは自身をレシーバーとして内容を変更する操作を認めています。 この差異により、mat.Matrixインターフェースのシグネチャの一つであるT()は戻り値を返すが、Denseの関数ではレシーバーを変更するという振る舞いの違いがあるのではないかと思われました。

gonum/matパッケージではほとんどの関数が空の行列を予め用意する方式に従っているため、慣れれば問題ない程度ではありますが、久しぶりに使う場合など、多少まごつくことが何度かありました。 個人的に、Go言語で何か書くときは迷わず書きたいという欲求があり、迷わないため一貫性のあるラッパーを作ることとしました。

Matrix Adapter

今回は、計算結果を戻り値で受け取れるように統一します。 これにより、利用側からはDenseらも不変であるかのように扱え、一貫性という側面から認知負荷が減ると考えるためです。

Matrix Adapterを適用した場合、先ほどの例は以下のようになります。 cがレシーバーではなく、先ほどは引数となっていたaがレシーバーとなっていることに注意してください。 cは戻り値として受け取ることになりました。

c := a.Product(b)

実装と使い方

Adapterの実装は単純明快で、元の構造体を埋め込み(embedding)し、結果を戻り値で返すように関数のシグネチャを変更しました。 変更が不要なものは移譲されます。 いわゆるGoFのデザインパターンにおけるAdapterパターンというやつです。

type Dense struct {
	*mat.Dense
}

func (m *Dense) Add(b mat.Matrix) *Dense {
	var dense mat.Dense
	dense.Add(m.Dense, b)
	return &Dense{&dense}
}

現状、DenseとVecDenseに対するAdapterを提供しています。 既存と同名のNewDense()NewVecDense()を使って、ラップされたDenseやVecDenseを作成できます。

package main

import (
	"fmt"

	"github.com/monochromegane/mat/adapter"
)

func main() {
	m := adapter.NewDense(2, 2, []float64{1.0, 2.0, 3.0, 4.0})
	fmt.Printf("%v\n", m)
	// ⎡1  2⎤
	// ⎣3  4⎦
}

ちなみに、提供されるDenseとVecDenseはfmt.Stringerインターフェースを実装し、行列の内容を整形して出力するようにしています。

ここで、少し実践的な例として、リッジ回帰によるパラメータ推定($\hat{\theta} = (X^{\top}X + \lambda I)^{-1} X^{\top}Y$)を実装し、比較してみます。

Matrix Adapterでの実装

	X, Y := syntheticData(N, theta) // Return adapter.Dense

	I := mat.NewDiagDense(3, []float64{1.0, 1.0, 1.0})
	reg := DenseCopyOf(I).Scale(lambda)

	XTXinv, _ := X.Transpose().Product(X).Add(reg).Inverse()
	XTY := X.Transpose().Product(Y)

	estimated := XTXinv.Product(XTY)

gonum/matでの実装

	X, Y := syntheticData(N, theta) // Return adapter.Dense

	XTXinv := mat.NewDense(3, 3, nil)
	XTXinv.Product(X.T(), X)

	I := mat.NewDiagDense(3, []float64{1.0, 1.0, 1.0})
	reg := mat.DenseCopyOf(I)
	reg.Scale(lambda, reg)

	XTXinv.Add(XTXinv, reg)
	XTXinv.Inverse(XTXinv)

	XTY := mat.NewDense(3, 1, nil)
	XTY.Product(X.T(), Y)

	estimated := mat.NewDense(3, 1, nil)
	estimated.Product(XTXinv, XTY)

この例では、gonum/matでの実装に比べてMatrix Adapterでの実装が、結果用のDenseの準備が省略できたこと、各関数で受け取る引数が減ったことなどから、幾分か簡潔に記述できているかと思います。

なお、Adapterでの実装では、Method Chainによる行数の短縮も見てとれます。 これについては、戻り値を返す実装としたことで副次的に得られた、本Adapterの特徴です。 Go言語におけるMethod Chainは、errorを含む多値の戻り値との相性から、積極的に採用されていないと認識しています。 ただ、今回は元のパッケージが各計算においてerrorを返さないものが多く、多値にならない関数が多くできたため、結果としてMethod Chainがつながる場合ができています(Inverse()などerrorを返すものもあるため全部は繋げません)。 この辺りのエラー処理については、一考の価値があると思いますが、現時点で本Adapterの対象外(従来パッケージを踏襲)としています。

相互運用性

Adapterの提供する関数でも、引数はmat.Matrix(やmat.Vector)を使うため、既存のラップしていないものを入力として受け取れます。 また、これらのAdapterは、mat.Dense(やmat.VecDense)構造体を埋め込んでいるため、mat.Matrix(やmat.Vector)の実装を満たします。 よって、ラップされたadapter.Dense(やadapter.VecDense)を既存の関数の入力として渡すことができます。

また、T()mat.Matrixとして維持しなければならない関数であることから、同等のTranspose()を提供しています。 これにより、転置行列がレシーバーとなるような呼び出しであっても、adapter.Denseとして振る舞うことができるようになり、Matrix Adapterとの親和性が向上します。

// X.T().Product(Y) is invalid due to mat.Matrix has no method Product.
XTY := X.Transpose().Product(Y) // Valid

まとめ

本エントリでは、gonum/matパッケージを直感的に操作するためのMatrix Adapterを紹介しました。 本Adapterの作成とエントリ執筆において、「直感的でない」と主観的に感じる理由について、不変と可変の混在に起因するものではないかなと言語化できたのがよかったかなあと思います。

自分の利用範囲だと、DenseとVecDenseで事足りる場合が多いのですが、必要に応じて対象を増やしていこうかと思います。

参考

  • Go + Gonum を使った行列計算まとめ
    • 関数の直感性を上げるための独自関数や、行列のフォーマットなどを参考にさせていただきました。
  • gorgonia/tensor
    • gonum/matではないGo言語の行列計算パッケージ。戻り値で結果を受け取れたりerrorも返すので本Adapterの目指すところに近いとは思います。速度含めて検証が必要なのもあり、今回は慣れて使っている方が多いであろうgonum/matをラップする方式を採用しました。

2021

2021年は、自分の研究テーマとひたすら向き合った年となった。 昨年10月より博士後期課程に在学していることもあり、まずは1本国際会議に通すべく、自身の提案手法の改善、評価と従来手法との比較分析を、1年間ひたすら続けていた。 研究の進捗の節目ごとに投稿していた国際会議は、残念ながら3回投稿して全てリジェクトとなってしまったが、これらのフィードバックや方式の改善の結果、論文の質や提案手法の性能はこの1年間で随分上がったのではないかと思う。

実際に、これらの進捗を議論すべく報告した、国内の2回の研究会では3つの賞を受賞することができ、客観的にも、自分の研究テーマとの向き合ってきた結果が出てきていると思える。 昨年度の受賞は、優秀プレゼンテーション賞という発表の分かりやすさの側面が強かったが、今年は、それに加え、座長や運営委員による選定という、より内容に踏み込んだ評価の上での受賞であり、非常に嬉しかったし、国際会議挑戦を継続するにあたって励みになった。

来年は引き続き国際会議への挑戦と研究の発展を進めたい。 そのために、結果に一喜一憂せずに淡々と継続することを心がけていく。 また、手法改善の基盤となる数学的な能力向上や先行研究のサーベイは一過性ではなく計画的に長期的に取り組めるような枠組みを作り上げたい。 加えて、来年度は、個人のみの研究の位置付けからもう少し視座を高め、例えば研究所の取り組みと各研究員の研究、会社のサービスやビジョンとの関係性などから、方針や行動を見定め、それらに向かって導いたり知ってもらえるような振る舞いなど、今よりも先を見通し、今よりも大きく影響を与えることも意識していきたい。

2022年からは、支えてくれる周りの人にも、恩返しだったり良い影響を与えることをできるようになりたいと思う。 来年もよろしくお願いします。

実績

以下、実績を列挙する。

表彰

2021年は2つの研究会で3つの賞を受賞できた。 聴講者だけでなく運営委員や座長による評価をいただけるような研究を継続的に出せるようになっていることは素直に嬉しい。 また、研究所の共著論文でも2つの賞を受賞しており、研究所全体の盛り上げにも貢献できてよかったと思う。

論文

招待講演1本、研究報告2本。 実際には国際会議3回投稿、投稿中の国内ジャーナル1本があり、体感的な執筆量は例年と変わらない程度であったと思う。 また、研究報告のラストオーサーを2本、国内査読付き論文と国際会議(ワークショップ)論文でそれぞれ1本づつ共著を務めた。

  1. 三宅 悠介, 峯 恒憲, 仮想的な探索を用いて文脈や時間の経過による番狂わせにも迅速に追従する多腕バンディット手法, ARG Webインテリジェンスとインタラクション研究会 第17回研究会予稿集, No.17, pp.19-24, Dec 2021. [論文] [発表資料]
  2. 三宅 悠介, 峯 恒憲, Synapse: 文脈と時間経過に応じて推薦手法の選択を最適化するメタ推薦システム, 研究報告知能システム(ICS), Vol.2021-ICS-204, No.9, pp.1-8, Sep 2021. [論文] [発表資料]
  3. 三宅 悠介, 栗林 健太郎, (招待講演) なめらかなシステムと運用維持の未来, マルチメディア,分散,協調とモバイル(DICOMO2021)シンポジウム論文集, 2021, p.1509, Jun-Jul 2021.[論文] [発表資料]

国内発表

技術イベント、研究会での発表をそれぞれ1回(学会の研究会、シンポジウムを除く)。 今年はFukuoka.goもWSAも開催が少なかったこともあり、随分控えめになってしまった。 来年はもう少し機会を見つけて登壇していきたい。

  1. 三宅 悠介 go:embedでExplainable Binaryを作る, Fukuoka.go#17(オンライン開催), 2021年6月.
  2. 三宅 悠介 非定常な多腕バンディット問題において効率的に変化を察知する方式の検討, Web System Architecture 研究会 (WSA研) #8, 2021年6月.

OSS

Fukuoka.go用に書いたツールが1本。 先行研究の実装など随分とコードは書いている気がするので研究とOSSもうまくつないでいきたいところ。

コミュニティ活動

今年よりこれまでのFukuoka.goに加え、学会系の活動も手伝うようになった。 具体的には研究会の運営委員への就任に伴う運営従事の他、査読、座長、シンポジウムのプログラム委員などを務めた。

ブログ

2本。昨年までに比べるとかなり少なめだが、研究の進め方シリーズとして集中的サーベイは研究所のみんなに紹介するなど役立ったと思う。 このような手探りからやり方に昇華できたものは今後もブログにまとめていきたい。

非定常な多腕バンディット問題において効率的に変化を察知する方式の検討

このエントリは、第8回 Web System Architecture 研究会 (WSA研)の予稿です。

非定常な多腕バンディット問題において効率的に変化を察知する方式の検討

はじめに

適応的なシステムの実現には、利用者と情報システムが互いの状態をよく理解するためのコミュニケーションと、それに応じた振る舞いの変更が必要となる。 一方で、そのコミュニケーションから得られる情報や利益の価値を考慮しなければならない環境では、確実な情報に基づく振る舞いを選択しつつ、まだ得られていない情報を引き出すために、価値の低いコミュニケーションを敢行しなければならない。

これは、多腕バンディット問題として定式化できる。 多腕バンディット問題では、振る舞いの選択肢のことを腕と呼び、ある時点までの情報をもとに有効な腕を選択することを「活用」、腕の可能性を探るために有効ではない腕を選択することを「探索」と呼ぶ。 それぞれの腕はある確率分布に従い報酬を生成する。 中でも、選択肢の相対的な有効性が時間経過とともに変化する問題設定は非定常な多腕バンディット問題と呼ばれ、いくつかの解法が提案されている。

非定常な多腕バンディット問題に対する解法には、腕の有効性の変化に応じた評価の更新が重要とされてきた。 しかしながら、選択による機会損失の低減を目的とした多腕バンディット問題の設定では、ある時点で有効性の低い選択肢が利用される機会は少なく、腕の有効性の変化を察知する、それ自体がまず難しい。

本研究では、このような非定常な多腕バンディット問題における変化を素早く察知するにあたり、探索による機会損失を抑制した、効率的な方式を検討する。 なお、多腕バンディット問題の設定は、同時に文脈付きの問題設定に拡張することができるが、課題の本質は同じであること、方式検討の容易性から、本方向では文脈の考慮は行わない。

非定常な多腕バンディット問題の解法における、変化察知の課題

非定常な多腕バンディット問題への解法では、腕の報酬分布が変化した際に、過去に観測した報酬に捉われずに腕の評価を迅速に更新しなくてはならない。 この問題の解法には大きく4つのアプローチがある。 一つ目は、腕の報酬分布が変化することを前提にして、観測時点からの経過に応じて腕の評価に重み付けをするアプローチである(減衰型)。 二つ目も、同様の前提において、新しく観測した報酬から一定の期間のみの情報で報酬分布を評価する(ウィンドウ型)。 三つ目は、腕の報酬分布の変化を契機として、腕を再評価するものである(変化検出型)。 このアプローチでは、変化検出の手法を用いて腕の報酬の変化を検出し、変化前の観測を取り除くことで、新しく観測された報酬を重視する。 これは変化検出による可変のウィンドウ型とみなすこともできる。 四つ目は、現時点の腕の評価を継続的に推定するものである。 このアプローチでは、腕の状態として状態空間モデルを仮定し、カルマンフィルタや粒子フィルタを推定に用いる。

これらの全てのアプローチは、変化後の報酬分布から得られる報酬のサンプルを一定数必要とする。 選択による機会損失の低減を目的とした多腕バンディット問題の設定では、ある時点で評価の高い腕を最も多く活用する。 そのため、評価の高い腕が、ある時点で有効性が低くなるようなケースでは、十分な報酬のサンプルを観測することができ、各アプローチは有効に働く。 反対に、評価の低かった腕が、ある時点で有効性が高くなるケースでは、その腕に対する報酬のサンプルを得るまでに時間が掛かり、機会損失の発生に繋がると考えられる。 例えば、ECサイトの推薦アルゴリズムのコールドスタートのような、一定の嗜好情報が蓄積されることでその有効性を増すような選択肢がある場合に、この問題が発生する。

この問題に直接挑んだ先行研究[1][2]では、いずれもなんらかの非定常な多腕バンディットの解法に従い腕の選択を行うが、一定の割合で、ランダムに腕を選択することで、腕の選択の偏りの解消を試みている。 また、上述のアプローチのうち、報酬の観測数の上限を変化させるような、減衰型、ウィンドウ型、変化検出型でも、間接的に腕の選択の偏りが緩和される。 なぜなら、多くの多腕バンディットの解法では、観測数の少なさを評価の不確かさと捉え、探索を促すからである。

これらの探索を増やすアプローチは、トレードオフが発生する。 すなわち、相対的な腕の評価が逆転しない期間では、その期間中の探索が機会損失につながってしまう。 そのため、評価の低い腕の有効性の変化を素早く察知できるよう探索を行いつつ、その探索に伴う機会損失を減らすことが求められる。

非定常な多腕バンディット問題の解法における、効率的な変化察知の方式の検討

本研究では、評価の低い腕に対する変化の察知について、素早さと機会損失低減の観点を両立させるため、この探索行為を多腕バンディット内の多腕バンディットとみなす。 そして、この多腕バンディット内の多腕バンディットの評価基準に、腕の不安定性と、将来性を採用することで、探索時の機会損失低減を目指す。

本報告では、先行研究の一定の割合で実施される探索行為を対象として機会損失の改善を目指す。 すなわち、腕の選定の比率が同一となるようなランダム選定ではなく、腕の不安定性と将来性を基準に、腕の選定の比率を変化させる。 提案手法では、腕の不安定性と将来性を扱うために、獲得報酬の時系列予測を行う。 時系列予測には、将来性の変化を扱えるよう少なくともトレンド成分を扱うことができ、不安定性を扱えるよう予測の幅も扱えるようなモデルが望ましい。 そこで、これらを満たすベイズ型統計モデルを採用する。 扱う報酬の形式により、カルマンフィルタや粒子フィルタを選択可能である。 探索には、各腕でn時点先の評価を予測値と信用区間に基づき腕の不安定性と将来性が高い腕を選定する。 予測値が将来性、信用区間の広さが不安定性に該当する。 なお、これらのモデルでは時系列予測の時点が進むにつれ、その信用区間が広がっていくことから、無限の将来を想定した腕の選定では、先行研究と同じ振る舞いになると考えられる。

評価

カルマンフィルタベースの提案方式のコンセプト実装し、トイ・シミュレーションで機会損失を抑えられることを評価した。

シミュレーション設定

評価環境として、腕の数が3、1000回の試行において、期間中に有効性の最も低かった腕が最も高くなるよう設定した。 なお、このシミュレーションでは、先行研究における一定数の割合の探索の試行のみを取り出したことを想定している。

plot_true_reward

評価方法

そして、以下のそれぞれの方式に対して、機会損失を抑える性能と変化を素早く察知する性能を評価した。

  • random: ランダムな探索(予測できない未来を想定)ε-Greedy(ε=1.0)
  • epsilon: 現在の情報に基づく探索(予測できない未来を想定)ε-Greedy(ε=0.1)
  • state model: 予測に基づく探索(予測できる未来を想定)ε-Greedy(ε=0.1)だが活用時はカルマンフィルタによる100期先予測の値で選定する

なお、本報告の提案手法のコンセプト実装では、将来性のみを扱い、不安定性の考慮はできていない。

本評価では、機会損失を抑える性能を、累積リグレットの低さによって評価する。 本報告で、累積リグレットとは、各時点での最適な腕から得られる期待報酬額と方策が選定した腕から得られた報酬額の差の合計のことを指す。 また、変化を素早く察知する性能を、腕の真の有効性が切り替わった時点以降で新しい最適な腕を選択した回数が一定数を超えるまでの期間の短さによって評価する。

なお、準備期間の関係上、シミュレーションは複数回行っていないため、変動する可能性がある。

機会損失を抑える性能の評価

各方式の累積リグレットの推移を下図に示す。

plot_cum_regret

均等に腕を選択するrandomではおおよそ線形にリグレットが増加する。 epsilonでは、変化前のリグレットの増加は抑えられるが、変化後には追従が遅れ、リグレットが大きく増加した。 これは、腕の選定の偏りによって探索が十分に行えないことと、過去データにひきづられて腕の評価の更新が遅れていることから発生していると考えられる。

提案のstate modelでは、シミュレーション初期にrandomと同じ程度のリグレットの増加が確認された。 これは、予測に基づく活用が精度が低かったことに起因する。 50時点以降は予測が安定することで、リグレットの増加がepsilonと同等になった。 そして、変化後であっても、リグレットの増加が抑えられていることが確認できる。 これは、予測によって、将来性がある探索すべき腕を決定し、評価の更新をいち早く行えたためである。

変化を素早く察知する性能の評価

切り替わり後の最適な腕を選択した累積回数の推移を下図に示す。

plot_sampled_new_arm

均等に腕を選定するrandomではおおよそ線形に腕が選定される。 本研究の課題設定では、この増加より大きいことが望まれる。 epsilonでは、腕の有効性の変化に追従できず、ε-Greedyの探索割合に応じた増加にとどまった。 これは、腕の選択肢が増加するほど、探索が行われない可能性が増すことも示している。 提案のstate modelでは、予測によって、将来性がある探索すべき腕を決定し、該当の腕に対する探索がrandomと比べて多く行われた。 これにより、変化の察知が素早く進むことが期待できる。

腕の有効性の変更に対する、提案方式の100時点先の予測を下図に示す。

plot_predicted_reward

本評価のシミュレーション設定は非常に単純なものであったため、予測がおおよそ正しかったことがわかる。

まとめ

本報告では、非定常な多腕バンディットにおける変化の察知の課題を整理し、腕の不安定性と将来性に着目した予測型の多腕バンディット方策を提案した。 将来性を考慮可能なコンセプト実装では、シミュレーションにおいて、累積リグレットを抑えた素早い変化察知の可能性が示唆された。 今後はコンセプト実装に、不安定性の考慮を組み込むこと、そのためにε-Greedyではなくトンプソンサンプリングをベースにした手法との統合を進めたい。 また、文脈を考慮した場合での実装とシミュレーションの拡張を行う。 加えて、探索割合自体を環境の変化の度合いに応じて変動させる方式も検討する。

参考文献

  • [1] Fang Liu, Joohyun Lee, and Ness Shroff. 2018. A change-detection based framework for piecewise-stationary multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 32.
  • [2] Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. 2019. Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 418–427.

発表スライド

発表を終えて

Archives