PFIインターン2015 参加報告
8/3-9/30の期間、Preferred Infrastructure (PFI)のインターン（PFNと合同）に参加しました。 参加報告のために、凍結していたこのブログを解凍します。
応募から選考まで
PFIという会社については、学部の頃から存在は知っていました。 周りでインターンに応募する人もいたりして、夏にインターンをやっていることも、おぼろげながら感じ取っていました。 ただ、当時の僕は、専門的能力もなかったので、自分には関係ない世界かな、とも思っていました。
その後、留学したり大学院を変えたり紆余曲折あって、自然言語処理（NLP）の研究をすることにしました。 PFIの話もよく耳にするようになり、何だか先進的で面白いことをやっている会社だなと思っていました。 そのような面白い会社で、実際にどんなことをしているのか、是非見てみたいと思いました。 それから、僕は、頑張らなくても大丈夫な環境にいると、だらけてしまう性質があります。 自ら環境を積極的に変えていかなければならないことは、それまでの経験から身にしみて感じていたので、 この機会にインターンに挑戦し、自分を奮い立たせようと思いました。
応募後は、書類選考の後に、Skype面接がありました。 面接では、自己紹介をしたり、事前に提出した課題に関して質問を受けたりしました。 自分の考えが浅かったり、喋りが苦手なところもあって、これはダメだと思ったのですが、 なんとか拾っていただいたようです。
テーマ決め
インターンが始まる前に、テーマの大枠を決めるためにSkypeでミーティングがありました。
唐突ですが、僕がNLPの研究をしようと思ったのは、アニメキャラを具現化したいからです。 アニメキャラの具現化のためには、視覚や音声など様々な要素がありますが、 中でも、対話できることが最も重要な要素だと思っています。 そのような目標があることはメンターの方々にも、折にふれて伝えていました。
そして、ここにきて、Recurrent Neural Network (RNN)を使って文生成ができるという話が盛り上がっています。 RNNを使って、画像のキャプションを生成したり、対話文が生成できるというのが、最近のホットな話題です。 RNNが生成する文が、これまでの生成手法による文に比べて優れているかと言われれば、様々な意見があると思います。 ですが、RNNは非常に簡単に実装できるのでアイディアをすぐに試せること、 ベクトルの演算により組み込みたい情報を簡単に組み込めるということは、確かな利点ではないかと思います。 そこで、キャラとの対話を念頭において、RNNによる文生成に関して何かするという方向性になりました。
インターン開始後
文生成がテーマだということで、最初の2週間ほどは、適当に文を生成して遊んでいました。 遠い昔のことなのでよく覚えていませんが、キャラに何かを喋らせたり、キャラを合成したり（？）していた気がします。
文を生成して遊べるようなツールはすぐに作れました。これは、ひとえにChainerの力であると言えます。 僕はそれまでTheanoを主に使っていましたが、RNNのコードを書くことに関して言えば、Chainerが圧倒的に開発効率が高かったです。 Chainerがなければ、僕のインターンは、また違ったものになっていたでしょう。
文生成だと漠然としているので、最終発表に向けて、一つはっきりしたテーマを決めることになりました。 キャラとの対話では、口調などのキャラ付けが、重要な要素のひとつです。 特にアニメキャラなどでは、他との差別化のために、言葉遣いがかなり特徴的だったりします。 そこで、そのような言葉遣いによるキャラ付けを自動的に学習することがテーマになりました。 手法としては、Variational Autoencoder (VAE)を使うことにしました。 VAEは色々なことに使える手法ですが、例えば、手書き数字画像のアナロジー生成ができることが知られています。 今回のテーマも、同じアイディアに基づくものでした。 僕が知る限り、VAEをNLPに適用した例を見たことがありません。 なので、どのような結果になるか、自分自身とても興味深いテーマでした。
試行錯誤の連続
他のインターン生の方に教えていただいたりしたおかげで、実装はわりと早く終わりました。 しかし、深層学習の辛いところは、コードを書いて終わりではなく、上手く行くパラメータを見つけなければならないことです。 パラメータによってすごく良い結果が出たり、逆に全然だめだったりします。 どうすれば良いパラメータを見つけられるのか誰も知らないけれど、かといってノウハウが全く無いわけではなく、魔術的だとよく言われます。 1つのパラメータを試すのにかかる時間が長く、パラメータを全通り試して明確な結論を導くことができないので、研究テーマ的には苦しいところです。
今回、色々なパラメータを試したのですが、最終発表の10日前になっても、全然見せられるような結果が出ていませんでした。 今度こそと思ってもやっぱり上手くいかず、精神的にはかなりつらい日々が続きました。 ドキュメンタリー番組でよくある、ハッピーエンドに向けた逆境の時期なのだと、自分に言い聞かせていました。 このままだと、最終発表で土下座することになると思っていたのですが（もちろんメンターの方々は優しくしてくれました）、ある日偶然、上手く行く方法を発見しました。 確かに、言われてみれば上手く行きそうな方法なのですが、見つけられたのは、ただラッキーだったと思います。 とにかく、発表までに、最低限何か動くものができたかなという感じになりました。 ただ、上手く行っているのは非常に限定的な状況なので、まだまだ解決すべき問題が山積しています。
最終発表は、スライドが抜けてしまったり、説明がグダグダになってしまったところもありましたが、 なんとか期日までに成果をまとめることができて良かったです。 後日、コードなどを公開できればと思います。
インターンで得たもの
インターンを通じて、企業で働くということがどういうことか、少し想像ができるようになったと思います。 エンジニアの仕事を間近でみるのは、今回が初めての機会でした。 エンジニアといえば、製品のコードを書いたり、アイディアを実験したりする仕事だというイメージがあります。 ですが、顧客とのコミュニケーション能力やビジネス的な感覚なども必要で、純粋に技術的なことは一部にすぎないのだと感じました。 技術的なこと以外にも、もっと幅広く様々なことを知らねばという思いが強くなりました。
また、学生生活を進める上での考え方が大きく変わりました。 生活が研究室で閉じていると、論文を書いて採択されることが無条件で尊いことだという考え方になってきます。 ですが、インターンで色々なものを見て、研究をして論文という形で成果を出していくのは、数ある生き方の一つに過ぎないのだと思いました（当たり前ですが）。 あえて研究をするという選択をする以上、論文を書くこと自体が生活の目的になっていないか、 本当に自分がやりたい研究テーマに取り組んでいるか、強く意識するようになったと思います。
最後に、アニメキャラと対話できるようにするのが僕の夢であると述べましたが、 漠然と思っていただけで、正直なところ、自分の手では実現できないだろうと思っていました。 ですが、今回のインターンでは、関係するテーマに、2ヶ月間真剣に取り組ませもらえました。 この機会に、夢の実現に向けて、もう少し真剣に考えてもよいのではないかと思うようになりました。 これが個人的には一番の収穫でした。
おわりに
今回のインターンは、技術的に成長できたことはもちろん、自分の考え方が大きく変わる機会だったと思います。 それから、本郷の周辺で毎日美味しいものを食べられたのが最高に幸せでした。 今いるNAISTでは、お店選びに迷うような贅沢ができず、本当に困っています。 Red Bullも毎日飲ませていただきました。冷蔵庫に補給してくださった方々、どうもありがとうございました。 PFI/PFN関係者の方々、他のインターン生の皆さん、2ヶ月間大変お世話になりました。 とても有意義な体験をさせていただき、ありがとうございました。
ロシア語メモ
位置の表現
| на столе́(前置格) | on the table |
| в стака́не(前置格) | in the glass |
| под столо́м(造格) | under the table |
| пе́ред столо́м(造格) | in front of the table |
| за столо́м(造格) | behind the table |
| к(与格) | hin |
| от(生格) | her |
| ря́дом с тобо́й(造格) | close to you |
| к тебе́ | to you |
| ко мне | to me |
| со столо́м(造格) | with the table |
| по улице(与格) | along the street |
位置を表す前置詞は、動作を表す時、対格とともに用いられる。
発音の注意
ロシア語のт,дの発音は、英語のt,dの発音とかなり異なる。
ロシア語のт,дでは、舌を上下の歯につけて発音するため、息があまり漏れない。
例文
| На столе стоит стакан. | There is a glass on the table. |
単語
| стоя́ть(impf.) | to stand |
| ста́вить/поста́вить | to put, place |
| лечь(pf.) | to lie down |
| лежа́ть(impf.) | to lie |
| класть/положи́ть | to put down |
| находи́ться | sich befinden |
橋（bridge）検出アルゴリズム
連結グラフにおいて橋（bridge）とは、それを取り除くと連結でなくなってしまうような辺のこと。閉路に含まれない辺が橋になる。
橋はDFSを行うことで検出することができる。DFSは、アルゴリズムの一部としてグラフの構造を調べる時によく使われる。
アルゴリズム
まず、頂点を１つ選び、DFSを開始する。
各頂点には、pre、lowという２つのデータを記録する。
preは、DFS木の行きがけ順（pre-order）の値を保持する。
lowは、DFS木でその頂点から到達しうる頂点のpreの最小値を保持する。初期値はその頂点のpreである。
次の頂点が、すでに訪れてある（preの値が存在する）場合は、自分のlowを、次の頂点のlowと比べて小さい方に更新する。
次の頂点をまだ訪れていない場合は、その頂点に対してDFSを続ける。そして、その頂点へのDFSが終了した際に、lowがpreより小さくなっていれば、その頂点へ向かう辺は橋である。
例えば、次のような無向グラフがあるとする。
左端の頂点からDFSを始める。行きがけ順でpreの値を設定していく。
preの値を円内に、lowの値を右下に表示している。
以降、pre=Xの頂点を、頂点Xと呼ぶ。
頂点2へのDFSが終了した。このときlow=pre=2となっている。つまり、頂点2より先はそこで完結しているということがわかる。したがって、頂点1->頂点2の辺を橋とする。
別の頂点へDFSを続ける。
頂点3は既に訪れており、lowの値は当然小さい。頂点6のlowを3に更新する。
頂点7はlow=pre=7なので、頂点6->頂点7の辺は橋である。
頂点6はlow=3<pre=6なので、頂点6->頂点7の辺は橋ではない。
DFSが終了する度に、親ノードのlowを更新していく。
頂点4のlowの値が再び更新された。
low=pre=1より頂点1の先で完結していることがわかるので、頂点0->頂点1を橋とする。
注意点として、親ノードが次の頂点である場合には特別な対処が必要だ。
無向グラフでは必ず双方向に辺が張っている。例えば、A->Bという辺があった場合、B->Aという辺も必ず存在する。しかし、これは閉路ではないので、無視しなければならない。
上の図では親ノードへの走査を省略している。
サンプルコード
typedef vector<int> VI; typedef vector<VI> VVI; typedef pair<int, int> PI; // res: bridges // v: current node // from: parent node int dfs(VVI& g, vector<PI>& res, int v, int& count, int from, VI& low, VI& pre) { pre[v] = count++; low[v] = pre[v]; for (VI::iterator it = g[v].begin(); it != g[v].end(); it++) { int to = *it; if (pre[to] == -1) { // destination has not been visited // visit destination and update low[v] low[v] = min(low[v], dfs(g, res, to, count, v, low, pre)); if (low[to] == pre[to]) { // edge is not contained in a closed path -> bridge res.push_back(make_pair(v, to)); } } else { if (from == to) { // ignore a path to parent continue; } low[v] = min(low[v], low[to]); } } return low[v]; } // Calculate bridges in a undirected graph. // Assume graph is connected and has no parallel edges or self-loops. // g: adjacency list // V: number of nodes vector<PI> bridges(VVI& g, int V) { vector<PI> res; if (V > 0) { // assume at least the first vertex exists VI low(V, -1); // lowest reacheable index VI pre(V, -1); // pre-order index int count = 0; // pre-order index counter dfs(g, res, 0, count, -1, low, pre); // start dfs from vertex 0 } return res; }
参考
- http://stackoverflow.com/questions/11218746/bridges-in-a-connected-graph
- Introduction to Algorithms, 3rd, Problem 22-2
スペイン語メモ
例文
| Me interesan los idiomas. | I'm interested in foreign languages. |
| Estoy aprendiendo alemán. | I'm learning German. |
| ¿Puedes repetir lo? | Could you repeat it? |
| Quisiera aprender ruso. | I would like to learn Russian. |
| ¿Que idiomas ya has aprendido? | What languages have you already learned? |
| Ya se me olvidó todo. | I've already forgot everything. |
| Los kanji que he aprendido en Japon ya se me olvidaron. | I forgot the kanji I've learned in Japan. |
| ¿Cuantas letras hay en el Sánscrito? | How many letters are there in Sanskrit? |
| ¿Cuanto tiempo aprendiste chino? | How long did you learn Chinese? |
ロシア語メモ
今日勉強したことのメモです。
完了体と不完了体
ロシア語には完了体と不完了体の対立がある。これらの使い分けがロシア語を学ぶ上で難関のひとつである。
動詞を覚える際は、不完了体、完了体のどちらかを常に意識しなければならない。
| 不完了体動詞 | 完了体動詞 | 意味 |
| де́лать | сде́лать | to do |
| брать | взять | to take |
| писа́ть | написа́ть | to write |
| бежа́ть | побежа́ть | to run |
不完了体動詞に接頭辞がついて、完了体動詞ができることが多い。
不完了体では、動作自体（process）に関心がある。一方、完了体では、動作の結果（result）に関心がある。
例えば、以下のような例文に区別が見られる。
Я не хочу писать.
私は書きたくない。
（書くという動作自体をしたくない）
Я хочу написать письмо.
私は手紙を書きたい。
（書いた結果の手紙に関心がある）
Напиши!は、何か特定の事柄（名前など）を書かせたいときに用いる。（書かれた結果に関心がある）
Пиши!は、例えば、だらしない生徒が書くのを嫌がっている時に、先生が書くことを命令する時などに用いる。（書くこと自体に関心がある）
例文
| Ты хочешь есть? | Do you want to eat? |
| Что ты делаешь? | What are you doing? |
| Что ты сделаешь? | What will you do? |
| Сколько сейчас вре́мени(genitive of время)? | What time is it? |
| Который(which) сейчас час? | What time is it? (more polite) |
| Пора домой. | Time to go home. |
| Это смешно. | It's funny. |
単語
| ве́чер | evening |
| у́тро | morning |
| смех | laughter |
| смея́ться | to laugh |
Codeforces Round #206 (Div. 2)
Codeforcesに初参加したので感想を書きます。最初の２問しかできませんでした。
A
難易度の基準がわからなかったので、定義を見てかなりビビった。でも、他の人達が即答しているのを見て、見掛け倒し問題なのだとわかった。
B
簡単な場合分け。
最高でもc4を払えば十分。busに払う額をmax_bus、trolleyに払う額をmax_trolleyとして、max_bus+max_trolleyとc4の少ない方を払う。
max_busは、最高でもc3。これと一枚ずつ払う場合と比較すればよい。
max_trolleyも同様。
C
ぱっと見では、左から取った回数、右から取った回数で2次元DP（最後に取った方によって2枚用意）をすれば良いと思うが、1<=N<=10^5なので、それだと間に合わなくなる。
なぜか、配列を再利用して空間計算量を削減すれば大丈夫だと思い、そのまま実装してしまった。
結局、N=10^5のテストケースをもらってHacked。
正解を見たら、全然DPじゃなかった。
まず、左から取った総数Lを決める。すると、右から取った総数R=N-Lが決まる。
L<Rのとき、R回のうちR-L回は、必ず右から連続して取ることになる。
ここで、取る順番によって結果が変わるのに、それを考慮していないことが気になるが、最小コストさえ求めればよいことに注目。
つまり、左から連続して取る場合や、左から取り始める場合は考えなくて良い。
最善手は、右から取り始め、左右交互に取っていく方法であり、この時のコストは簡単に求まる。
あとは、Lを0からNまで動かして最小値を求めればよい。
左から取った総数Lを決めるとかなりのことが決定される（左のL個は全て左から、右のN-L個は全て右から取ることになるし、連続で取る回数も分かる）のだが、そこが意識できていなかった。
最善手を考えることによって探索空間を削減するのは良くあるパターン。
あと、10^5を10000と間違えるというミスもしていた。今後は気をつけよう。
D
誰も解いていなかったのでパス。
E
1<=n<=3*10^5、1<=a<=10^5なので、brute forceではもちろん間に合わない。
求めるgcdをa[0]~a[n-1]の最小値から初め、少しずつgcdの値を小さくして試していく。
a[0]~a[n-1]を昇順にソートして、小さい順番に試し、制約を満たさない場合はgcdを1減らすという方法でやってみた。
ここで、残り時間が少なかったので、「a[n]まで既に制約を満たしている場合は、gcdを1減らしてもa[n]までは制約を満たしている」という謎の仮定を置いた。
他の人の解答を見ても、このように考えた人が多かったようだ。
結局TLEになってしまったわけだが、多くのテストケースを通っているので、もしかするとこの仮定は正しかったのだろうか？
ポイントは、gcdを効率よく減らしていくことにあったようだ。
あるa[i]に対して、a[i]%gcd>kだったとする。（つまり制約を満たさない）
ここでa[i]の中にはa[i]/gcd個のgcdが入っている。
ここからgcdを減らしていくわけだが、どこまで減らせるだろうか？
仮にgcdを1減らすとする。gcdが十分大きい場合、a[i]%(gcd-1)=a[i]%gcd+a[i]/gcdであり、a[i]%(gcd-1)>k、つまり制約を満たさないことは瞬時に分かる。
検討に値するのは、a[i]に入るgcdの個数が増えるときである。
結局、gcdはa[i]/(a[i]/gcd+1)まで一手で減らすことができる。
群論入門 ３章 準同型・同型
第３章「準同型・同型」
