2012/10/20

C++で2種類のコンテナを同時にソートする

C++でデータを扱っていると,2種類のコンテナを同時にソートしたい場合が時々出てくる.どういうことかというと,
int main() {
    int keys[]   = {5, 3, 1, 2, 4};
    int values[] = {1, 2, 3, 4, 5};
    aoba::sort_by_key(keys, keys+5, values);
    for(int i=0; i<5; ++i) {
        std::cout << keys[i] << " ";   // 1 2 3 4 5
    }
    std::cout << std::endl;
    for(int i=0; i<5; ++i) {
        std::cout << values[i] << " "; // 3 4 2 5 1
    }
    std::cout << std::endl;
    return 0;
}
と,片方のソート結果を元にもう片方をソートするような感じ.これはCUDAライブラリであるthrustに標準搭載されており,sort_by_keyという名前がついている.

さて,こういうときに一からソートアルゴリズムを組み直すなんてことは馬鹿らしい.じゃあどうするか.基本的には既存のstd::sortに渡すイテレータを変形することで,なんとか解決しようとする.そうなると,boostにzip_iteratorが存在することに気付けば,イテレータをboost::tupleの組で表現することによって,まとめてソートさせればいいような気がしてくる.こんな風に:
std::sort(
    boost::make_zip_iteator(
        boost::make_tuple(
            keys_first, values_first)),
    boost::make_zip_iterator(
        boost::make_tuple(
            keys_last, values_last)),
    compare_functor());
しかし,そうは問屋が降ろさない.何故なら,boost::zip_iteratorはWritableではない.これはソートアルゴリズムの要件を満たしていないため,適用させようとしてもコンパイルエラーが発生してしまう!

それじゃあどのようにして解決するかというと,一番楽な方法としてはWritableなコンセプトを満たしたzipイテレータを新しく作ってやって,それを用いてstd::sortを行うのがいい.とはいっても,C++でそれをやるのは若干手間のかかる作業になる.具体的にはこんな感じで実装した:
実装したといっても,実際には『Sorting two arrays simultaneously』の内容を若干手直しするだけなので基本的にはそんなに大変じゃないし,ただ利用するぶんには単純にsort_by_key()を呼び出すだけでよい.

しかし,なんでこんなにC++は行数が多くなってしまうのか.haskellなんか一行で済むのに.

2012/08/21

超一様分布列をBoost.Randomを用いて実装する

ご存知の通り、C++のライブラリには高性能な擬似乱数生成エンジンBoost.Randomが存在している。Boost.Randomは擬似乱数を生成するエンジン部分と、一様分布、ガウス分布、ベルーヌーイ分布など好みの分布を生成する出力部分の2つで構成されている。

しかし、ことモンテカルロ法においては主に収束速度を早める目的として、擬似乱数ではなく低食い違い量列(Low-Discrepancy Sequence, LDS)と呼ばれる数列が用いられる場合がある。これを用いると低次元での積分計算の際に収束速度を大きく改善することができ、具体的には従来のモンテカルロ法で(1/√N)だった収束速度が約(1/N)くらいにまで落とすことができる。

さて、このような低食い違い量列をBoost.Randomで用いるためにはエンジン部分を製作すればいいだけで、実際には以下のような形で実装すれば良い。今回は簡単なHalton列を用いて実装を行った:

具体的には、対象のファンクタがUniform Random Number Generatorのコンセプトを満たすためには以下の記述が必要となる:
  • X::result_typeoperator()が返す型を指定
  • operator()にエンジン部分を記述
  • min(), max()にエンジンが生成する分布の最小値、最大値を指定
さらに、対象のファンクタが上述の内容に加えPseudo-Random Number Generatorのコンセプトを満たすためには:

  • X()にデフォルトの状態で生成されるようなコンストラクタを指定
  • X(...)にユーザ指定の状態で生成されるコンストラクタを指定
  • seed(...)にエンジンの状態を変更するためのメンバ関数を指定
するだけで良い。後はBoost側が良きに計らってくれる。非常に便利だと思う。

余談
C++0xには同等のstd::randomが付属しているため、これを利用すればいいのではという声もあるとは思うが、std::uniform_real_distribution<>にこのLDSを食わせたところ、どうみてもLDSではない値が出力される結果となった。恐らくresult_typeがdoubleという一般の擬似乱数ではない型を指定しているために起こる現象だと思うが、ソースを見ていないので一先ずは従来のBoost.Randomの手法を用いることにする。

2012/08/18

Restricted Boltzmann Machineの学習手法についての簡単なまとめ



近年の機械学習ではDeep Learningと呼ばれる分野が一世を風靡しています.コンピュータビジョンや自然言語処理,音声認識などの分野では何らかの問題を解こうとした際に,まず対象の入力データからSIFTやケプストラムといった何らかのアルゴリズムを用いて特徴ベクトルを抽出し,ごりごりと判別していくといった流れが一般的です.しかし,その特徴ベクトルを生成するという生のデータから本質となる部分を抽出するアルゴリズム自体は研究者が一生懸命考えながら作るのが普通でした.

Deep Learningの分野で最も有名な手法の一つであるDeep Belief Nets(DBN) [Hinton06]は,研究者がアルゴリズムを作るのではなく,それ自体も機械学習にやらせましょうという動機で生まれたアルゴリズムです.DBNではまるで一昔前にやたら流行ったニューラルネットワークのように各ノードを層状に配置し,それらのパラメータをRestricted Boltzmann Machine(RBM)と呼ばれるモデルを用いて学習することによって自動的に特徴ベクトルを生成します.これが既存手法を大きく超える精度を出してしまったためにDeep Learningは一躍有名となり,ニューラルネットの再来か,機械学習は人工知能の夢を見るか,みたいに言われているような状況です.最近ではGoogleがネコのニューロンを自動的に学習したとかでニュースになっていました.

さて,そのような状況にもかかわらず,そのDeep Belief Netsやその改良版であるDeep Boltzmann Machineを学習するためには,まずその基礎となっているRBMについて学ぶ必要があります.しかしそのRBMですらお世辞にもわかり易いものとは言えず,しかもその最終的な更新式やその導出過程についてきちんと書いている文献は今まで確認したところ存在していません(*1).「チュートリアルや論文だけでは良く分からないので,実際に手を動かして確認したい.だがその計算過程は公開されていないため,結局良く分からないままで終わる」ことが多いように思われました.

ということで,RBMの計算過程について書いた個人用のpdfファイルを公開してみることにします.外部に見せるということで多少文章を詳しくしましたが,これ単体で学ぶのではなく他の資料と比較しながら見るとベターかと思います.多分数式は間違ってないと思いますが,何かありましたらご一報頂けると幸いです.

http://dl.dropbox.com/u/2048288/RestrictedBoltzmannMachine.pdf

*1 Deeplearning.netの式は比較的詳しいですが,実際に計算したところ微妙に間違えている箇所を数ヶ所発見しています