ディープラーニング分散学習ハッカソン参加報告
経緯
研究室のお金でディープラーニング分散学習ハッカソンに参加してきました．
東京大学情報基盤センターが主催する、マルチGPUを使った学習のハンズオン。申し込みは締め切られているが、資料が公開されており分散学習の仕組みと課題、そしてChainerMN/TensorFlowで実際に分散学習を行う方法までが解説されている。 https://t.co/ISU1CZIr2b
— piqcy (@icoxfog417) 2019年1月24日
想定する読者
- 深層学習してる人
- 分散深層学習をやってみようと思っている人
イベントの概要
要旨：参加者が持ち寄った深層学習のコードを強いメンターたちに助けられながら分散深層学習のコードに書き換えていく．
共催：
期間：2019/01/24--2019/01/25 の 2 日間
場所：東京大学情報基盤センター
計算機：情報基盤センターの Reedbush-H
フレームワーク：Chainer か Tensorflow
プログラム：
- 主催側からのプレゼン（各組織 20 分ずつ）
- 参加者自己紹介
- 各自作業
- 成果報告
分散深層学習基礎講座
Nvidia さまから 分散学習基礎講座 というタイトルのプレゼンがあったので，その内容を私なりにまとめる．詳細は元スライドを参照のこと．
分散深層学習とは
深層学習を，複数の GPU を使って行うこと．データ並列/モデル並列 や 同期更新/非同期更新，パラメータサーバ方式/P2P方式 などの分類がある．
データ並列とモデル並列
データ並列
モデルをコピーして，パラメータを共有した状態でそれぞれ別のサンプルで訓練する並列化方法．GPU ごとに別々のデータで勾配を計算させるので，モデル更新時にはうまいことパラメータを一致させる必要がある．
同期更新と非同期更新
パラメータの更新方式は同期更新と非同期更新に分けられる．
| 同期更新 | 全 GPU の勾配計算完了を待ってモデルを更新する．GPU 性能に差がある場合無駄が出る． |
|---|---|
| 非同期更新 | 一部の GPU の勾配計算が終わったらモデルを更新する．後述の Staleness 問題が発生する． |
パラメータサーバ方式と P2P 方式
GPU 間の通信にはパラメータサーバ方式と P2P 方式がある．
| パラメータサーバ方式 | パラメータサーバのパラメータを，各 GPU がそれぞれ更新していく． |
|---|---|
| P2P 方式 | ある GPU での更新を他の GPU に伝播させる． |
モデル並列
一つのモデルを複数の GPU に置く．一つの GPU にはモデルの一部が乗っている状態．各レイヤを GPU に割り当てたり，一つのレイヤを複数の GPU に割り当てたり，いろんな切り方がある．どのような切り方がいいかはモデル依存．
各方式の弱点
データ並列：大規模化に伴う精度低下
一回の重みの更新の時に関わるサンプル数が [バッチサイズ] × [並列数] になるため，並列化しすぎると精度が低下する．
どこまで並列化できるかや，たくさん並列化しても精度を落とさないようにする研究が行われている．
- 「8k 並列までなら精度落ちない」by 顔本
- 「32k まではいける」by PFN
ちなみに SGD 的な最適化を行う場合，学習率を下げることとバッチサイズを大きくすることは等価 であるため，学習が進むにつれて学習率を下げる代わりに並列数を大きくするのもアリかもしれない．簡単には実装できなさそうだけれど．
同期更新：GPU の性能差で無駄が発生
パラメータの更新時に全ての GPU での勾配計算が完了するのを待つため，GPU に大きな性能差がある場合に無駄な時間が発生する．
非同期更新：Staleness 問題
非同期更新では，勾配の計算中に他の GPU がパラメータを更新するので，勾配計算に使っていたパラメータが相対的に古くなってしまう．これを Staleness 問題という．Staleness 問題は収束性の悪化の原因となるらしい．
モデル並列：通信コスト
フォワードプロセスでも GPU 間で通信が必要なので，データ並列に比べ通信コストが高い．
私たちがやったこと
弊研究室 からは K 先輩と私の 2 人で参加した．私たちは Chainer を使った seq2seq 機械翻訳モデルのコードに対して ChainerMN でデータ並列の分散化を施した．
資料 の通りに秒速 MN 化を行ったところ，悲しいことにバグが大量発生したので Chainer の中の人に助けられながらその解消を行っていった．なんとか時間ギリギリでエラーの出ない状態になり，並列化でどれくらい速くなったか測ろうとしたところ時間切れとなってしまった．ログを見る限り並列化しないほうが速かったので，多分まだどこかにバグがあるんだと思う．悲しい．
バグ取りを通して得られた知見
重複するエラーメッセージ数
並列数とエラーメッセージの重複数が同じ場合は GPU ID に関係のないところで出ているエラー，異なる場合は GPU ID によってエラーが出る場合と出ない場合があるエラー．私たちの場合は GPU に ID を割り振る操作をコードの中で複数回呼んでしまっていたことで起きていた．
単一 GPU でも同じエラーが出るかどうか
同じコードでも単一 GPU に設定した場合は動く場合，GPU 間の通信時に起きているエラーの可能性が高い．単一 GPU だと通信が行われないのでエラーが発生しない．
GPU に載せるテンソルは to_gpu とかの後に作る
ChainerMN ではデバイスをセットする操作の前後の行列を混ぜると死ぬ．
参加しての感想
ChainerMN 開発者をメンターに据えて ChainerMN を使ってみるという贅沢な時間でした．開発者ならではのお話が聞けて楽しかったです．
2 日間とも Nvidia さまがお弁当を提供してくれたり，1 ヶ月間 Reedbush を利用できるという特典も付いているのに参加費は無料という超絶お得なイベントでした．参加してよかったです．
分散深層学習を行うのは初めてだったのですが，難しかったです．私の研究では画像もテキストも扱うので，モデルの大きさによってはバッチサイズを小さくしないと動かないということが起こります．そんな時にデータ並列は [バッチサイズ] × [並列数] が実質のバッチサイズになるので魅力だと思いました．頑張ろうかな．頑張れるかな．
修論で忙しいにも関わらず本記事の最終確認をしてくれた T 氏に感謝いたします．
Latex で画像位置がずれる問題へ対処した話
経緯
lab メンが某会議への論文投稿でハマっていたのをみんなで解決した．ググってもなかなかドンピシャの解決にたどり着けなかったので記事に残す．
想定する読者
- 論文の投稿を dvi + eps 形式で行うように指定されている人
- Overleaf のプレビューでは正しいのに，dvi を出力してコンパイルすると画像位置がどうしてもずれてしまう人
- matplotlib で eps 形式の図を出力して latex に includegraphics しようとしている人
発生した問題
ことの経緯を以下にまとめる．
- モデル図はパワポで作って eps 形式で保存
- グラフは python の matplotlib.pyplot で描画して eps 形式で保存
- Overleaf でこれらの eps ファイルを includegraphics
- コンパイラを latex に設定してコンパイル
- Overleaf のプレビューで正しくコンパイルできていることを確認
- Overleaf のドキュメントに従って dvi 形式でダウンロード
- eps ファイルたちと dvi ファイルを一つのフォルダにまとめて zip
- 某会議に zip ファイルを提出
- 某会議のシステムで pdf にコンパイルされ，その結果がこちらに届く
- 届いたものを確認するとグラフの表示位置がずれている
似たような状況として以下がある．ただしこちらの解決策は今回通用しなかった．
私たちが dvi 形式に疎く，また某会議がわのコンパイル環境がわからなかったこともあり，対処が難航した．Overleaf で出ているエラーを解決したり，includegraphics のオプションで重複のある部分を取り除いたり，利用 OS の種類を某会議への提出時に選択するのだが，それを変えてみたり...．
対処
調査の結果，上記と同じことが起きていたっぽいことがわかった．matplotlib でグラフを保存する際 pdf 形式を選択し，ImageMagic で eps に変換することで解決した．
eps にはいろんな情報が含まれているっぽい．今回は一部の余分な情報が悪さをしてて，pdf にすることでそいつを落としたら解決したのかな，と理解した．知らんけど．
あとがき
Overleaf の問題なのか，某会議の方の問題なのか，ビューワーの問題なのかがわからなくて苦労した．Overleaf で直接 pdf をダウンロードできるので，私含めみんなが dvi を意識したことがなかったのも足を引っ張った．
私含め 5 人でこの問題に対処したのだが，結果的に解決に繋がらなかった方法も含めて，それぞれが鋭い着想に基づいた方法で lab メンつおいってなった．eps 全てではなく，グラフだけがずれていることに着目した lab メンがこの方法を提案し，それを聞いた私が上の記事を見つけた．ちゃんとした位置に図が配置されている pdf を見たときは歓声が上がった．みんなで課題解決するの楽しい．
ちなみに今回は eps 形式という指定があったからそうしたが，選べるのなら eps 形式ではなく pdf 形式で図を入れたほうが安定だと思う．こことかにそう書いてある．
何はともあれ無事投稿できたようで安心．通っているといいな．
Amazon Mechanical Turk (MTurk) を使ってみたメモ
経緯
研究の一環で Amazon Mechanical Turk (MTurk) を使う機会があった．日本語のドキュメントや記事が少なく，ところどころ苦戦したので，使用感などをメモっておく．
私が参考にした大変よくまとまった資料を以下に紹介する．MTurk を使うための資料としては本記事よりもこちらを読むことを推奨する．
想定する読者
- MTurk を使う予定の弊 lab 学生
- クラウドソーシングでデータを集めようと思う人
- MTurk についてなんでもいいから情報が欲しい人
MTurk の概要
MTurk は Amazon が提供する，クラウドソーシングを円滑に行うためのサービスである．MTruk ユーザはワーカかリクエスタどちらかの形態をとる．ワーカは仕事を行う人，リクエスタは仕事を発行する人である．
MTurk の利用：ワーカ編
ワーカは仕事（MTurk では1個の仕事を HIT と呼ぶ）を行う．
HIT 選び
サービス上で現在開かれている HIT 一覧を確認することができる．HIT には仕事内容の簡単な説明，報酬，ワーカ条件，制限時間などが定められている．だいたいどれくらいの時間でできる仕事なのかを説明のところに明記しているものが多いので，それで時給換算できる．ワーカ条件とはその HIT に取り組めるワーカの条件で，『US 在住』『今までで最低 50 件の HITs をこなした』などの項目がある．HIT をクリックすることでより詳細な仕事内容を確認することができる．
HIT への取り組み
詳細な HIT 内容を確認した上で，仕事に取り組むボタン（ボタンの名前は忘れた）を押して，実際に仕事を行う．仕事は選択肢から正解をどんどん選んでいくものもあれば，画像の物体位置に矩形とオブジェクトラベルを付与するようなものもある．このような仕事を制限時間内に行い，最後に submit を押すと仕事を行なったことになる．制限時間をすぎると submit できないので，集中して取り組む必要がある．
報酬の受け取り
ワーカが submit した成果は HIT 発行者であるリクエスタによって確認される．リクエスタが承認するとワーカは報酬を得る．否認すると報酬はもらえない．また，HIT 承認率はワーカ条件として指定可能なため，否認が増えると取り組める HIT が減ることになる．仕事には誠実に取り組みましょう．
MTurk の利用：リクエスタ編
リクエスタは HIT の発行と提出された成果の承認を行う．
HIT の発行
HIT の発行にあたり定義するべき項目はざっと以下の通りである．
- HIT のタイトル
- 仕事内容の簡単な説明
- キーワード（ワーカがHITを検索する上で利用される）
- 報酬
- ワーカ人数
- 制限時間（緩めに設定しておくことが推奨されている）
- ワーカ募集期間（もちろん人数に達した時点で募集をやめることにはなる）
- ワーカの submit から自動承認を行うまでの期間（この期間をすぎると否認できなくなる）
- ワーカ条件
特に気をつけるべきは『報酬』と『制限時間』と『ワーカ条件』である．以下ではそれぞれについて注意点を述べる．
気をつけるべきポイント：報酬編
報酬は適切に定められることが望ましい．だいたい 5$/1h と風の噂で聞いたため，1 時間程度の HIT だった私は 5$ と設定した．ただ，あくまで時給換算は目安であることに注意すべきである．仕事内容や仕事画面の UX 設計によっては，たとえ同じ拘束時間であってもワーカの感じる仕事量に差が出ることがあり，必ずしも時給換算した報酬が適切とは限らない．ワーカが仕事内容の説明を読んで簡単そうだと思うのなら報酬は安めに設定すべきだし，難しそう/めんどそうだと思うのなら報酬は高めに設定すべきである．
特に，報酬が安すぎると全然ワーカが集まらないといったことが起こる．大変...
（20181116追記）クラウドソーシングにおける賃金設定のガイドラインがあるらしい．Guidelines for Academic Requesters - WeAreDynamo Wiki
気をつけるべきポイント：制限時間編
制限時間は厳守される．そのため，制限時間は『普通にやっていれば絶対に超えない時間』くらいには緩めに設定しておくべきである．私の場合は 1 時間の想定に対し制限時間を 2 時間と設定したにも関わらず，1 名のワーカが制限時間をオーバーしてしまった．3 時間くらいにしておけばよかったかなぁ...
気をつけるべきポイント：ワーカ条件編
ワーカ条件には様々なものが選べる．その中で設定するときに特に注意すべきが『HIT 承認率』である．これはそのワーカが今まで submit した仕事のうちどれくらい承認されたかを表すものである．私は最初これを『greater than 99%』としていた．さて，これを和訳するとどういう意味になるだろうか．答えは『99% より上』である．サービスの実装上，この条件だと，承認率 99.3% のワーカも条件外になってしまう．正しくは『greater than or equal 99%（99%以上）』であるべきだ．こんなところで英語力のなさが露呈した...
提出された成果の承認
リクエスタは成果提出者のワーカIDと実際の成果物を確認し，成果物の質によって承認/否認を決定する．何もしなければ自動的に承認される．成果物の質の定義は様々で，私の場合はダミー問題を用意しそれへの正解率を基準に決定した．
否認することはリクエスタにとってもワーカにとってもリスクとなるため，基本的には行わないことが望ましい．よっぽど成果物の質が悪い場合にのみ否認を選択する．否認するときには否認理由を対象のワーカに通知することができる．ワーカはリクエスタのメールアドレスを見ることができるので，説明不足な否認を行うと抗議文が届いたりして面倒なことになりそう．否認理由はしっかりと書くことが望ましい．
その他 MTurk を利用した上で気になったこと
ワーカ-リクエスタ間のやり取りについて
ワーカからリクエスタにはメールを送ることができる．リクエスタからワーカには直接の連絡を取ることができない．リクエスタからワーカに連絡をとる唯一の方法は，成果物を否認するときのメッセージのみである．なんか不公平だよね．
仕事画面の作り方について
仕事画面は MTurk 上で作ることができる．結構様々な機能があるっぽい．ただしアップロードできるデータ量に制限があり，それを超えるような仕事の場合は自前でサイトを作成し，そこへのリンクを飛ばすという方法を取る．この場合 MTurk 上ではサイトから発行する仕事完了コードを受け取るだけになる．完了コードはワーカによって別々のものを発行することが望ましい．
ワーカは MTurk とサイトを行き来することになるので，途中で間違えてページを閉じてしまったりしても大丈夫なように自前サイトにはログイン機能を実装することをおすすめする．また，MTurk 上で受け取る情報はワーカ ID と終了コードのみになるため，成果物の確認をするならば自前サイト側でもワーカ ID をもらう必要があると思う．多分．ワーカ ID は大事なものなので，ちゃんと『もらった情報は研究にしか使いませんよ』的なことを説明書きに書いたり，最低限 https なサイトにしたりする方がいい．
あとがき
なかなか執筆時間が取れず，MTurk を使ってから結構時間が経っての投稿となってしまった．そのせいでところどころうろ覚えで，あまり意味のある文章にはならなかったように思われる．悲しい．弊 lab では今回，共同の MTurk リクエスタアカウントを作成し（てもらっ）た．今後この記事が弊 lab 学生の役に立つことを祈る．
参考にさせていただいたサイト
Amazon Mechanical Turk - Wikipedia
レトリバインターン参加報告
経緯
サマーインターンで2ヶ月間，株式会社レトリバ様（以下敬称を略させていただきます）にお邪魔し，製品開発の職業体験をさせていただいたのでその記録です．
想定する読者
- 来年以降インターン時期になるNLPer
- レトリバに興味がある人
- レトリバの人
選考
インターンに参加しようと思ったきっかけ
弊学ではインターン参加が修士の単位として認められています．毎年多くの M1 が夏休みに 2週間~2ヶ月間 のインターンに参加します．私も夏休みにどこかのインターンに参加することにしておりました．
インターンに参加するには（基本的に）受け入れ機関の審査に合格する必要があります．選考方法は受け入れ機関によって様々ですが，私が受けたところは大体 書類選考→ プログラミング課題 → 面接 の流れだったように思います．プログラミング課題はそれこそ機関によって様々で，時間内に解くものもあれば時間は自由でしっかり作り込むようなものもありました．ただし時間制限がないと言っても学業に差し支えるといけないので，そこは課題を出す側も解く側も気をつけます．
レトリバにしたきっかけ
どうせ行くならしっかりと得られるもののあるインターンに参加したいと思い，1ヶ月以上の長期のインターンを中心に選びました．また，苦学生なのでちゃんとお給料がでるところっていうのも大事です．インターン参加によって普段のバイトをお休みするので，最低でもその分は稼げるところじゃないと生活できません．
このような基準でいくつかのインターンを選び，応募しました．その中でも自然言語処理を前面に推しているレトリバインターンはトップクラスで行きたいものでした．人気が予想され，また枠も少ないので落ちる覚悟でした．なので他のインターン選考も結構ちゃんと進めていました．
結果，一度は落ちたもののご縁あって開発のインターンに参加させていただけることになりました．
レトリバインターンについて少し詳しく
レトリバは例年，研究のインターンを1名程度受け入れています．今年からはインターン枠を少し増やして，研究2名，開発1名という枠でした．狭き門...
レトリバのインターン選考は プログラミング課題→面接 だったかと思います．プログラミング課題は研究も開発も共通です．時間制限がないタイプの課題だったので私なりに結構しっかり作りました．プログラミング技能そのもので私が他の人（特に競プロer）に勝てる気は全くしなかったので，テストや README をちゃんと書くことで差別化を図りました．ちょうどその時期テストにハマっていたんですよ〜．テスト楽しい．テスト通ると嬉しい．
プログラミング課題で通ると面接に進みます．面接は研究開発別々で，どちらも応募している場合はそれぞれ1回ずつあります．遠方にお住いの際はリモート面接OKでした．私はリモートでさせていただきました．大阪-東京 の往復で丸一日潰れてしまうので，リモートOKは助かりました．
面接が終わるとしばらくしてから，具体的には他の候補者の面接が全て終了してから，合否が返ってきます．実は私は一度落ちています．3枠が埋まり，4番手だったらしいです．だったのですが，面接をしていただいた社員さん（インターン期間中のメンターさん）が私のコードの雰囲気を気に入ってくださったようで，私をとりたいと思ってくれていたらしいです．そしてその思いが社長に届いたようで，開発の枠を一つ増やすという取り計らいをしてくださったらしいです．嬉しい．
インターンでやったこと
Answer Finder （レトリバが提供する FAQ 検索システム）の改善
Answer Finder ユーザからいくつかの改善してほしい事項が上がっており，これの原因究明および対応をさせていただきました．以下ざっくりと時系列でやったことをまとめます．
1~2 週目
Answer Finder やその周辺のコンポーネントの開発環境構築や修正の反映方法の確立をしました．コンパイル言語がまず初めてだったので，ビルドでこけた時にめっちゃ詰まりました．メンターさんにビルドとはなんぞやを教わりました．院試勉強で知識としては知っていたけれど，実際のコマンドとリンクしていなかった...
3~4週目
課題の原因究明と対応を2, 3件ぶん行いました．めっちゃC++読んだ．いじるコード量はそんなに多くなかったので，使い慣れている PyCharm で作業していました．それをみた CRO が不思議な顔をしていたのが印象に残っています．わかる．
5週目
中間報告資料作成とか発表練習とか発表本番とかをしました．
Answer Fidner の裏で回っているシステムのリファクタリング
中間報告までで最初に用意されていた課題を全て解決してしまいました．残りの期間は自由にしていいということだったので，Answer Finder の裏で回っているシステムのリファクタリングを強く希望しました．コードをみていてちょくちょく気になったところがあったんですよ．
リファクタリングは『レガシーコード改善ガイド』という本にしたがって進めました．大まかにはまずテストを作って，その上でコードの編集を行うという手順です．また，コードを読みやすく編集する上では『リーダブルコード』を参考にしました．どちらも良本です．
6週目
リファクタリングをする上での目標を定めました．現在は使われていない機能の切り離しを目標とすることにしました．
7週目
テスト作成をしました．テストが圧倒的に足りていなかったので，足りていないところの整備です．ただ時間がなかったのでひとまず外から見たときの挙動がざっと変わらないようにメソッドを絞って単体テストすることにしました．
8週目
リファクタリングをしました．インデントやタブのスタイルの統一という軽いところから初めて，リーダブルなコードになるようにこまごまと編集しました．機能の切り離しまで到達できました．実は機能の切り離しはすでになされていたなんて言えない
並行して最終報告資料作成なども行いました．最終報告は社外に公開されるので緊張しました．発表中に放送が落ちてしまうというハプニングがありつつもなんとか耐えました．
最終報告資料はこちらになります．
業務以外の色々
歓迎会
インターン生および同時期に入社した方の歓迎会がありました．歓迎される側の人は自己紹介の一環として一発芸を披露することが慣例となっているそうです．私は腕を一回転させるっていう関節やわらかい自慢をしました．
昼食
オフィス街に位置しているのでお昼ご飯を食べるところがたくさんあって，毎日「さて今日はどこに行きましょう...」という問答が生じていました．サクラテラス3Fの炭火の焼き魚やさんが好き．
ボドゲ会
ボドゲ好きな社員さんたちが持ち寄ったボードゲームがオフィスにたくさんありました．レトリバでは歓迎会やカジュアルパーティーなどでしばしばボードゲームが行われているそうです．インターン期間中に3回ほどボードゲームに興じました．『私の世界の見方』はゲームに勝手も負けても楽しく，盛り上がるカードゲームでした．『ダイスフォージ』というボードゲームはダイスを強くしていくダイスゲームです．絵柄が綺麗で好き．
社風
レトリバは，その理念の3つ目に人材への投資を掲げるほどに社員を大切にする企業です．リモートワークや半休を気軽に取得できたり，完全週休2日だったり，休憩スペースの備品が充実していたりと働きやすい環境づくりがしっかりとなされていました．あと椅子が最高です．弊研究室の椅子も結構いいやつなのですが，それが霞んで見えるくらいにめっちゃいい椅子でした．
下の要望を上が全力で通そうとしてくれる，というのも感じました．例えば，私の「お客様が実際に製品を使っているところを見たい」という願いを受けて，インターン生の連携企業見学が実際に計画されていました．残念ながら震災の影響で中止になってしまいましたが，それがなければ実際に見学に行けていました．行きたかった...
このように風通しの良い社風で，アットホームな職場です（ホワイト）って感じでした．おかげでのびのびとインターンを楽しめました．
学び
今回のインターンを通じて，製品の保守や，保守しやすいコードとは何かを学ぶことができました．また，2ヶ月間がっつりと職業体験ができて，就職した後の生活を垣間見ることができました．
インターン仲間の参加記たち
feature_importances_ について調べてみた
経緯
授業でランダムフォレストを使ってみる課題が出たが，いまいち feature_importances_ の算出方法がわからずモニョったので調べてみた．
想定する読者
- sklearn を使う人
- 決定木がなんとなくわかる人
- ランダムフォレストが主に分類に用いられるアルゴリズムであると知っている人
sklearn.ensemble.RandomForestClassifierのfeature_importances_ について
概要
from sklearn.ensemble import RandomForestClassifier
model = RandomForestClassifier()
model.fit(train_data, train_label)
importances = model.feature_importances_
すっごく色々はしょるが，こうすると特徴量ごとの重要度が出てくる．
詳しくはこの辺のサイトを参考にしてください．
feature_importances_ の算出方法
では，この feature_importances_ はどのようにして算出されているのだろうか？
これを知るにはまずランダムフォレストのアルゴリズムをおさらいする必要がある．
決定木のアルゴリズム
ランダムフォレストは決定木の集まりでできている．決定木とは以下のようなもののことである．
決定木そのものは訓練データを用いて構築される．
あるノードにおいて分類にもっとも効果的な特徴量を選択し，データ集合の乱雑さが0になるまで，つまりそのノードにおける全てのデータが同じラベルを持つまで，順次ノードを作っていく．ここで言う効果的な特徴量とは，その特徴量によってデータ集合を分割した際にクラスラベルの乱雑さがもっとも減少するものを差す．乱雑さは gini係数やエントロピーなど様々な式で定義でき，sklearn ではデフォルトで gini係数を用いている．
sklearn.tree.DecisionTreeClassifier — scikit-learn 0.19.1 documentation
ランダムフォレストのアルゴリズム
決定木は過学習を起こしやすいとされ，これを避けるのがランダムフォレストである．
ランダムフォレストではまず，訓練データからいくつかの部分データ集合をランダムサンプリングによって生成する．この部分データ集合ごとに決定木を構築することを考える．ただしあるノードにおいて特徴量は，全ての特徴量のうちランダムにサンプリングされたものの中から選択される．こうすることによって全ての決定木が同じような挙動をすることを避ける．
こうして得られた決定木それぞれが分類を行い，その投票によって分類結果が決定される．
feature_importances_ の算出方法
決定木ではある特徴量による分類の前後で乱雑さがどれほど減少するかで特徴量の選定を行っていた．この減少幅を利得と言うことにする．利得は木の構築時に計算されていることになる．
ざっくり言えば，feature_importances_ はこの利得の特徴量ごとの平均である．ただし，決定木の構築に使われたデータのうちいくつのデータがそのノードへ到達したかで重み付けがなされている．たくさんのデータをさばくノードは重要度が高くなると考えれば，この定義は直感的に納得がいく．
詳しい説明はこのサイトを参考にしてください．ベストアンサーの Gilles Louppe 氏は sklearn の開発メンバーの1人です．
あとがき
今回は sklearn.ensemble.RandomForestClassifier の feature_importances_ の算出方法を調べた．ランダムフォレストをちゃんと理解したら自明っちゃ自明な算出だった．今までランダムフォレストをなんとなくのイメージでしか認識していなかったことが浮き彫りなった．この執筆を通してランダムフォレストを分かった気になれたのでスッキリですわ．
ところで開発者本人から回答が来るって羨ましすぎるよ...
ここまで読んでいただきありがとうございました．私の理解が足りていないところなどがあれば，なにとぞ優しくまさかりを投げてください．ちょっとした質問などもいただけると嬉しいです．
今回の執筆にあたって，一緒に調べたり考えたりしてくれた同研究室のT氏にはお世話になりました．
参考にさせていただいたサイト
scikit learn - How are feature_importances in RandomForestClassifier determined? - Stack Overflow
Random Forestで計算できる特徴量の重要度 - なにメモ
http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html
http://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomForestClassifier.html
HMMとCRFとの違いについて調べてみた
経緯
系列ラベリングの代表的な手法として HMM と CRF はそれぞれ聞いたことあるし概要は本を読んでわかったつもりになっているけど，どうもそれらの違いがわからないなぁ...と思ってちょっと調べてみた．意外と日本語の記事が見つからず，英語の記事でいいものがあったのでそれの翻訳兼要約としてまとめる．英語に抵抗感がない人は元記事へ．
CRFとHMMの違いがどうしてもわからなくて延々とググっている．
— ノエル (@saya_hakuren) 2018年5月27日
想定する読者
以下の用語を聞いたことがあるかた
ちなみにこの辺りのことは自然言語処理概論やサポートベクトルマシンを参考にしてください．
HMM と CRF との違いは何か
ざっくり言えば
HMMはナイーブベイズを，CRFはロジスティック回帰を用いる．
以下詳細
以下では入力系列をX=(x1, x2, ..., xi, ..., xn)，ラベル列をY=(y1, y2, ..., yi, ..., yn)とする．
モデリング対象としている確率分布
HMM: XとYとの共起確率 P(X, Y)
CRF: Xが与えられた時のYの条件付き確率 P(Y|X)
学習の仕方
HMM: 学習データ中の出現頻度をカウント．またはEMアルゴリズムなどを用いて出現確率や遷移確率を推定．
CRF: 勾配効果法 (SGD) などの最適化アルゴリズム．
HMMの方がCRFよりも早く学習されるが，CRFの方が推定精度や偏りのある学習データへの頑健性などの面で強い．
系列全体の依存関係への挙動
（単純な）HMM: Xとyiとの依存関係を直接モデル化できない．
（単純な）CRF: Xとyiとの依存関係を直接モデル化できる．
CRFはラベル全体の分布Yをモデル化するだけであり，入力系列全体の分布Xを考慮しない．これに対しHMMは共起確率をモデル化する際にXとYの両方を考慮する必要がある．したがって，CRFはXのyiへの影響を直接モデル化することができる．
ほかの記事では
HMMはP(X, Y)をモデル化しているのに対してCRFはP(Y|X)をモデル化している．このためHMMでは P(X) = ΣP(X, Y) を行うことで，P(X)を求めることができる．P(X)は入力系列Xの確からしさを表しており，つまりはXに対する全てのYのスコアを足し合わせることで言語モデルとして使うこともできる．
あとがき
今回HMMとCRFとの違いという観点から両手法への理解を深めた．HMMは共起確率を，CRFは条件付き確率をそれぞれモデリングの対象としていることが全ての違いの中心にあると感じた．
余談であるがこのブログが私の初めてのブログである．間違ったことはいえねぇと，色々な書籍を引っ張り出して復習した．ブログむずい...．
ここまで読んでいただきありがとうございました．私の理解が足りていないところなどがあれば，なにとぞ優しくまさかりを投げてください．
今回の執筆にあたって，一緒にCRFのことを調べたり考えたりしてくれた同研究室のT氏とT氏には大変にお世話になりました．
参考にさせていただいたサイト
What is the difference between HMM and conditional random field? - Quora
https://www.cs.cmu.edu/~epxing/Class/10701-08s/recitation/em-hmm.pdf
