にっき

勉強したことや思ったことを書きます

ゲーム「マリーのアトリエ」をめぐって

お久しぶりです.差し迫った締切がないせいで,研究の方は低空飛行で頑張っています.

ここ最近「マリーのアトリエ」をスマホで遊んでいて,色々なことを書きたくなったので書きます.

結論

マリーのアトリエが面白いのでやりましょう.スマホなら1200円買い切りです.PSアーカイブスなら617円です.

マリーのアトリエ」とは

1997年にガストからプレイステーションで発売された,現在「アトリエシリーズ」と呼ばれているシリーズ第一作目です.

www.gamecity.ne.jp

当時はファイナルファンタジー7テイルズオブデスティニーなどの(今でも名前が通るような)大作RPGが多く発売された中で,そのようなRPG作品とは一線を画するコンセプトを打ち出しました.本作品のキャッチコピーは

世界を救うのはもうやめた

です.このコピーが語るとおり,このゲームは世界を救う王道RPGではありません.舞台こそ錬金術の世界というファンタジー色の強いものですが,主人公マルローネ(マリー)は錬金術アカデミーにおける歴代最悪の落ちこぼれ.その落ちこぼれがなんとか卒業するために,5年間錬金術の研究に打ち込む…というストーリーです.

何が面白いのか

ストーリーでも書いたとおり,マリーの目標は「アカデミーからの卒業」です.が,卒業のために何をしなければいけないかは明確には提示されません.裏を返せば5年というゲーム内時間を好きに使えます.

f:id:ehlfin:20180307212059p:plain
酒場「飛翔亭」.色々な人の頼み事を引き受けたり,他のキャラと話をしたりして日々が進みます.

f:id:ehlfin:20180307211700p:plain
調合画面.アイテムは全部で100種類.

f:id:ehlfin:20180307211713p:plain
素材を手に入れるために外出.

f:id:ehlfin:20180307211748p:plain
外出中に敵に襲われることもあるでしょう.

f:id:ehlfin:20180307211759p:plain
他のキャラとのイベントが起こることも.

このような性格を持ったゲームなので,特に初見プレイと2回め以降のプレイで大きな差異が生まれます.この2種類の面白さ両方が「マリーのアトリエ」の面白さだと私は考えています.

初見プレイではアイテムやイベントについて,プレイヤーは情報を持たずにスタートします.さながらマリーと同じ目線で,何を作るべきか,どこに新しいアイテムの情報があるかを手探りで考えていく事になります.時に予想しないイベントが起きたりするわけですが,そういう自由度の高さが大きなウリの1つです.

2回め以降は,(マリーはともかく)プレイヤーは多くの情報を持った上でスタートします.それらの情報をもとにして,5年という時間をより効率よく設計することが可能になるわけです.色々なイベントのフラグをある程度きちんと管理するパズルゲームのような面白さに変わります.その時に(私みたいなゆるいプレイヤーは)攻略サイトなどを見てもよいでしょうし,見ないで何度か試行錯誤するのも楽しいと思います.

慣れた人なら1周数時間でクリアできる程度の,適度な分量のゲームなので,周回する抵抗がそこまで高くないのもポイントです.

個人的な思い出その他

私がこのゲームに触れたのは随分昔のこと,小学生のときです.当時の私には自由度が高すぎて難しかったのをよく覚えています.確かメガフラム(上手くやれば中盤はじめくらいで作れる爆弾アイテム)を卒業間際に作って,普通の卒業エンドを見たような記憶があります.

そんな個人的な思い出もあって,今回このゲームが移植されるにあたり遊んでみようと思った次第です.思い出補正も入っているのかもしれませんが,とても楽しく遊べました.時代を感じさせる絵柄も,良いですよね…

他のアトリエシリーズについて

実は私,アトリエシリーズはこのマリーと,二作目のエリーしか遊んだことがありません.ロロナ?トトリ?アーシャ?なにそれおいしいの?

おそらく年齢不相応なプレイ歴なのは千万承知なのですが,そういうわけで他のアトリエシリーズを遊んだ方がどれくらい楽しめるのかは,よくわかりません.マリーが楽しめたならエリーが楽しめることはほぼ確実なんですが…

個人的にはロロナなどの「あたらしい」アトリエシリーズを経験した方々が,マリーのような「古典」を遊んだ時にどういう感想を持つのか,ということは興味があります.

まとめ

マリーのアトリエが面白いのでやりましょう.スマホなら1200円買い切りです.PSアーカイブスなら617円です.

Poincare Embeddingの実装について

まえがき

この記事はAP Advent Calendar 2017の25日目です,メリークリスマス.私はチョコレートケーキでも買って美味しく頂こうと思います.

この記事では論文Poincaré Embeddings for Learning Hierarchical Representationsにて提案されている双曲空間上での学習アルゴリズムの実装について,特に幾何学と計算機の相性という観点から述べます.やや変わった視点なので,もう少し癖のない記事が読みたい方はこちらの解説記事をおすすめします.なお,本記事では私が新しくやったものは何一つないです.

この周辺で研究していることはあるんですが,それは論文にしていないのでまだここには書けません.すみません.宣伝みたいで恐縮なのですが,私の研究の話は後日の創造輪講で話す予定なので,興味がある人はそちらで(詳細は一番最後に書きます).

論文の大まかな紹介

1行要約

階層構造やグラフ構造を持つデータは双曲空間というリーマン多様体に埋め込むと学習が上手くいく.

もう少し解説

階層やグラフ構造を持つデータは世の中に色々あって,それらはグラフで表現することができます.自然言語における単語の間には親単語-子単語の関係があるのでグラフで表現できます(単語がノード,親子関係の有無がエッジの有無です)し,ネットワークはグラフそのものです. さて,グラフ構造をグラフ構造のまま見てあげてもよいのですが,各ノードを距離空間に埋め込んで表現することを考えます.勿論,今考えているのは背後にグラフ構造があるデータの埋め込みですから,好き勝手に埋め込んで良い訳はありません.そこで,埋め込みに次のような要請を課すことにしましょう.

  • ノード間にエッジが張られているならば距離が近く,張られていないならば距離が遠くなるように埋め込め.

この要請を充たすようにグラフを空間に埋め込むことで,次のような工学的ご利益が期待できます.

  • ネットワークグラフが与えられていて,一部のエッジの情報が欠落していたとします.そこで現時点で存在がわかっているエッジの情報をもとにしてノードたちを埋め込みます.埋め込んだ結果,リンクが張られていないにも関わらず近くなるノードの組があったとすると,そのノードの間には実は欠落していたエッジが存在するのではないか,という予測・知識発見に繋がります.
  • 自然言語処理においては親子関係があるかないかという2値の分類のみならず,単語と単語の意味の近さみたいなものも定量化できます.例えば「コーヒー」と「ドーナツ」という単語はどちらが「飲み物」という単語と近いか,みたいな問いに対して数字で解答できます(当然,「コーヒー」のほうが「ドーナツ」よりも「飲み物」に近くあってほしいわけですが).

以上のご利益は原論文に記載がありましたが,これを応用すれば例えば文章が与えられたときにそのトピックを推定するなどの問題にも精度良い解答を出せるかもしれません.このあたりのポテンシャルは未知数です.

さて,この要請を充たすためにとりあえず空間を用意しましょう.いの一番に思いつくのはユークリッド距離を入れたユークリッド空間に埋め込むことです.ノードuたちを適当な乱数を振ってバラ撒いた上で,例えば \sum_{(u,v) \in E} d(u,v) - \sum_{(u,v) \notin E} d(u,v) みたいな損失函数を定めて最小化すればこの目的が達成できそうな気がするでしょう.1

しかしながら,たとえば1次元とか2次元のユークリッド空間に撒くノードの数を増やしていくと,それぞれのノードの間の制約はどんどん増えていきますから,そのうち限界が来て上手く行かなそうな気がします.実際にこの予想は正しく,ユークリッド距離を用いてこの埋め込みを実行すると,埋め込み先の空間の次元を充分大きく取らないと実用上は満足行く性能が出ないことが実験的にわかっています.

そこで現れるのが「双曲空間」と呼ばれるリーマン多様体です.この双曲空間はグラフ・木を埋め込むには大変相性の良い距離函数を備えていて,ユークリッド空間に埋め込むと100次元くらい必要な表現能力を5次元とかそこらで実現してしまいます.このあたりの話は原論文も詳しいですし,既にある解説記事がとても丁寧で参考になります.

双曲空間

ユークリッド空間や球面と並んでリーマン幾何では重要な図形(多様体)です.ここでは,

  • 上掲した論文が読める程度の最低限の説明
  • もうすこしちゃんとした説明

をします.

必要最低限の事項

多様体とか言われるとむずかしくてよくわかりませんが,事実として次のことを知っていれば論文は読めるし再現実験ももう少し勉強すれば多分できます.

  • n次元双曲空間\mathbb{H}^n」とは,集合としてはn次元ユークリッド空間内の単位球D^n := \{ x \in \mathbb{R}^n\ |\  \|x\| \leq 1 \}
  • 2点 u,v \in \mathbb{H}^n間の距離は d_{\mathbb{H}^n}(u,v) = {\rm arcosh} \Big(1+ \frac{\|u-v\|^2}{(1-\|u\|^2)(1-\|v\|^2)}\Big)
  • 原点中心の半径 0 \lt r \lt 1の円の弧の長さは 2 \pi \sinh r.これは rに関して指数的に大きくなること,即ち原点から離れるに従って指数的に空間が広がっていくことが重要.
  • 例えば二分木を考えると,これは木の深さ nが増えるに従って総ノード数は指数オーダ O(2^n)で増える.この指数で増えるノードたちを上手く扱うために,ユークリッド空間では次元を大きく上げることで対応したが,双曲空間は原点から離れるだけで勝手に空間が広がってくれるので都合がいい.

さて,計算機との相性についても少し述べておきましょう.

  • 距離函数はそんなに面倒な形をしてなくて, u,vの数値を与えれば(一番重たいのが内積の計算なので)高々 O(n)で計算機に計算させることができる.実時間的にもC++のstdなら多分早いし,GPUを使えば多分もっと早い.
  • 距離函数をその引数で微分して得られる導函数( \frac{\partial d}{\partial u}とか)も頑張れば解析解を計算できて, u,vの数値を与えれば O(n)で計算機に計算させることができる.
  • 計量テンソルの行列表示と呼ばれるものがスカラー行列になっていて,これの逆行列計算は単独で行ったとしても高々 O(n)でできる.ここで何言ってんのかわからない人はスルーしてください.ただ,少なくとも私にとってこの事実はマイム・マイムを踊って喜びたくなるくらい嬉しいことなのだということだけ覚えていて下さい.

とにかく色々なものが解析的に計算できるので計算機に載せて頑張ろうという気になれるのが何よりも重要です.

もうすこしちゃんとした説明

この節ではリーマン幾何の初歩を既知として,双曲空間について知られている事実をもう少しちゃんと列挙し,更に「自然勾配法」と呼ばれているアルゴリズムの実装可能性について言及しておきます.

  • 双曲空間は等長同型だが見た目が異なるモデルが複数存在する.1つのモデルの作り方は次の通り: \mathbb{R}^{n+1}に通常の位相を入れ,更に2次形式 Q(x)=(x^1)^2+ \cdots + (x^{n})^2 - (x^{n+1})^2から誘導される標準ローレンツ計量を入れたミンコフスキ空間\mathbb{M}^{n+1}を考える. Q(x)=-1で指定される超曲面Sを考えると,Sへの標準ローレンツ計量の制限は正定値になる.このリーマン計量を備えた超曲面Sを双曲空間の放物面モデルと呼ぶ.
  • この放物線のある点xから点(0,0,\cdots,0,-1)へ直線を引くと,この直線はD^n := \{ x \in \mathbb{M}^{n+1}\ | \ \|x\| \lt 1, x^{n+1} = 0 \}とただ1点で交わる.このような仕方でSからD^nへの全単射\varphiが作れるから,これを用いてD^nをリーマン多様体と見做す(ちゃんと言うなら逆写像\varphi^{-1}で位相と計量を引き戻している).このD^nを双曲空間の共形円板モデルと呼ぶ.
  • その他にも等長同型なモデルはたくさんあります.ベルトラミ・クラインモデルとか上半平面モデルとか.
  • 共形円板モデルのリーマン計量g_\mathbb{H}は上掲した仕方で構成されるが,その構成をきちんと追いかければg_\mathbb{H} = \Big(\frac{2}{1-\|x\|^2}\Big)^2g_\mathbb{R}となることがわかる.但しg_\mathbb{R}ユークリッド空間のユークリッド計量.特にこのことから双曲計量の行列表示がスカラー行列になることがわかる.
  • 従ってある点 u \in \mathbb{H}^nおよびその点における接ベクトル V \in T_u\mathbb{H}^nが与えられた時,勝手な函数f \colon \mathbb{H}^n \to \mathbb{R}の勾配ベクトル場{\rm grad }\ fが高々線形時間で計算できる.
自然勾配法との関係

勾配ベクトル場が計算できると自然勾配法が使えて嬉しいという話ですが,その前に手短に自然勾配法を復習しましょう.

  • リーマン多様体(M,g)に対して,函数f \colon M \to \mathbb{R}の勾配ベクトル場{\rm grad }\ fとは任意のu \in MおよびV \in T_uMに対してg({\rm grad }\ f,V) = Vfを充たすような唯一のベクトル場のことを言った.但し右辺は Vによる f微分
  • 局所座標(x^1,\cdots,x^n)を取って計算すると, {\rm grad}\ fの第i座標はg^{ij}\frac{\partial f}{\partial x^j}となることがわかる.但しg^{ij}はこの局所座標に関するgの行列表示の逆行列(i,j)成分.
  • このベクトル場の積分曲線をグラディエント・フローと呼ぶ.グラディエント・フローに沿って移動すると函数値は上昇する.
  • 多様体上の函数fが与えられた時,適当なステップ幅\etaを取って,u \leftarrow u - \eta {\rm grad}\ fなる更新を繰り返すことでfの最適化を試みる手法のことを自然勾配法と呼ぶ.

つまり,fのグラディエント・フローを1次近似しようというのが自然勾配法の戦略です.もっと言えば,座標ごとの微分を並べたもの\Big(\frac{\partial f}{\partial x^i}\Big)fの外微分の成分表示なので座標変換に対する共変性を持ちますが,座標函数は座標変換に対して反変に振る舞うので型が合いません.そこで計量を用いて\Big(\frac{\partial f}{\partial x^i}\Big)の添字を上げ,型をキャストしてあげることでちゃんと足し算をしている雰囲気を出しています.これは実験的に良い性能を出すことが知られていますし,勾配法の収束の証明を真似れば適切な仮定のもとで局所収束も言えると思います…多分.2

ところで,このアルゴリズムの実行には各ステップで計量行列の逆行列計算が必要になります.従って時間計算量はステップごとにO(n^3)です.やや口が悪くなりますが,これは余程特別な場合を除いて使い物にならないと言い切って良いです.しかし今回は計量行列がスカラー行列なので,逆行列の計算にO(n^3)も要りません.余程特別な場合に相当するわけです.そりゃヒャッハーの1つくらいしたくなります.

アルゴリズムの設計

細かいチューニングはともかく,今までの話を踏まえれば次のような手続きを踏んでいけば良いことがわかります.

  • 損失函数を予め設計しておく.損失函数はノード間の距離に依存し,上に挙げた要請を反映しているとする.
  • 単位球の内部にノードを適当にばらまく.
  • 損失函数を自然勾配法で最適化する.双曲空間においては自然勾配法は実行できる.

おまけ:私の研究の話

今回の記事は事実を淡々と述べていく仕方で済ませましたが,いま現在この論文の内容に手を加えて色々やっているところです.その内容について,12月26日の創造輪講で話す予定です.

あとで気づいたのですが,創造輪講は原則非公開でした.なので興味ある人は直接聞きに来て下さい.


  1. 実際にこの損失函数を使うわけではないです.損失函数は実際の問題に応じて慎重な設計をする必要があります.ここでは適用する問題の詳細に立ち入らずに大まかな解説をしたいのでこのようなtoy modelを挙げたに過ぎません.

  2. 多分,と言っているのは私が証明を読んだことがないからです. S.Amari “Information Geometry and Its Applications” には理論的なことが主張されていましたが,私自身の手で証明をverifyできていません.

インターン行って内定を頂いた話

すみません.日記をつけると決めたのに数ヶ月放置していました.たまにいろいろな人から「このゲームをやって早く感想を書け」とか言われるので,これからはたまに書きたくなったときに書こうと思います.

夏休みに某所にインターンに行ったので,備忘を兼ねてその話を書きます.場所を伏せているのは何となくです*1

正直な話として,当初インターンというものにはあまり行きたくありませんでした.理由を挙げていけばだいたい次のとおりです.

  • 数学してる方が楽しいという自信がある.
  • 研究したい.院生だし.
  • 朝起きたくない.
  • なんだか大変そう.

就活も,上のような理由で終始乗り気ではありませんでした.強いて上にない理由を挙げていくなら,

  • 事情が許すなら博士課程に行きたい.
  • 会社に媚を売りたくない.面接で美辞麗句を並べるのも嫌*2
  • 数学を嫌っている人間と机を並べて仕事をしたくない.
  • なんだか大変そう.

といったところです.

そうは言っても,これを真正面から通そうとしたら行き先は博士課程一択です.ですが博士課程で生き残れる絶対の自信を持てるほど私の精神は頑丈ではありません.もっと一般論として,こんな我儘が通るんだったら人生もう少しちょろいはずです.

少し重い腰を上げて,就活イベントに参加し,インターンに行きました.そこで若干の心変わりをして,かなり早めの内定をいただくところまで行きました.全部を書くと長いので,上に挙げたような「就活」とか「インターン」とかに対する精神的障壁のようなものに関連するところを書きます.

就活イベントについて
  • 存在を知ったのは研究室の先輩経由.行こうと思った直接の理由はタダ飯期待値が1食分を越えていることが明らかだったから.
  • イベントでは各企業に対して,数学が好きで,プログラミングと機械学習が好きじゃない旨をはっきり伝えた.これは結果として合わない会社さんを早い段階で特定できたので良かった.
  • 数学好きならぜひ来てくれ,と熱烈に言ってくれた会社さんが1社だけあったので,その会社さんのインターン参加のプロセスに進んだ.その会社さんには博士中退の人や応用数学の博士持ちの人がいると聞いたので,博士に行く場合の人生のお手本を見たいという気持ちでちょっと様子を見てみることにした.
インターンについて
  • インターン参加のための選考があったが,中身はよく覚えていない.気づいたらインターンに行くことになっていた.期間は2週間.
  • インターンの課題はかなりぼんやりとしたものが与えられた.手の付け所が分からない程度にぼんやりしていた.当初想定していたような,これをやれ,あれをやれという感じではなかった.自分で考えて頑張ってね,的な感じだった.なので最初方向性を決めるまでだいぶ苦労した.
  • データがあって,それに対して仮説を立てて,その仮説を検証するというプロセスを踏むことになったが,これは研究のサイクルと酷似していることに気づいた.博士に行かずに一旦就職するのも悪くないかと思った理由.
  • 数学っぽいことはまったくやらなかった.強いて言えば古典論理に基づく推論をした.後から振り返ると,評価された点はこの推論をきちんとやったことくらいな気がする*3
  • 特に午前中などの眠いときはよく机を離れて気分転換にオフィス内をランダムウォークしていた.お昼から調子が出るのがいつものことだった.
  • 残業はほとんどしなかった.そもそも残業は全く推奨されていなかったので,社員さんより早く帰ることもよくあった.
  • 進捗管理はほとんどされなかった.社員さんも「進捗管理はしたくない.議論の相手になりたいので,何か見せるなら議論可能なフォーマットにして」と言っていた.最初何を言っているのかよくわからなかったが,要するにゼミのレジュメ切ったり論文書くのと同じ要領で相手に伝わるように見せれば良いのだとわかってから捗った.
  • インターンの働きは最終的には高く評価して頂けたようだった.ありがとうございます.
選考について
  • プログラミングの課題をやって,その後ちょっと口頭試問を受けた.普段勉強していないアルゴリズムの基本事項を聞かれて,結果はボロボロだった.
  • 仕事上はアルゴリズムの話もやることになるわけだけどそれもちゃんとわかってほしいという意図があるらしかった.色々話をして,まあ私なりの(つらくなさそうな)働き方のイメージが掴めたのと,「100%自分のやりたいことだけやれるとは限らないよ」ということを会社さん側から明示してくれたのは個人的には高評価だった.自分のやりたいことだけやれるとは限らないのは研究職でも多分同じだろう.
  • これを機会にちゃんとアルゴリズム機械学習の各種手法について日頃から勉強しようと心に決めた.今日もアルゴリズムデザインを読んでいた.
  • 他にも面接を何回か受けた.自分の長所や短所を聞かれる事もあったが,素直に答えた*4.一切話を盛っていないのかと言われると何とも言えないが,嘘は言ってないはず.
  • 結果としては内定を頂いた.ありがとうございます.
その他印象に残ったエピソード
  • 雑談で趣味を聞かれたときは「勉強」と答えた.時間があればデレステするか勉強するかどちらかであるから,嘘は言ってない.
  • ある社員さんが,「学生と違って社会に出ると厳しいとかいう巷の主張は意味がわからない,そういうことを言うやつは余程ぬるい学生生活を送ってきたのだと解釈してニコニコしている」と言っていたのを覚えている.ニコニコで済ませるあたりに高い社会性を感じたので見習いたい.
  • その社員さんであるが,「学生の頃から成果を出すことには拘ってきたし,社会人になってもそれは変わらない.ずっと学生気分で仕事をしている」とも言っていた.もし博士に進むにしても会社で働くにしても,どちらかを選ぶことが自分のスタイルに本質的な選択・変更を迫られるようではダメだという学びになった.
全体を通して

上にも簡単に書きましたが,結局私が出会ったその会社さんで働くのも,研究職としてやっていくのもまあボチボチ同じようなものだと思ったのが就活をする心変わりをした理由だと思います.

そうは言っても勉強や研究をしている時間は幸せな時間です.博士号への憧れは強いし,修士を出てすぐに民間で働くことにしたとしても,どこかで博士号を取って自分なりに何かしら研究成果と呼ぶに相応しいものを残してやりたいと思っています.但し,具体的にどのようなルートを設計するかはまだ決めていませんが,一度会社で働くことで得られるものはとみに多いはずという確信があるので,今のところ直接進学の可能性は低いです*5

他人に「就活はこんな感じでやると良いよ」とかおすすめするのは気が引ける例を構成してしまいましたが,この手のものは肩の力を抜いて適当にやるくらいが,存外幸せなのかもしれません.

*1:というか,インターン中取り交わした守秘義務の課せられている範囲を私が忘れてしまったので,かなりぼんやりした記事になってます.すみません.

*2:子供じみた意地を張っている側面は否定しないしできないが,何より私の性格からして,媚を売って入ってもお互い不幸せになるだけだと思ってのこと.

*3:古典論理に基づく推論ができることそのものに正の市場価値が伴うのではないかという仮説を今のところ持っているが,確信には至っていない.個人的には棄却したい仮説であるーなぜなら,多少数学を真面目に勉強した人間ならば絶対にできるはずの能力だから.

*4:工学部だけど数学はちゃんとやることに自負を持っている,とか,あまりにちゃんとやりすぎるので周りの人々からよく煙たがられる,とか.読んで印象に残った本を挙げてと言われたときは斎藤毅「線形代数の世界」を挙げた.

*5:どうなるかなんて自分でもわかりませんが.「将来どうするの/何になるの」という質問は(個人的な経験も手伝って)かなり苦手で,訊かれるたびにGUNSLINGER GIRLのアレッサンドロの言葉を思い出します―3年後の自分の生死だってわかりゃしない,と.