東大 創造情報 院試について(2020年度冬入試)

はじめに

この度、2020年2月に行われた東京大学大学院 情報理工学系研究科 創造情報学専攻の冬院試を受験し、合格しました。
受験に際して、先人達の受験に関するブログ記事を参考にさせていただいたので、自分も今後受験する人たちのために自分の院試勉強内容、試験当日の事、その他感想などを載せておきます。 自分の経歴としては、学部は東大の数物系学科出身（理物でも理数でもない弱いとこ）、夏入試では、物理工学科を受験し一応合格しましたが、志望していた研究室に入れず、受かった研究室が正直あまり自分の興味と合わず、情報系の分野にも興味があったことから、冬に創造情報を受けることにしました。(決めたのは2019年の9月頃)。東大だと冬院試をやっている専攻は、情報学環と情報理工がありますが、情報学環の方は教授の推薦文などが必要で、用意できなかったため受けられず、情報理工の中でもググったら1番冬入試についての情報が多かったので創造情報を受けることにした、という感じです。

院試を受けようとおもった時点での実力

院試勉強開始時点でCS分野の知識はほぼほぼゼロでした。
プログラミングについては、機械学習のバイトをしていて、jupyterlabに書き捨てるようなゴミコードを書いてたぐらいでした。いわゆる競技プログラミングと言われる類のものはやった事がなかったです。9月にatcoderのABCを初めて解いた時、確かABCまで解けてDがTLEで解けなかったというのを覚えています。

やったこと

大学で情報系の授業を取りました。
具体的には、駒場で開講されている情報数理科学7(機械学習の講義)、情報工学Ⅱ(コンピュータアーキテクチャとOSについて)、情報通信理論(情報理論の一部)、情報数理科学演習Ⅱ(競技プログラミングの問題演習をする)を取りました。どれも非常にためになったので、駒場にいる人にはおすすめです()。
授業とは別に、教科書も読みました。読んだ教科書は、離散数学4〜6章、情報理論途中まで、ディジタル回路、コンピュータアーキテクチャの本途中まで、データ構造とアルゴリズム5章までです。詳しくは他の人のブログにあると思うでそれを参考にして下さい。過去問は解いてる時間がなくて、一応問題だけ眺めました。

具体的な記録

9月

とりあえず、冬入試を受けることにしたので、atcoderをはじめました。最初pythonでやっていましたが、c++のほうが早いというのを知って、c++の勉強をはじめました。

10月

バイトをたくさんしてました。

11月

TOEFLを受験しました。勉強期間は大体1週間くらいだっと思います。TOEFLはテンプレートを暗記してるのとしてないのでだいぶ点数が変わるので(多分15点くらいは変わる気がする、writingとspeakingで)、ちゃんと対策をしておいた方がいいと思いました。

12月

卒論とバイトで忙しかったです。

1月

１月の中旬ごろにやるべきことをリストアップした結果一日13時間くらい勉強をしないと終わらないことに気付き、泣きそうになりました。

2月

卒論の発表と院試の試験が被って死にそうになりました。試験終わった後は結果発表までずっとそわそわしてました。

試験当日のことについて

自分の年は、コロナが流行っていたので、中国から来た方は別の教室で受験してさせられているなどイレギュラーな感じがしました。1日目は筆記試験で、2日目がプログラミング、3日目が面接でした。

1日目(筆記試験)

卒研の発表が午前中にあって、大変でした。試験は思ったより簡単で拍子抜けしましたが、自分の年は問題が簡単だったぽくてTwitterでは満点続出だろみたいな声が結構あって、自分はわりと適当に答えた箇所も結構あったので不安になりました。(合格人数何人か知らないし)→自分の年は13人でした。

2日目(プログラミング試験)

多分そんな難しくない問題だったと思うのですが、試験中に頭が全然うごかなくなってしまって非常に焦りました。おかげで3/5解いた時点で30分くらいしか時間がなくて、後の二問は貪欲法で適当に書きました。
午後の口述試験は、入力の結果だけ見られてるような感じでした。プログラムの説明とかは全くしなかったです。あっさりしすぎててやる意味あるのか疑問に思いました。

3日目(面接)

志望分野の知識と卒業研究について聞かれました。時間は5分くらいだっと思います。

やってよかったこと

  • 情報系の授業をとる
    単位も貰えて、院試の勉強にもなってめっちゃ良かったです。

やらなくてよかったこと

  • c++の勉強
    結局pythonで、受験しました。

やれば良かったこと

  • 研究室訪問
    面接で初対面は良くなかったと思います。

  • TOEFL対策もう少し
    あと1週間やればテンプレートをもう少し覚えられたので、あと5〜10点はスコア上がりそうだなあと思いました。

  • 機械学習の勉強
    今後も使うだろうし、第三問で頻出なのでもっと重点的に勉強すれば良かったです。

点数開示

後日公開します。
自分の手答えとしては、筆記の方は、大体全部埋められて、語句の説明が微妙なのがあるかなあという感じなので、8割くらいではないかと思っています。プログラミングの方は、部分点込みで6割くらいかなあと思っています。

TOEFLの方は75点でした。60点くらいを想像してたので運が良かったのかなと思ってます。

参考にしたサイト

後日追加します。

新しく買ったWindows PCにUbuntuをデュアルブートする

はじめに

自分用メモ

環境等

Ubuntu 20.04

必要なもの

手順

1. Ubuntuのイメージファイルを落とす

用意したusbにUbuntuのiosイメージをに入れて、ライブusbを作る。

参考

Linuxをインストールできる「ライブUSBメモリ」をWindowsで作成する方法【スクリーンショットつき解説】 | LFI

2. ハードディスクのパーティションを分割する

参考

jp.easeus.com

3. UbuntuをいれたいPCのBIOS設定を変更して、ライブusbを起動できるようにする。

パソコン起動時にF10連打でbios画面に入れます。（HPのPCの場合）

4. ライブusbを挿して、PCを再起動

5. 自分の好みの設定で、Ubuntuをインストール

気を付けて選ばないとWindowsを消してしまうことになるので注意。

6. BIOSを起動して最初に起動するOSをUbuntuに変更する。

アルゴリズムと計算量、基本的なデータ構造

データ構造とアルゴリズム アルゴリズム コンピュータ科学 勉強

目次

1. アルゴリズムとは

アルゴリズムとは与えられた問題を解くための手順のことです。アルゴリズムは明確な手順を記した疑似コードという形とよばれる表現方法で記述されることが多いです。疑似コードから計算機プログラムへの変換の例として、ユークリッドの互除法のアルゴリズムを紹介します。

例1-1:ユークリッドの互除法

疑似コード

Euclid(m, n) { //整数mとnの最大公約数を返す
    以下の操作を繰り返す
    mをnで割ってあまりをrとする
    もしr=0であれば、計算結果としてnを返し終了
    mにnを代入して、nにrを代入する
}

これをもう少しプログラムらしくすると下のようになります。

int Euclid(int m, int n) { //整数mとnの最大公約数を返す
    repeat
    r << mをnで割ったあまり;
    if (r = 0) return n;
    m << n, n << r;
}

新しい問題を解くためには、自分で新しい問題を解くかなければならないですが、そのためにはまず疑似コードのレベルでプログラムを設計することが大事です。

2. 計算量

アルゴリズムの計算量とは、入力として与えられたデータの大きさnに対して、計算の手間がどれくらいになるかをnの関数として、見積もったものです。普通に考えるとプログラムの動作にかかる時間で議論すべきですが、これは実行する計算機の性能に依存してしまうためアルゴリズム本来の効率を議論するのに適しません。計算量という概念をもう少し明確に定義すると、正定数c,n _ 0が存在して、すべてのn > n _ 0で、T(n) \leq cf(n)となるとき、

\begin{aligned} T(n) = O(f(n)) \end{aligned}

表記します。

3. 配列とリスト

複数のデータが順序を持って並んだもの（列）は計算機が扱うデータの中で最も基本的なものです。列を表現するためには大きく分けて配列による表現とリストによる表現があります。それぞれ短所と長所があるので、プログラムの目的によって適切に使い分ける必要があります。

配列

配列による表現は、あらかじめ確保された連続した領域に要素をしまうもので、列の何番目かの要素を指定すると。O(1)の計算時間で即座にその位置の要素を取り出すことのできるデータ構造です。しかし、列の途中に要素を追加する場合は、それ以降の要素を一つずつ後ろにずらしてあげる必要があり、列の途中の要素を削除する場合はそれ以降の要素を前にずらしてあげる必要があります。どちらもO(n)の計算時間がかかります。

リスト

リストによる表現は、要素一つ一つに独立した領域をもたせ、次の要素を格納している場所を示すポインタを前の要素に持たせておくことで全体を辿れるようにしたものです。配列と違いi番目の要素を取り出すには、前から順に辿って行かなければならず、O(n)の計算時間がかかります。しかし、列の途中に要素を追加したり、削除したりするのには、一つ前の要素と挿入したポインタを付け替えるだけで済むので、計算時間はO(1)で済みます。



以上のように、列へのアクセスが多く長さがあまり変わらないときは配列、逆に列の要素の追加や削除が多く、要素にアクセスするときは最初から順番に取り出すことが多い場合は、リストを使うと良いでしょう。

配列とリストの実装

通常の手続き型言語でデフォルトで用意されているのは配列です。リストを使うためには、自分で実装するか、ライブラリを利用するといいでしょう。ライブラリを利用するときは、実際の実装が明らかになってないことも多いので注意してください。

4. スタックとキュー

スタックとキューについては別の記事で説明したことがあるので、説明を割愛させていただきます。リンク先の記事を参照してください。

slimelimestech.hatenablog.com

キューの実装に当たっては、配列を用いて単純に実装すると、dequeするたびに配列を前に詰める操作が必要になってしまいます。これを避けるために一連の配列領域の先頭と最後尾がリング状に繋がっているとみなして、データの先頭番地と最後尾番地を保持する循環行列という方法があります。

5. 木

木は一つの根のしたのに多数のノードが階層構造をもって接続されているデータ構造であり、一つの親ノードの下に複数の子ノードが接続された形となっています。子を持たない末尾のノードは葉と呼ばれます。データのアクセスは通常根を起点として、中間ノードを辿っていくことで実現されます。木の表現方法としてはセルをポインタで繋いだものが一般的ですが、一つの親ノードに接続される子ノードの個数が一定である場合には配列による表現も可能です。

Linux(Ubuntu18.04)でeduroamに接続する方法

eduroam Wifi Ububtu Linux qiitaっぽい記事

この記事の内容

eduroamにつなげるのに苦労したので、その対処法を書いておきます。

条件

  • すでにユーザーIDとパスワードは取得済みです。

詰まったところ

右上のメニューのWifiタブから、"ネットワークを選択"を選んで、eduroamに繋ごうとすると下のような画面が出てきて、どこに何を入力していいのか分からなくなりました。 f:id:slimelimes:20191129191456p:plain

解決方法

結論としては、上の２つの入力部分は無視して大丈夫です。"CA証明書が要求されましたが存在しません"にチェックを入れて、下の２つの空欄に取得したIDとパスワードをいれれば、接続できます。

Alexa Netの論文"ImageNet Classication with Deep Convolutional Neural Networks."を和訳する。

勉強 論文読み 機械学習 画像認識

はじめに

Alexa Netの論文"ImageNet Classication with Deep Convolutional Neural Networks."を（一部省略しつつ）和訳したので、掲載しておきます。訳が間違っていたら教えてください。

https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf

1 Introduction

最近の物体認識タスクにおいては、ニューラルネットワークの技術を使うのが一般的となっています。ニューラルネットワークのパフォーマンスを向上させるために、より大きいデータセットを集め、より強力なモデルで学習させ、そして過学習を防ぐ良い手法を取り入れる必要があります。しかし、既存の手法では、MNISTの手書き数字の認識のような単純な画像認識タスクはできても、複雑な画像認識タスクを行うためには、非現実的な量のデータが必要でした。CNNを用いた私たちの手法は、既存の手法よりはるかに良い画像認識精度を実現させることに成功しました。我々は、ImageNetの部分集合である、ILSVRC-2010とILSVRC-2012のデータセットを用いて、学習を行いました。

2 The Dataset

ImageNetは、1500万以上の画像と、22,000以上のカテゴリーからなるデータセットです。画像は、webで集められ、Amazon's Mechanical Turk crowded-sourcing toolを用いて、人の手でラベル付けされています。ILSVRCはとある画像認識タスクのコンペティションの名前で、ILSVRC-2010が2010年に行われた、ILSVRCのコンぺでつかわれたデートセットの名前です。そのデータセットはImageNetから作られていて、1000種類のカテゴリーについて、それぞれ1000枚程度の画像があって、合計120万枚の訓練画像と5万の検証データ、15万のテストデータからなるデータセットです。

ILSVRC-2010は、テストセットのラベルが公開されている、唯一のILSVRCのデータセットです。なので我々は、主にこのデータセットを使って、実験を行いました。テストセットのラベルが利用できない、ILSVRC-2012のデータセットを利用する、ILSVRC-2012のコンぺに参加したので、その結果を第6章にまとめておきました。
ImageNetでは、慣例的に2つの誤り率でモデルの精度を評価します。top-1エラー率とtop-5エラー率です。top5エラー率とは、モデルによって予測した答えの上位5つのうちのどれかが、正解ラベルと一致していたら正解とみなす評価方法です。

ImageNetのデータセットには、さまざまな解像度の画像を含みます。我々の手法では、入力の大きさが固定であるので、全ての画像に対して、256 * 256の解像度に変換するダウンサンプリングを行いました。長方形の画像に対しては、最初に短い方の辺が256ピクセルになるようにスケール変換して、その後中心の256*256を切り取って利用しました。それを除くと、訓練セットの各ピクセルからmean activityを引き出すということ以外に、前処理を行っていません。つまり我々は、（ほとんど）生のRGB値を使って、学習を行いました。

3. The Architecture

われわれのネットワークの概要は、図２に記載してあります。（元論文を参照してください。）8つの学習されたのレイヤー（５つの畳み込み層と３つの全結合層）を含みます。以下3.1から3.4のセクションでは、われわれのネットワークの設計において新規のあるいはあまりメジャーではないいくつかの特徴について記述します。セクション3.1~3.4は重要であると思われる順に並んでいます。

3.1 ReLU Nonlinearity

標準的なモデルにおけるニューロンのアウトプット部分では、入力xに対して、f(x) = tanh(x)またはf(x) = \frac{1}{1 + e ^ {-x}}というような関数を用います。最急降下法にかかる学習時間という観点から見ると、これらの関数は漸近が遅く、f(x) = max(0,x)という区分線形関数と比べると学習に時間がかかります。NairとHintonに従って、われわれはこの関数をReLUs(Rectified Linear Units)と呼ぶことにします。ReLUsによる深層CNNの学習は、tanhを使ったものよりも数倍早いです。図1でこのことを実際に示しています。図1は、CIFAR-10のデータセットで4層からなるCNNで訓練誤差が25%以下になるまでにかかる繰り返し回数を表示しています。このプロットによって、巨大なニューラルネットワークで実験を行うには、従来の関数を使っていては収束しないので、だめだということが分かります。

我々は、ニューロンの活性化関数に、従来のものと異なる関数を使用しようと最初に提唱したわけではありません。例えば、Jarrettetらは、非線形関数f(x) = |tanh(x)|が有効であったと主張しました。（あとはこの論文に関する説明なので略）

3.2 複数のGPUに用いた学習

GTX580（GPUの名前）単体では、3GBのメモリしかなく、学習できるネットワークの大きさを制限してしまいます。120万の訓練データは、一つのGPUに載せて学習を進めるには大きすぎるということが分かりました。それゆえ、われわれは、ネットワークを二つのGPUに分散させました。昨今のGPUは並列処理によく適合しており、ホストマシンのメモリを経由することなく、直接GPUのメモリ同士に読み書きできます。並列処理の枠組みは、二つのGPUにそれぞれカーネルを半分ずつのせました。また、GPU同士はある特定のレイヤーにおいてのみ通信をするようにしました。これは例えば、レイヤー3のカーネルは、レイヤー2のカーネルからのすべての出力を入力として受け取ります。一方で、レイヤー4のカーネルは、レイヤー3のうちで、自分と同じGPUに属している部分からのみ入力を受けます。繋ぎ方のパターンを選ぶことは、交差検証法の問題です。しかし、これによって、(コンピュータースペック的に)可能な計算量に達するまでの、通信路の量を調整を正確にすることができます。

結果としてできた構造は、Ciresanらによって、用いられた"柱状の"CNNと幾らか似ているものとなりました。異なる点は、我々の"柱"は、それぞれが独立していないと言う点です。このアーキテクチャを採用することによって、それぞれのレイヤーにおけるカーネルの数を半分にした一つのGPUで実装した場合と比べて、top1エラーとtop5エラーをそれぞれ1.7%と1.2%減らすことに成功しました。また、学習時間に関しても、2つのGPUを使った方が１つのGPUを使った時より、少し短くなりました。

3.3 Local Response Normalization

ReLUには、飽和を避けるための正則化をしなくてもよいという望ましい特徴があります。もし、少なくともいくつかの訓練サンプルがReLUに正の入力を生み出せれば、そのニューロンで学習は起きます。しかしながら、われわれは次のような局所正則化が汎化に役立ちます。a ^ i _ {x,y}を位置(x,y)にあるカーネルiのニューロンの出力とします。

\begin{aligned} b ^ i _ {x,y} = \frac{a ^ i _ {x,y}}{(k +\alpha \sum _ {max(0,i-n/2)} ^ {min(N _ i -1,i+n/2)} (a ^ j _ {x,y}) ^ 2) ^ \beta} \end{aligned}

ここで、シグマ記号は空間的に同じ場所のn近傍のカーネルの出力について二乗和をとることを表しています。N _ iはレイヤーiの中のカーネルの数を表しています。カーネルマップの順序については、もちろん任意性があり、訓練を始める前に決める必要があります。この種の応答正規化は、本物の神経細胞にみられる活動からインスパイアされて、側方抑制の形を実装したものとなっていて、異なるカーネル間を使用して、計算されたニューロン間で大きな活動の競合を引き起こします。
定数k,n,\alpha,\betaは、ハイパーパラメーターで検証セットを使って調整しました。今回はk=2,n=5,\alpha=10 ^ {-4},\beta = 0.75となりました。我々はこの正則化を特定のレイヤーにReLUを適用した後に、おこないました。
この手法は、Jarrettらによって提案された、局所コントラスト正規化法(Local Contrast Normalization)といくつか類似点があります。しかし我々の手法の方が、カーネルの出力の平均値を引くという操作を行っていない分、"輝度の正規化"という意味では、正確です。応答正規化によって、top1エラーとtop5エラーをそれぞれ、1.4%と1.2%減らすことができました。我々は、CIFAR-10のデータセットに対してもこの手法の有効性を確認しました。4層からなるCNNに対して、正規化無しでは13%のエラー率であったのに対して、正規化ありでは11%のエラー率となりました。

3.4 Overlapping Pooling

CNNのプーリング層は、同じカーネルマップの隣接するグループのニューロンの出力をまとめます。伝統的には、隣り合うプーリングユニットによってまとめられる隣接するグループ同士は、重なりません。より正確にいうと、プーリング層は、それぞれがプール単位の位置を中心とするサイズｚ×ｚの近傍をまとめる、ｓピクセル間隔で配置されたプールリングユニットの格子から構成されていると考えることができます。もし、s=zとすると、一般的にCNNで採用されている伝統的な局所プーリングとなります。そして、もし、s<zならば、オーバーラッププーリングとなります。これが、我々のネットワークで採用したプーリングで、s=2およびz=3としました。この手法によって、s=2,z=2のオーバーラップさせないプーリングと比べて、top1エラーとtop5エラーをそれぞれ0.4%と0.3%減らすことができました。実験を通して、オーバーラッププーリングをさせていると過学習しづらくなるということが観察されました。

3.5 Overall Architecture

さて、我々のCNNの全体構成について描写する準備ができました。Figure2に描かれているように、ネットワークは8つの重み付きのレイヤーからなります。最初の5つは畳み込み層で、残りの3つは全結合層です。一番後ろの全結合層の出力は、1000個の出力をソフトマックス関数にします。我々のネットワークは、多項ロジスティック回帰の値を最大します。これは、訓練データにおいて、予測分布の下で正しいラベルの対数確率の平均値を最大化するということと等価です。

2,4,5番目の畳み込み層のカーネルは、同じGPUに属するレイヤーだけと結合しています。3番目の畳み込み層のカーネルは、2番目の畳み込み層のすべてのカーネルと結合しています。全結合層のニューロンはその１つ前のすべてのニューロンと結合しています。応答正規化層は、1番目と2番目の畳み込み層の後につけてあります。マックスプーリング層は、3.4節で詳しく説明したものを、２つの応答正規化層の後ろと、5番目畳み込み層の後ろに付けています。すべての層には、活性化関数として、ReLUを採用しています。

最初の畳み込み層は、224×224×3の入力を11×11×3の大きさの96個のカーネルを4ピクセルずつ動かして、フィルターします。そして、2番目にある畳み込み層が、(応答正規化され、プーリングされた)最初の層からの出力を、入力として受け取り、5×5×48の大きさのカーネルでフィルターします。3,4,5番目の畳み込み層同士の間は、プーリング層や正規化層を挟むことなく繋がっています。3番目の畳み込み層には、2番目の畳み込み層の(正規化され、プーリングされた)出力を入力として受け取る、3×3×256の大きさのカーネルが384個あります。4番目の畳み込み層には、3×3×192の大きさのカーネルが384個あって、5個目の畳み込み層には、3×3×192の大きさのカーネルが256個あります。そして、それぞれの全結合層には、4096個のニューロンがあります。

4 Reducing Overfitting

我々のニューラルネットワークには、6000万個のパラメータがあります。一方で、ILSVRCの1000のクラスは、それぞれの訓練データに対して、画像からラベルへのマッピングに10ビットの制限が課されていますが、これは、かなりの過学習をすることなしには、この非常に多くのパラメータを学習させることはできないということになります。下に、我々が過学習の問題に対処するために使った２つの主な方法を記述します。

4.1 Data Augmentation

画像データの過学習を抑制する、最も簡単で、最もありふれた方法は、ラベルを保存するのような変換によって、人工的にデータセットを増やしてしまうことです。我々は２つの異なる方法によってデータの水増しを行いました。どちらの手法も元の画像データから非常に少ない計算量で新しい画像をつくれるので、水増ししたデータはディスクに保存しておく必要がありません。我々の実装では、変換された画像は、GPUが前のバッチの画像について学習させている間に、CPU上でPythonのコードを使って生成されています。なので、これらのデータの水増しの方法は、事実上、計算コストなしに行なっています。

まず第1の手法は、画像の水平反転とイメージ変換によって生成する方法です。256 \times 256の画像からランダムに224 \times 224のパッチを選び、イメージ変換と水平反転をした画像をネットワークに流し込み、学習させました。もちろん、トレーニングデータ同士の相互依存性は高くなりますが、これによりトレーニングセットのサンプル数が2048倍に増加しました。この手法なしだと、われわれのネットワークはかなり過学習をしてしまい、より小さなネットワークを使わなければならないところでした。テストのときは、ネットワークは5つの224 \times 224パッチと（四隅と中心）その水平反転（合計10個のパッチ）を使って予測を行い、10個のソフトマックス関数の出力して現れる予測値を平均化します。

第2の手法は、トレーニングデータのRGBチャンネルの強度を変えることで画像を生成します。具体的には、それぞれのImageNetの訓練セットのRGBの値のセットに対して、主成分分析を実行します。それぞれの訓練画像に対して、対応する固有値と平均0,標準偏差0.1のガウス分布からランダムにとってきた値を掛けたものに比例した大きさの倍数を発見した主成分にかけたものを足し合わせます。従って、それぞれのRGBピクセルI _ {xy} = (I ^ R _ {xy}, I ^ G _ {xy}, I ^ B _ {xy}) ^ Tに対して、次のような量を加えることとなります。

\begin{aligned} (\bf{p} _ 1, \bf{p} _ 2, \bf{p} _ 3)(\alpha _ 1 \lambda _ 1, \alpha _ 2 \lambda _ 2, \alpha _ 3 \lambda _ 3) ^ T \end{aligned}

\bf{p} _ iと\lambda _ iはそれぞれ、3 \times 3のRGBピクセルの相関行列のi番目の固有ベクトルと固有値を表しています。また\alpha _ iは、前述したようなランダムな値です。それぞれの\alpha _ iは、この手法によって、本来の画像の重要な特徴をだいたい捉えます。つまり、オブジェクトの特徴は輝度とカラーの変化に対して不変であるからです。この手法によって、top1エラー率は、1%以上減少します。

4.2 Dropout

様々なモデルの予測値を混ぜ合わせることは、テスト誤差を減らすのに非常に良い方法です。しかし、この方法は、ニューラルネットワークのサイズが大きいときは、訓練に非常に多くの計算資源を必要とします。しかしながら、モデルを組み合わせるのに非常に良い方法があります。最近導入された、ドロップアウトという手法は、隠れ層のそれぞれのニューロンの出力を確率0.5で0にしてしまいます。この手法によって、"ドロップアウト"されたニューロンは、出力に影響を与えず、また、誤差逆伝播にも関与しません。なので、毎回入力が与えられるたびに、ニューラルネットワークは、重み付けは共有しているが、アーキテクチャが異なるものとなります。この技法は、毎回あるニューロンがそのニューラルネットワークの形状の変化により特定のニューロンに依存できなくなることによって、ニューロンの複雑な共適応を防ぎます。それゆえ、ニューラルネットワークはより頑健な特徴を学習するように強いられます。テストの時は、我々はすべてのニューロンを使いますが、それぞれのニューロンの出力には、0.5をかけます。指数関数的な量のドロップアウトネットワークによって、予測された確率分布の幾何平均を取ることが、もっともらしい近似となるからです。

我々はドロップアウトを、図2にあるような最初の２つの全結合層で利用しました。ドロップアウトを入れないと、我々のネットワークは、かなりの過学習を示します。また、ドロップアウトは、収束するのに必要な試行回数をだいたい2倍にします。

5 Details of learning

我々は確率的勾配降下法を使ってモデルをトレーニングさせました。パラメーターは、バッチサイズ128、モーメンタム0.9、重み減衰(weight decay)が0.005です。我々は、この小さなweight decay の値が、モデルを学習させるのに重要であることを見つけました。つまり、ここでは、weight decay は単なる正則化項ではなく、モデルの訓練誤差を減らすことに貢献しているのです。重みパラメータwの更新規則は次のとおりです。

\begin{aligned} v _ {i+1} := 0.9 \cdot v _ i - 0.0005 \cdot \epsilon \cdot w _ i - \epsilon \cdot ＜\frac{\partial L}{\partial w} | w _ i＞ _ {D _ i} \end{aligned}

iは回数のインデックス、vは運動量を表す変数、\epsilonは学習率、＜\frac{\partial L}{\partial w} | w _ i＞ _ {D _ i}は、i番目のバッチD _ iの目的関数のそれぞれのwに対する導関数のw _ iにおける値の平均を表しています。
まず、それぞれの層の重みパラメータ－を平均0、標準偏差0.01のガウス分布で初期化します。2,4,5番目の畳み込み層のニューロンのバイアスを、全結合している畳み込み層のバイアスと同様に、定数1で初期化します。この初期化は、正の入力が与えられたときの、ReLUの初めの方の学習を加速させます。そして、残りのニューロンのバイアスはすべて定数0で初期化させます。
われわれは、全てのレイヤーに対して、手動で設定した、同じ学習率を学習の間中適用させます。我々が参考にしたヒューリスティクスは、validation errorの減少がストップしたら、学習率を10で割ったものへ置き換えるというものです。学習率は0.01で初期化され、学習を終了するまでに3回学習率を減少させます。我々は、120万の画像セットに対して大体90サイクルを回し、学習終了までに、NVIDIA GTX 580 3GB GPU2台で5~6日ほどかかりました。

6 Results

われわれのILSVRC-2010に対する結果は、表1にまとめられています。我々のネットワークは、top-1およびtop-5テストエラーとして、それぞれ、37.5%と17.0%というスコアを達成しました。ちなみに、ILSVRC-2010コンペでの最高記録が47.1%および28.2%でした。

我々は、ILSVRC-2012のコンペティションに参加し、その結果を表2で記載しています。ILSVRC-2012のテストセットのラベルは非公開であるため、われわれが試したすべてのモデルに対するテストエラーを載せることはできません。この章における注意事項として、差が0.1%以上ないので、検証データとテストデータは交換し合えるということがあります。本論文で使用したCNNは、top-5エラー率が18.2%でした。５つ似通ったCNNの予測結果の平均をとった結果、エラー率は16.4%になりました。あるCNNを、6つの畳み込み層を追加して、ImageNet Fall 2011 のすべての画像（22000カテゴリの1500万の画像）を使って訓練させて、ILSVRC-2012のデータセットを使って”ファインチューニング”したところ、前述したような（ただし今回は7つ）CNNの予測平均のエラー率は15.3%になりました。ILSVRC-2012コンペにエントリーしていたモデルで2番目によかったものは、26.2%のエラー率でした。

最後に、2009年秋バージョンのImageNet(10184カテゴリー、890万枚の画像からなるデータセット)に対してのわれわれのモデルの エラー率を報告します。データセットのうち半分を訓練データに、半分をテストデータに使用しました。データセットの分け方に関しては決まりが存在していないため、他にこのデータセットを使ってモデルを評価した人たちと厳密に同じ条件であるというわけではないですが、この違いは感知できるほどは結果に影響しません。我々のtop-1及びtop-5エラー率はそれぞれ、67.4%と40.9%でした。

6.1 Qualitative Evaluations

図3は、ネットワークでの学習によって得られた畳み込み層のカーネルを示しています。ネットワークは、様々な色の表現とともに様々な方向の振動パターンと方向のカーネルを学習しています。セクション3.5で説明したように、我々のネットワークは２つのGPUによる、特殊なつなぎ方をしていることに注意してください。GPU1のカーネルの多くは、色に無頓着に見える一方で、GPU2のカーネルの多くは、色を特徴量して拾っています。この種の専門化は、毎回起きて、また、重み付けの初期化パラメータと独立な関係にあります。

図4の左側のパネルは、8つのテスト画像に対して、我々が学習させたネットワークによる、top-5の予測を定性的に評価したものです。上の段の一番左にあるmiteの写真のように、対象が中心にない写真でさえも、ネットワークによって認識されていることに注意してください。たいていのtop-5予測は、正当な予測であるように見えます。例えば、leopordの予測結果には、他の種類のネコのみが候補に挙げられています。いくつかのケースでは、(grille,cherry)画像が何を指しているのか曖昧であるために、別のものを検知してしまっています。

ネットワークの視覚的知識を証明する別の方法は、4096次元の隠れ層からなる最後の層の出力イメージから生成される、feature activationを考えることです。もし二つの画像が生成するfeature activation ベクトル同士のユークリッド距離が近いならば、ニューラルネットワークは高いレベルで、その二つの画像が似ているとみなしていると、言えます。図4の右側のパネルは、テストセットからとってきた5つの画像と、トレーニングセットから、この尺度に則って、それと最も似ている画像を6つ並べたものです。ピクセルレベルでは、これらの画像のL2ノルムは一般に、一番左の列の近くないということに注意してください。例えば、トレーニングセットから持ってきた象や犬たちは、いろいろな方向を向いています。補足資料では、たくさんのテスト画像に対する結果を示しています。

二つの4096次元の実ベクトルのユークリッド距離を用いて、類似性を計算することは、効率的ではありませんが、オートエンコーダを用いて、これらの4096次元ベクトルを、短いバイナリコードに押し縮めることは、有効かもしれません。この方法は、最初のデータのピクセルにオートエンコーダを適用するより良い画像を生み出します。というのは、この手法は画像のラベルを活用していなく、それゆえ、その画像が意味論的に一致しているかどうかにかかわらず、似たような輪郭のパターンを持つ画像を選んでしまう傾向にあるからです。

7 Discussion

我々の結果は、大きくて深いネットワークには、かなり難易度の高いデータセットに対しても、純粋な教師あり学習を使って、今までになかったようなすごい記録を生み出しうる能力があることを示しています。ネットワーク中の畳み込み層を一つでも外すと結果が悪くなるということは、注目すべきことです。例えば、任意の中間層を一つ外すと、top-1エラー率がだいたい2%ほど上昇してしまいました。なので、われわれの結果において、ネットワークの深さはかなり重要な役割を占めていることが分かります。

われわれの実験を簡略化するために、いかなる教師なし学習的な前処理を、たとえそれが役に立つことが予想できているものであっても、特に、かなりの量のラベル付けされたデータを利用できて、ネットワークをさらに巨大化できるほどの、十分の計算資源を手に入れていれいたとしても、行っていません。今のところは、我々のネットワークはさらに巨大化させて、長く学習させることで、より良い結果を生み出すと思いますが、人間の下側頭葉を走っている視覚システムとマッチさせるためには、まだ大きな課題があります。究極的には、現在の構造を流用した、とても大きくて深いCNNを映像情報に適用していきたいと思っています。

疑問点

  • 前処理を本当にしなくていいのか？
  • 3.2 1GPUの時とのスペックの比較カーネルの数同じにすべきでは？？
  • 3.3 カーネル同士の順序はどう定義するの？

標準データ構造、区間の調査

アルゴリズム 競技プログラミング C++ 勉強 コンピュータ科学 atcoder

スタック(stack)とキュー(queue)

スタックとキューはどちらもデータを一時的に保存したり、取り出したりするためのデータ構造です。どちらも、データを一列に並べて管理して、新しいデータを列のどちらかの端に保存し、また取り出す際もどちらかの端から取り出します。スタックはあとに保存したデータを先に取り出すデータ構造で、キューは先に保存したデータを先に取り出すデータ構造となっています。また、データを取り出すときに、各データにラベリングされた優先度に基づいて、データを取り出す優先度付きキューという構造もあります。

スタック

概要

スタックは、push()とpop()という２つの操作を提供するデータ構造です。それぞれデータの追加と取り出しを行います。また、現在先頭にあるデータはtop()で参照できます。

命令 スタック
初期状態 [] (empty)
push(3) [3] (top = 3)
push(4) [4, 3] (top = 4)
push(1) [1, 4, 3] (top = 1)
pop [4, 3] (top = 4)

使用上の注意と実装

push(),pop(),top()の計算時間は配列のサイズによらず定数時間です。

#include <stack>
#include <iostream>
using namespace std;
int main() {
    stack<int> S;
    S.push(3);
    S.push(4);
    S.push(1);
    while (! S.empty()) {
        int n = S.top();
        S.pop();
        cout << n << endl; //1, 4 ,3
        }
}

キュー

概要

キューはデータの格納と取り出しができるデータ構造です。現在先頭にあるデータはfront()で参照します。

命令 スタック
初期状態 [] (empty)
push(3) [3] (front = 3)
push(4) [3, 4] (front = 3)
push(1) [3, 4, 1] (front = 3)
pop [4, 1] (front = 4)

使用上の注意と実装

実装には配列やdequeが用いられます。計算コストはpush(),pop(),front()ともに定数時間です。C++には、queueというテンプレートクラスが用意されています。

#include <queue>
#include <iostream>
using namespace std;
int main() {
    queue<int> Q;
    Q.push(3);
    Q.push(4);
    Q.push(1);
    while (! Q.empty()) {
        int n = Q.front();
        Q.pop();
        cout << n << endl; //3, 4, 1
        }
}

優先度付きキュー

概要

優先度付きキューは、データの格納と取り出しができるデータ構造で、データにラベリングされた優先度順に取り出すことができるものです。実装には二分ヒープなどが利用されます。計算コストは、top()は定数時間ですが、push()またはpop()の操作については、格納されているデータの数をNとして、O(\log N)の時間がかかります。

実装

#include <queue>
#include <iostream>
using namespace std;
int main() {
    priority_queue<int> Q;
    Q.push(3);
    Q.push(4);
    Q.push(1);
    while (! Q.empty()) {
        int n = Q.top();
        Q.pop();
        cout << n << endl; //4, 3, 1(大きい順に格納されている？)
        }
}
memo

pythonにはheapqというパッケージがあるので、それを使います。 自分で優先度付きキューを実装する場合は、配列またはvector上に二分ヒープ(binary heap)を作成するのが簡便です。

集合と連想配列

集合(set)

C++で集合を表現するための標準ライブラリとして、setとunordered_set(C++11以降)が用意されています。整数の集合を例にして説明します。どちらもほぼ同じ操作を提供しますが、ここでは、insert（挿入）,size（全体の要素数の取得）,count（指定した要素の有無の検索）を使用します。実装においては、setはデータに順序をつけて、unordered_setは順序を無視して管理をします。前者は通常二分探索木で実装され、挿入や検索には、O(\log N)の時間が必要です。後者は通常ハッシュ表を使って実装され、各操作は平均的には定数時間内で収まると期待されています。

要素の重複を許す場合

C++では、要素の重複を許す集合として、の表現方法として、multisetおよび、unordered_multisetというデータ構造が標準で用意されています。利用方法は通常のset及びunordered_setとほぼ同じです。

連想配列

連想配列とは、keyとそれに対応するvalueのペアを管理するために配列で、例えば、名簿の管理などに使えます。C++では、mapとunordered_mapが標準で用意されています。下の例では文字列がkey、整数がvalueとなっています。

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<string,int> table; // 文字列を数値に対応させる map
table["taro"] = 180;
table["hanako"] = 160;
cout << table["taro"] << endl; // 180
cout << table["ichirou"] << endl; // 0
}
文字列の出現回数

keyが存在しない場合の振る舞いは処理系の設定に依存します。上記の例では0が変えるようになっていて、これを利用して文字列の出現回数を簡単に計測できます。

各データ構造を使う問題

配列Aの連続する部分列について、その和がS以上となるものもうちで最小の長さを求めろ。

すべての区間を調べると、O(N ^ 2)の時間がかかりますが、popとpushを使って合計がSに近い区間のみを調べると、O(N)で処理できます。つまり、はじめキューの合計がSを超えるまでは、キューにpushしていき、Sを超えたら、先頭の要素をpopしていくという方法を取ればいいわけです。いわゆるしゃくとり法と呼ばれる方法です。cinだと遅いのでscanfを使うといいでしょう。

Visual Studioを使ったWindowsでのkaldi環境構築

kaldi 音声処理 Visual Studio Windows qiitaっぽい記事

はじめに

この記事でやること

Windows上でkaldiの環境を構築します。やり方は、下の公式のガイドを参考にしています。

https://github.com/kaldi-asr/kaldi/blob/master/windows/INSTALL.md

目次

使用したバージョン等

  • 作業日：2019年11月8日
  • OS:Windows10 Pro 64ビット
  • CYGWIN_NT-10.0 : 3.0.7(0.338/5/3) x86_64 Cygwin
  • (2.24.0) 64-bit version of Git for Windows

  • Visual Studio

    f:id:slimelimes:20191108150256p:plain
    visualstudio

  • cmake version 3.16.0-rc3

注意

  • egs/にあるサンプルコードは動かせません。これらは、Windows向けに書かれていないからです。
  • そもそもWindows上でkaldiを扱うのは非推奨なので、特別な事情がない限りは素直にLinux上で動かしましょう。
  • ATLAS（線形代数ライブラリ）は使えません。
  • CUDAも使えません。
  • openfst 1.6.5のみサポートされています。
  • gitコマンドを使って、必要なものをインストールする箇所もあります。

手順

1. Cygwinのインストール

Cygwinとは、Windows上で、Linux向けのディストリビューションを動かすためのGNUです。（正確にいうとUnix）

https://www.cygwin.com/

上のurlに行き、Cygwinをインストールしてください。とりあえず全部デフォルトで。以下コマンドはすべてCygwin上で実行しています。

2. Visual Studioをインストールする。

https://docs.microsoft.com/ja-jp/visualstudio/releasenotes/vs2017-relnotes

上のurlからインストールしてきてください。Community版で。インストール内容の指定は、”C++によるデスクトップ開発”のみ選択してください。

3. Git for Windows をインストールする。　　

gitコマンドを使うためにGit for Windowsをインストールします。
下のリンクにアクセスすることで自動でインストールが始まります。 https://git-scm.com/download/win

4. Compiling OpenFST

OpenFSTをコンパイルするには、CMakeがインストールされている必要があります。下のリンクに飛んでダウンロードして、インストールしてください。 Windows版、拡張子がmsiのものを選ぶ。下のサイトと同じやり方でやってください。

https://www.kunihikokaneko.com/tools/win/cmake.html

https://cmake.org/download/

cmakeを有効にするためには、インストール後一回windowsを再起動する必要があります。

インストールしたら、Cygwinを立ち上げて、作業用のディレクトリへ行き、下のコマンドを順に打ち込んでください。

    $ git clone https://github.com/kkm000/openfst.git
    $ cd openfst
    $ mkdir build64
    $ cd build64
    $ cmake -G "Visual Studio 15 2017 Win64" ../

5. kaldiのコンパイル

built64のディレクトリに入り、openfst.slnというファイルを見つけ、VisualStudio17で開いてください。

configuration（構成）を Debug|x64 に切り替えて、solutionをbuildしてください。Release|x64　でも同じようにやってみてください。もし二つのうちの片方でもビルドできないならば、一回ここで止まって、原因を特定するべきです。

kaldiのコンパイル

  1. kaldiの中身を確認しましょう。下のコマンドでkaldiをダウンロードしてください。
 $ git clone https://github.com/kaldi-asr/kaldi.git kaldi
  1. 線形代数ライブラリのインストールをします。下のurlからwindows版をインストールしてください。とりあえずよくわからなかったので、フルパッケージをダウンロードしました。

https://software.intel.com/en-us/mkl

  1. kaldiディレクトリの中のwindowsディレクトリに移動してください。

Example:

  (kaldi)/$ cd windows
  (kaldi)/windows $ pwd
  1. variables.props.dev を　variables.propsにコピーしてください。そのあと、好きなテキストエディタでvariables.propsのパスを正しいものに修正してください。OPENBLASDIR のパスの部分は使わないので無視して下さい。

例

  (kaldi)/windows $ vim variables.props

  1. kaldiwin_mkl.props を kaldiwin.props にコピーしてください。

  2. MSVC solutionを生成する次のスクリプトを呼び出してください。

 (kaldi)/windows$ perl generate_solution.pl --vsver default
  1. 次のコマンドを打ってください。
 (kaldi)/windows$ perl get_version.pl
  1. Visual Studioの中の (kaldi)/kaldiwin_vs_というサブフォルダに生成されているソリューションを開いて、Debug|x64 または Release|x64でビルドしてください。10個のプロジェクトが失敗することが予期されますが。これは想定の範囲内の動作です。テストのコンパイルも失敗しますが問題ないです。（そのうちkaldiの開発者が修正するつもりであるそうです。）

参考

qiita.com