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

進化的アルゴリズム（EA）の概略とpythonでのEA計算用パッケージDEAPのチュートリアル

遺伝的プログラミング 遺伝的アルゴリズム GP GA 機械学習 python3 DEAP 進化的アルゴリズム EA 最適化問題

この記事について

進化的アルゴリズムを実装するためのフレームワークである、DEAPについて説明します。
この記事では、進化的アルゴリズムの概要について触れつつ、DEAPの公式のドキュメンテーション(DEAP1.3.0 documentation)のFirst stepsとBasic tutorialsを、要約しつつ日本語訳します。

deap.readthedocs.io

進化的アルゴリズムについて

進化的アルゴリズム(evolutionary algorithm、EA)は、進化的計算の一分野で、個体群ベースのメタヒューリスティックな最適化アルゴリズムの総称です。解の探索において、解空間構造が不明で、その問題に固有な知識が使えず、全探索が不可能であるような広大な解空間を持つようなタイプの問題に対して、主に威力を発揮します。
EAは主に次の4つの手法からなります。

この章ではそれぞれのアルゴリズムについて、簡単に説明します。

遺伝的アルゴリズム(GA)について

遺伝的アルゴリズムとは、生物進化における遺伝と適者生存の仕組みをソフトウェア的に真似することで、複雑な問題に対する最適解（の近似値）を模索する（メタヒューリスティクスな）方法です。

概要

遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する手法です。適応度は適応度関数によって定義します。
この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことです。 必要とされる条件は評価関数の全順序性と、探索空間が位相（トポロジー）を持っていることです。
また、遺伝子の表現の仕方によっては組合せ最適化問題やNP困難な問題などのさまざまな問題に適用可能です。
具体的には、ある命題の解の候補を遺伝子(gene)とその集合体である、染色体(chromosome)で表現した個体(individual)を複数用意し、適応度(fitness)の高い個体を優先して選択し、交叉(crossover)、突然変異(mutation)などの操作を繰り返しながら、最適解の探索を行います。

流れ

遺伝的アルゴリズムは一般に以下の流れで実装されます。なお、下記では個体数を N, 最大世代数を G と置きます。

  1. あらかじめ N 個の個体が入る集合を二つ用意します。以下、この二つの集合を「現世代」、「次世代」と呼ぶことにします。
  2. 現世代に N 個の個体をランダムに生成します。
  3. 評価関数により、現世代の各個体の適応度をそれぞれ計算します。
  4. ある確率で次の3つの動作のどれかを行い、その結果を次世代に保存します。
    1. 個体を二つ選択（選択方法は後述）して交叉（後述）を行います。
    2. 個体を一つ選択して突然変異（後述）を行います。
    3. 個体を一つ選択してそのままコピーします。
  5. 次世代の個体数が N 個になるまで上記の動作を繰り返します。
  6. 次世代の個体数が N 個になったら次世代の内容を全て現世代に移します。
  7. 3.以降の動作を最大世代数 G 回まで繰り返し、最終的に「現世代」の中で最も適応度の高い個体を「解」として出力します。

遺伝的アルゴリズムの問題点

遺伝的アルゴリズムには、下に挙げるようないくつか注意しなければならない問題点があります。

  • 初期収束
    初期収束とは、最初の方の世代で偶然他の個体より、圧倒的に適応度の高い個体が生まれてしまったとき、集団の中でその個体の遺伝子が爆発的に増えてしまい、探索がかなり早い段階で収束してしまう減少です。ルーレット選択の設定が甘いときや、突然変異も効果がうまく表れないときに起こりやすいです。
    対策としては、ルーレット選択を行う際に適切な設定をする、適応する問題に対して効果的になるように突然変異の操作を変更する、突然変異率を増やす、または、集団の数を増やすなどがあります。しかし、明確にこれで大丈夫という方法はなく、結局各パラメーターを何度も設定し直すしかありません。

  • ヒッチハイキング
    詳細は省きますが、交叉の手法として、二点交叉を用いた場合、最適解の近くで解がなかなか収束しないという問題です。一様交叉を使うとこの問題は発生しません。

進化戦略について

概要

進化戦略では、実数のベクトルで解を表現し、探索を行うと同時に自己変異用のパラメーターも更新していきます。

First steps

Overview（概観）

まずは、DEAP上で遺伝的プログラミングを実装する際の概要を説明します。これでDEAPのすばらしさが解ると思います。

Types

最初にやるべきことは、適切な問題のタイプを考えることです。これは、Creatingメソッドで行います。

Initilization

Typeを作ったらそこにランダムな初期値を入れます。これには、toolsというメソッドを使います。

Operators

Operatorの定義もInitializationと似ています。いくつかの演算はtoolsの中に予め入っていて、また、ユーザーが自分で演算を定義することも可能です。

Algorithms

上の3つで前段階は終わりです。いよいよアルゴリズムの実装に入ります。これは通常main functionの中で行われます。

Installation

Requirements

DEAPを使用するためには、Python3.4かPython2.7 以上のバージョンである必要があります。この記事では、Python3系の利用を想定しています。また、SCOOPとNumpyが導入されている必要があります。

Install DEAP

DEAPは次のpipコマンドでインストールできます。

pip install deap

Porting Guide

後方互換性についての話が乗っています。特に必要がない場合は読み飛ばしていいでしょう。

Creating Type

このチュートリアルでは、どのようにして、creatorメソッドでtypesが作られるのかとtooboxで初期化がされるのかを見せます。

Fitness（適応度）

Fitnessはweightアトリビュートを必要とする抽象クラス（抽象メソッドを持つクラス）です。適応度を最小化するためには、weightのパラメータを負にします。逆に適応度を最大化する場合は、正にします。下のコマンドはFitnessMinという名前の最小化適応度を作っています。

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))

create()関数は少なくとも２つの引数を必要とします。新しく作るクラスの名前と、ベースとなるクラスです。それ以外の引数は全て、クラスのアトリビュートとなります。

Indivisual（個体）

個体を定義するクラスについての説明です。個体とは、遺伝子の集合として表されます。このクラスはNumpyから、引き継ぐことが可能なので、Numpyから引き継ぎたい人は、下の”Numpyからの引き継ぎチュートリアル”を参照してください。

https://deap.readthedocs.io/en/master/examples/ga_onemax_numpy.html

ここでは、いくつかの個体のタイプについて説明します。

List of Floats（実数値エンコーディング）

最初は遺伝子を、小数を含む単純なリストとして表現する実数値エンコーディングです。このような個体のリストを定義するためには、creatorメソッドを使って、まずIndivisualクラスを作る必要があります。

import random

from deap import base
from deap import creator
from deap import tools

creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

IND_SIZE=10

toolbox = base.Toolbox()
toolbox.register("attr_float", random.random)
toolbox.register("individual", tools.initRepeat, creator.Individual,
                 toolbox.attr_float, n=IND_SIZE)

ここで新しく出てきたregister()メソッドの説明をします。registerメソッドは、少なくとも２つの引数を必要とします。エイリアスとそのエイリアスに渡す関数です。それ以外の引数はすべて、functools.partial()のコマンドが呼びだされたときに、関数に渡されます。

permutation（順列エンコーディング）

各遺伝子を順序を示す数字として表現する順列エンコーディングについての説明です。やり方は上でやったランダムな小数列によるエンコーディングとほとんど同じです。違いはtoolbox.registerの部分だけです。

import random

from deap import base
from deap import creator
from deap import tools

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

IND_SIZE=10

toolbox = base.Toolbox()
toolbox.register("indices", random.sample, range(IND_SIZE), IND_SIZE)
toolbox.register("individual", tools.initIterate, creator.Individual,
                 toolbox.indices)
Arismetic Expression(木構造エンコーディング)

最後に算術表現によく使われる木構造エンコーディングについて説明します。この場合は、PrimitiveSetという算術を定義の集合を作っておく必要があります。下のサンプルコードでは、PrimitiveSetは、"MAIN"という名前で呼び出されています。演算の取る引数の個数をarityといいます。また、個体は、木構造を生成するgenHalfAndHalf()関数によって生成されています。

import operator

from deap import base
from deap import creator
from deap import gp
from deap import tools

pset = gp.PrimitiveSet("MAIN", arity=1)
pset.addPrimitive(operator.add, 2)
pset.addPrimitive(operator.sub, 2)
pset.addPrimitive(operator.mul, 2)

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin,
               pset=pset)

toolbox = base.Toolbox()
toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
toolbox.register("individual", tools.initIterate, creator.Individual,
                 toolbox.expr)
Evolution Strategy（進化戦略）

進化戦略のための個体を作成する手順は、２つのリストを含むという点で、今までのものとは少しばかり異なります。リストのうちの一つは、実際の個体を表し、もう一つは、変異用のパラメータを表しています。今回のサンプルコードでは、listをベースクラスに使う代わりに、array.arrayを継承します。1つのオブジェクトの中に２つの異なるベクトルを生成する関数は用意されていないので、自前でそれを定義してやる必要があります。initES()関数が２つのクラスを受け取り、与えらた範囲内でランダムなパラメータを生成することで、それらのインスタンスを作成します。

import array
import random

from deap import base
from deap import creator
from deap import tools

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", array.array, typecode="d",
               fitness=creator.FitnessMin, strategy=None)
creator.create("Strategy", array.array, typecode="d")

def initES(icls, scls, size, imin, imax, smin, smax):
    ind = icls(random.uniform(imin, imax) for _ in range(size))
    ind.strategy = scls(random.uniform(smin, smax) for _ in range(size))
    return ind

IND_SIZE = 10
MIN_VALUE, MAX_VALUE = -5., 5.
MIN_STRAT, MAX_STRAT = -1., 1. 

toolbox = base.Toolbox()
toolbox.register("individual", initES, creator.Individual,
                 creator.Strategy, IND_SIZE, MIN_VALUE, MAX_VALUE, MIN_STRAT, 
                 MAX_STRAT)
particle

粒子もまた、速度といままで通った経路の中で一番良い場所についての情報を持っているという点で特別なタイプの個体です。このタイプの個体は、今までやってきたようにcreateメソッドによって個体を定義することに加えて、speedとbestそして速度の上限と下限である(smin, smax)を定めてやる必要があります。ここでも、関数を自分で定義してあげる必要があります。

import random

from deap import base
from deap import creator
from deap import tools

creator.create("FitnessMax", base.Fitness, weights=(1.0, 1.0))
creator.create("Particle", list, fitness=creator.FitnessMax, speed=None,
               smin=None, smax=None, best=None)

def initParticle(pcls, size, pmin, pmax, smin, smax):
    part = pcls(random.uniform(pmin, pmax) for _ in xrange(size))
    part.speed = [random.uniform(smin, smax) for _ in xrange(size)]
    part.smin = smin
    part.smax = smax
    return part

toolbox = base.Toolbox()
toolbox.register("particle", initParticle, creator.Particle, size=2,
                 pmin=-6, pmax=6, smin=-3, smax=3)
A Funky One

もし、取り扱っている問題が上で扱った以外の特別なパラメータを必要とする場合でもDEAPでは、簡単に実装することができます。 下のサンプルコードでは、ininCycle() functionによって、整数と実数のlistを作っています。

import random

from deap import base
from deap import creator
from deap import tools

creator.create("FitnessMax", base.Fitness, weights=(1.0, 1.0))
creator.create("Individual", list, fitness=creator.FitnessMax)

toolbox = base.Toolbox()

INT_MIN, INT_MAX = 5, 10
FLT_MIN, FLT_MAX = -0.2, 0.8
N_CYCLES = 4

toolbox.register("attr_int", random.randint, INT_MIN, INT_MAX)
toolbox.register("attr_flt", random.uniform, FLT_MIN, FLT_MAX)
toolbox.register("individual", tools.initCycle, creator.Individual,
                 (toolbox.attr_int, toolbox.attr_flt), n=N_CYCLES)

population（集団）

集団のクラスの作成方法も個体のクラスの作成方法と似ています。個体のクラスではアトリビュートで初期化していたところを、個体や戦略、粒子等で埋めるだけです。ここから、いくつかのタイプの集団についてのクラスの作成方法を説明します。

Bag

bag population(日本語名不明)は、最もよく使われる集団のタイプです。一般的にlistを用いて実装しますが、この集団の集合は、順序を持ちません。bagは特別なアトリビュートを持たないので、特別なクラスを必要としません。この集団は、toolboxのinitRepeat() functionを用いて、直接的に作成できます。

toolbox.register("population", tools.initRepeat, list, toolbox.individual)
Grid

grid populationは近接する個体同士が相互作用し合うような場合に用いる特別な集団のクラスです。各個体は、格子の中に割り当てられます。それぞれの格子には1個体までしか入ることができません。この集団の実装は、複数のlistからなるという点以外はbagの場合とそれほど変わりません。

toolbox.register("row", tools.initRepeat, list, toolbox.individual, n=N_COL)
toolbox.register("population", tools.initRepeat, list, toolbox.row, n=N_ROW)
Swarm(群)

swarm populationは粒子群最適化をするときに使われる手法です。クラスの内部に通信用のネットワークを持っているという点で上の２つとは異なります。使うことがしばらくなさそうなので、今回はこれの詳細についての説明は省かさせていただきます。

Demes

demeは副次的な集団で、集団の中に含まれます。使うことがしばらくなさそうなので、今回はこれの詳細についての説明は省かさせていただきます。

populationの実装例
import json

from deap import base
from deap import creator

creator.create("FitnessMax", base.Fitness, weights=(1.0, 1.0))
creator.create("Individual", list, fitness=creator.FitnessMax)

def initIndividual(icls, content):
    return icls(content)

def initPopulation(pcls, ind_init, filename):
    with open(filename, "r") as pop_file:
        contents = json.load(pop_file)
    return pcls(ind_init(c) for c in contents)

toolbox = base.Toolbox()

toolbox.register("individual_guess", initIndividual, creator.Individual)
toolbox.register("population_guess", initPopulation, list, toolbox.individual_guess, "my_guess.json")

population = toolbox.population_guess()

operators and Algorithms

複雑なアルゴリズムを始める前に、DEAPについている基本的なアルゴリズムについて見てみましょう。最初は、（前節を参考にして）単純な個体クラスを作成することから始めます。そしていくつかの異なる演算子によって、その個体同士を相互作用させます。その後、アルゴリズムやその他のツールをどのようにして利用するか学びます。

A First Indivisual

最初に必要なモジュールをインポートして、個体クラスを作るのに要求される関数を登録します。

import random

from deap import base
from deap import creator
from deap import tools

IND_SIZE = 5

creator.create("FitnessMin", base.Fitness, weights=(-1.0, -1.0))
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("attr_float", random.random)
toolbox.register("individual", tools.initRepeat, creator.Individual,
                 toolbox.attr_float, n=IND_SIZE)

最初の個体は次のようにして作成します。

ind1 = toolbox.individual()

print(ind1)               # [0.86..., 0.27..., 0.70..., 0.03..., 0.87...]
print(ind1.fitness.valid) # False

Evaluation

評価は、進化的アルゴリズムの中で最も個別的な部分です。この部分だけは、ライブラリを使わないで、自分で定義を書かなければなりません。典型的な評価方法は、個体一つを引数としてとり、その個体の適応度をタプルにして返り値にしています。例えば、下のサンプルコードは、さっき作ったind1に対して適合度を計算しています。

def evaluate(individual):
    # Do some hard computing on the individual
    a = sum(individual)
    b = len(individual)
    return a, 1. / b

ind1.fitness.values = evaluate(ind1)
print ind1.fitness.valid    # True
print ind1.fitness          # (2.73, 0.2)

注意点として、評価関数の返り値は必ずタプル形式である必要があります。

Mutation（突然変異）

次に紹介する演算子は突然変異演算子です。deap.toolsモジュールの中にたくさんの突然変異演算子が入っています。それぞれの突然変異には、固有の特徴があり、個体のタイプに合わせて選択する必要があります。望まない挙動を避けるためにも、自分が使用するオペレーターのドキュメンテーションはしっかり読みましょう。
突然変異に関する一般的なルールとしては、それらは変異させることだけするということです。つまり、突然変異演算子を作用させる前に、もし変異する前の個体を保存しておきたいなら、その個体のコピーを作っておいてあげる必要があるということです。

mutant = toolbox.clone(ind1)
ind2, = tools.mutGaussian(mutant, mu=0.0, sigma=0.2, indpb=0.2)
del mutant.fitness.values

一番下の行で適合度の値を削除したのは、そこには変異させる前の個体の適合度が格納されているからです。また、上で突然変異演算子を作用させたことによって、mutantとind2が同じであることに注意してください。

print (ind2 is mutant)    # True
print (mutant is ind1)    # False

Crossover（交叉）

次の紹介する演算子は、交叉演算子です。突然変異演算子同様deap.toolsというところに交叉演算子がたくさん入っていて、個体のタイプに合わせて、選んでやる必要があります。
交叉演算子に関する一般的なルールとしては、この演算子は、個体同士を配偶させるだけであるということです。つまり、交叉演算子を作用させる前に、もし交叉させる前の個体を保存しておきたいなら、その個体のコピーを作っておいてあげる必要があるということです。 では実際に予めクローンをつくておいた個体に対して、交叉演算子を作用させてみます。

child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxBlend(child1, child2, 0.5)
del child1.fitness.values
del child2.fitness.values

Selection（選択）

選択は集団クラスに対して作用させる演算子で、deap.toolsに格納されています。選択演算子の第一引数には、個体のiterableな変数を入れる必要があり、第二引数には選択する個体の数を入れます。そして返り値は、選択された個体のリストとなっています。

selected = tools.selBest([child1, child2], 2)
print child1 in selected   # True

そして、たいていは選択のあとか、個体を変化させる前に、すべての集団の複製を作ります。

selected = toolbox.select(population, LAMBDA)
offspring = [toolbox.clone(ind) for ind in selected]

Using Toolbox

toolboxの使い方について書いてあります。要約すると、deap.toolsの中にある諸々の関数はToolboxに登録して使うと管理しやすいというようなことが書いてあります。Toolboxには、register()とunregister()の２つのメソッドを主に使って、toolの登録と解除を行います。

from deap import base
from deap import tools

toolbox = base.Toolbox()

def evaluateInd(individual):
    # Do some computation
    return result,

toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evaluateInd)

Computing Statistics

しばしば、最適化の過程で何が行われているのかを調べるために、統計量を計算したくなることがある。Statisticsは任意のデザインされたオブジェクトのアトリビュートに対して、統計量を取得することができます。そのためには、望む統計オブジェクトが内包されている統計関数をtoolboxに登録する必要があります。

stats = tools.Statistics(key=lambda ind: ind.fitness.values)

statisticsオブジェクトは最初の引数にkeyを指定する必要があります。

stats.register("avg", numpy.mean)
stats.register("std", numpy.std)
stats.register("min", numpy.min)
stats.register("max", numpy.max)

うえのコードによって、統計関数が登録されました。register関数は、第一引数にエイリアスを要求して、ベクトルに作用する関数を第二引数に要求します。

Predefined Algorithms

eaSimple(), eaMuPlusLambda(), eaMuCommaLambda(), eaGenerateUpdate()というような予め用意されているアルゴリズムを使う場合、統計量オブジェクトは、アルゴリズムに引数として渡せば良いです。

pop, logbook = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=0, 
                                   stats=stats, verbose=True)

こうすると、集団のすべての世代ごとに統計量が毎回計算されます。verboseオプションをTrueにしてると、最適化が行われている間にも、統計量が表示されるようになります。アルゴリズムが終了すると、終状態における集団とLogbackが出力されます。

Writing Your Own Algorythm

自分でアルゴリズムを書くときは、統計量を含めることは、とても簡単です。compile()メソッドを呼び出すだけで良いです。

record = stats.compile(pop)

そしてこの統計量の値は、print()関数で呼び出すことができます。

>>> print(record)
{'std': 4.96, 'max': 63.0, 'avg': 50.2, 'min': 39.0}

Multi-objective Statistics

numpyの関数を使って、統計量は直接計算されているので、すべてのオブジェクトはnumpyのデフォルトの振る舞いでまとめることができます。それゆえ、どれについて統計関数を作用させるかは、statsオブジェクトを宣言するときに、指定する必要があります。

stats = tools.Statistics(key=lambda ind: ind.fitness.values)
stats.register("avg", numpy.mean, axis=0)
stats.register("std", numpy.std, axis=0)
stats.register("min", numpy.min, axis=0)
stats.register("max", numpy.max, axis=0)

Multiple Statistics

Logging Data

統計関数で計算された統計量は、Logbookに保存され、あとから呼び出せるようになっています。

logbook = tools.Logbook()
logbook.record(gen=0, evals=30, **record)

Logbookから特定の統計量だけを抜き出してくることもできます。

gen, avg = logbook.select("gen", "avg")

Logbookはピッケル化可能なオブジェクトです。

import pickle
    pickle.dump(logbook, lb_file)

Printing to Screen

logbookはスクリーンやファイルに出力することができます。

logbook.header = "gen", "avg", "spam"

>>> print(logbook)
gen   avg      spam
0     [ 50.2]

Dealing with Multi-statistics

logbookはMultiStatisticsオブジェクトの返り値である辞書の辞書型の値にも対応しています。それぞれの辞書型変数は、chaptersの中に格納されています。なので、複数のオブジェクトの統計も一つの場合と同じように扱うことができます。

logbook = tools.Logbook()
logbook.record(gen=0, evals=30, **record)

ひとつの違いは、カラムの順序で、したのようにします。

logbook.header = "gen", "evals", "fitness", "size"
logbook.chapters["fitness"].header = "min", "avg", "max"
logbook.chapters["size"].header = "min", "avg", "max"

出力は以下のようになります。

>>> print(logbook)
                     fitness                 size
            -------------------------  ---------------
gen   evals min      avg      max      min   avg   max
0     30    0.165572 1.71136  6.85956  3     4.54  7

データを引き出すには、下のようにchaptersを介して行います。

gen = logbook.select("gen")
fit_mins = logbook.chapters["fitness"].select("min")
size_avgs = logbook.chapters["size"].select("avg")

Some Plotting Suger

最適化が終わったときに最も一般的によくする操作の一つは、進化の過程のデータをプロットすることです。Logbookによって、この作業はとても効率的に行なえます。これは、matplotlibを使って行います。

gen = logbook.select("gen")
fit_mins = logbook.chapters["fitness"].select("min")
size_avgs = logbook.chapters["size"].select("avg")

import matplotlib.pyplot as plt

fig, ax1 = plt.subplots()
line1 = ax1.plot(gen, fit_mins, "b-", label="Minimum Fitness")
ax1.set_xlabel("Generation")
ax1.set_ylabel("Fitness", color="b")
for tl in ax1.get_yticklabels():
    tl.set_color("b")

ax2 = ax1.twinx()
line2 = ax2.plot(gen, size_avgs, "r-", label="Average Size")
ax2.set_ylabel("Size", color="r")
for tl in ax2.get_yticklabels():
    tl.set_color("r")

lns = line1 + line2
labs = [l.get_label() for l in lns]
ax1.legend(lns, labs, loc="center right")

plt.show()

Using Multiple Processors

この節には、分散処理のやり方についての説明が書いてありますが、今回は省略します。

正規分布への最尤推定の推定値の求め方

最尤推定 統計学 勉強

正規分布への最尤推定とは、母集団が正規分布に従うという仮説の下で、標本データをどの正規分布に当てはめるのが一番尤もらしいかを推定する方法です。
平均\mu、分散\sigma ^ 2の正規分布の確率密度関数は、以下で表せます。

\begin{aligned} \frac{1}{\sqrt{2 \pi \sigma ^ 2}} exp \left( - \frac{(x - \mu) ^ 2}{2 \sigma ^ 2} \right) \end{aligned}

なので、データが正規分布に従うと仮定した場合やるべきことは、データから最も尤らしい平均値\mu ^ *と分散\sigma ^ {2 *} を求めることだけです。すなわちこの二つのパラメータを求めるのが、最尤推定ということになります。数式では、以下のように表せます。

\begin{aligned} \mu ^ {\\*} = \max _ {\mu} \prod _ {i=1} ^ N p(x _ i) \\ \sigma ^ {2 \\*} = \max _{\sigma ^ 2} \prod _ {i=1} ^ N p(x _ i) \end{aligned}

上の式は、一番実現確率が高いp(x)をあらわしています。つまり、サンプルの集合(x _ 1,...,x _ n)に対して、どのような正規分布の時に、nこのサンプルの同時実現確率p(X _ 1 = x _ 1,...,X _ n = x _ n)が最も大きくなるかというのを考えているわけです。積の形で表さているのは、それぞれの標本が独立であることを暗に仮定しているためです。ちなみにこの最大化する確率の積のことを尤度といいます。そして、尤度の対数をとったものを対数尤度といい、尤度を最大化することと、対数尤度を最大化することは等価であることが知られています。

さて、上の式の解を求めるのにはどうしたらいいでしょうか。正規分布の確率密度関数は、\muで2回微分してあげると、定数\times ((x-\mu) ^ 2) ^ N \times指数関数の項　となっているので、これは広義の凸関数であることが分かります。また、\sigmaについても2回微分をすると同様のことが言えます。したがって、最大値を与える\mu,\sigmaは必ず存在して、しかも、次の関係式が成立します。

\begin{aligned} \frac{\partial \prod _ i p(x _ i)}{\partial \mu} = 0 \\ \frac{\partial \prod _ i p(x _ i)}{\partial \sigma ^ 2} = 0 \\ \end{aligned}

これを解くと、最尤推定値は以下のようになることが分かります。

\begin{aligned} \mu ^ {\\*} = \frac{1}{N} \sum _ {i=1} ^ N x _ i \\ \sigma ^ {2 \\*} = \frac{1}{N} \sum _ {i=1} ^ N (x _ i - \mu) ^ 2 \\ \end{aligned}

ここからわかるように最尤推定値は標本の平均と分散に一致します。 つまり、標本の平均と分散を求めるという行為は、正規分布（と標本の独立性）を仮定して、母集団分布の平均と分散を求める行為であるといえます。

ケルト人について

はじめに

なぜか知らないけど、ケルト人について書きます。

目次

概要

大陸のケルト

ケルト人は、青銅器時代に中部ヨーロッパに広がり、その後期から鉄器時代前期にかけてハッシュタット文化を発展させたと考えられています。
ケルトの社会は、鋭利な鉄製武器を身に着け、馬に引かれた戦車に乗った戦士階級に支配されていました。ケルト人は概して好戦的であったようです。彼らは部族単位で生活しており、特定の国家を形成せず、欧州各地の様々な民族と接触し混じりあっていました。しかしそれゆえ、戦士としては強靭で優れていたにも関わらず、紀元前一世紀頃、カエサルらが率いるローマ軍の組織力の前に衰退し、やがて、500年にわたって、ローマ帝国の支配を受けることとなります。ローマの被支配層となった、ガリア地域に居住していたケルト人は、俗ラテン語を話すようになり、中世にはゲルマン系のフランク人に吸収されフランス人に変質していきます。

島のケルト

ケルト人がいつブリテン諸島に渡来したかははっきりせず諸説あり、ケルト民族の研究における大きな論点となっております。ここでは、そのことについては、あまり深入りせず、ブリテン島には過去のある時期よりケルト人が定着していたものとして話を進めます。紀元前1世紀頃、大陸のケルトが、ローマ人によって支配されましたが、そのままローマ人はブリテン諸島にも侵攻してきて、イングランドとウェールズはローマの支配を受けてしまいます。 その後、ローマ帝国の影響力の低下した隙をついて、5世紀にアングロ・サクソン人がイングランドを侵略し、イングランドのケルト文化は消失してしまいました。一方西部のウェールズはアングロ・サクソン人の侵略を免れ、ケルトの言語が残存しています。 また、同じブリテン島でも、スコットランドやアイルランドはもともとローマの支配を受けておらず、ケルトの文化が根強く残っています。

ケルトと宗教

当初のケルトの宗教は自然崇拝の多神教で、ドルイドとよばれる神官がそれを司っていました。 初期のドルイドは、祭祀のみではなく、政治や司法にもかかわっていました。ケルト人には、輪廻転生と霊魂の不滅の宗教観があり、ケルト人は勇敢さと人命の軽視は、その死生観からくるものだと考えられます。

ケルトの文化

神官であったドルイドたちは、教えを文字にすることは正しくないと考えており、そのため全て口承で伝えられ、全てを暗記するのに20年かかったものもいるといわれています。それ以外のものの記録には、ギリシャ語を借用していました。
ケルト文化は、呪術的で感情的であり、深く心に訴えかける音楽、詩、美術、文学が育まれてきました。音楽（エンヤ）などは現代でも再び脚光を浴びつつあります。また、あの有名なファンタジー小説の、ハリーポッターや指輪物語はケルト文化が下敷きとなっています。

現代のケルト人

現代における”ケルト人”とは、ケルト語派の言語が話される、アイルランド、スコットランド、マン島、ウェールズ、ブルターニュの人々のことを指します。しかしこの5つの地域の人々で、ケルト系言語を使って日常生活を送る人は、30%程度にすぎないです。しかし近年、さまざまなケルト語再生運動が活発に行われてます。

箱玉系の概要

箱玉系 勉強 離散数学 セル・オートマトン

目次

はじめに

この記事では、箱玉系の概要について説明します。

無限に長い箱玉系

箱玉系(ball-box system、BBS)とは、セルオートマトンの一種で、有限個のボールと無限の長さを持った箱の列から構成されたものです。
各球は次のようなルールで時間発展していきます。ここで、一つの箱には、高々一つのボールしか入れられないと仮定します。


1. 1番左のボールを1番近くの右側の空いてる箱に移動させる。
2. 動かしていないボールのうちで、1番左のボールを1番近くの右側の空いてる箱に移動させる。
3. 全てのボールを動かすまで、2.をくりかえす。


一つのタイムステップ t \rightarrow t+1 の間に、この1〜3が行われます。そして、この時間発展は可逆であることにも注意してください。(右と左を逆にすると過去方向に時間発展します。)下に例を示します。

ボールがある状態を1、ない状態を0として数列で表します。
t=0:...|0|0|0|0|0|0|0|1|1|1|0|0|0|1|0|0|0|0|0|0|0|0|...
t=1:...|0|0|0|0|0|0|0|0|0|0|1|1|1|0|1|0|0|0|0|0|0|0|...
t=2:...|0|0|0|0|0|0|0|0|0|0|0|0|0|1|0|1|1|1|0|0|0|0|...
t=3:...|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|0|0|0|1|1|1|0|...

ひとつの非自明な結果として、例えば上の例だと、初期状態では、3コの連続したボールとそれから右に４ます空いて1つのボールからなります。これを3 + 1と表現することにすると、十分時間発展した後では(上の図だとt \geq 2)、1 + 3となります。これは、任意の初期状態に対していうことができて、他の例を挙げると、t=0で4 + 3 + 1 である時、十分時間発展させると、 1 + 3 + 4というように、大きい順にソートされます。この連続したボールの塊をソリトンと いうこととします。

周期的境界条件（環状に並んだ箱玉系）

箱玉系は次のように、周期的境界条件によっても構成することができます。Lを箱の列の長さ（箱の個数）として、箱の右端と左端がつながっているとします。これは箱が環状につながっているということと同じです。これらに M \leq L/2 - 1 個のボールを配置します。そして、無限に長い箱玉系のときと同じように、1.~3.のルールでボールを時間発展させていきます。ただし今回は、一番左や一番右といった最大を定義することができないので、時間発展の規則を次のように少し変更します。


1. 任意のボールを１つ選び、1番近くの右側の空いてる箱に移動させる。
2. 動かしていないボールのうちで、さっき動かしたボールがあった場所から1番近くの右側のボールを1番近くの右側の空いてる箱に移動させる。
3. 全てのボールを動かすまで、2.をくりかえす。

t=0:||1|1|1|0|0|0|1|0|0|0|0|0||
t=1:||0|0|0|1|1|1|0|1|0|0|0|0||
t=2:||0|0|0|0|0|0|1|0|1|1|1|0||
t=3:||1|1|0|0|0|0|0|1|0|0|0|1||
t=4:||0|0|1|1|1|0|0|0|1|0|0|0||
t=5:||0|0|0|0|0|1|1|1|0|1|0|0||
t=6:||1|0|0|0|0|0|0|0|1|0|1|1||


面白いことに、この規則で1.で初めにどのボールを選んだとしても、系が同じように時間発展することが知られています。また、この時間発展も可逆的です。（つまり、右と左を逆にすると過去方向に進んでいきます。）

上の図から大きなソリトンが小さなソリトンを何回も追い越していることがわかります。無限に長い箱玉系との一番の違いは、状態の種類が有限であるという点です。{}_L C_M個の状態のみ存在しえます。なので、状態の遷移は循環的になります。つまり、有限時間の範囲で元の状態に戻ってくることができるということです。

運搬車によるBBSの局所的な記述

さて、話を無限に長い箱玉系に戻します。実は、箱玉系の時間発展は次のような”運搬車”変数を設定してあげることによって、局所的な記述にすることができます。運搬車は次のようなルールで動きます。

1.はじめ運搬車はすべてのソリトンよりも左側に、存在します。そして、運搬車に載っているボールの数を変数xとしてとります。はじめ運搬車にボールは載っていないとして、x=0とします。
2. 運搬車は一マスずつ右に動いていきます。この時、動くところの状態によって、次のように運搬車とボールの数が変化します。

x 運搬車と出会う前の箱の中の状態（0か1） 運搬車と出会った後の箱の中の状態(0か1) 相互作用後の運搬車の値
x 1 0 x+1
x (> 0) 0 1 x - 1
x = 0 0 0 x = 0
  1. 上の相互作用にのっとり、運搬車をすべてのソリトンよりも右に来てかつ運搬車にボールが載っていない状態になるまで、運搬車を動かす。

...|0|1|1|1|0|0|0|1|0|0|0|0|0|0|...
例えば、時刻t=0で上のようなソリトンの配置になっていたとします。この時運搬車は以下のように動きます。

t=0...|0|1|1|1|0|0|0|1|0|0|0|0|0|0|...
x::::::|0|0|1|2|3|2|1|0|1|0|0|0|0|0|0|...
t=1...|0|0|0|0|1|1|1|0|1|0|0|0|0|0|...

自然な拡張

自然な拡張として次のようなものが考えられます。

  • 運搬車に載せるボールの数を制限する。
  • 箱に入るボールの数の最大値を制限する。

箱玉系の数理の解析では、このような系についてcrystalといわれる代数構造を定義することで、背後の数理構造を調べます。 この記事の目的は、箱玉系の概要を説明することなので、これ以上のことは別の記事で書きます。