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++でそれをやるのは若干手間のかかる作業になる．具体的にはこんな感じで実装した:
#pragma once
#include <algorithm>
#include <functional>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/tuple/tuple.hpp>
namespace aoba {
namespace detail {
template<typename KeyIterator, typename ValueIterator>
struct sort_keyvalue_iter_helper_type {
typedef boost::tuple<
typename std::iterator_traits<KeyIterator>::value_type,
typename std::iterator_traits<ValueIterator>::value_type> value_type;
typedef boost::tuple<
typename std::iterator_traits<KeyIterator>::reference,
typename std::iterator_traits<ValueIterator>::reference> reference;
};
template<typename KeyIterator, typename ValueIterator>
class sort_keyvalue_iterator
: public boost::iterator_facade<
sort_keyvalue_iterator<KeyIterator, ValueIterator>,
typename sort_keyvalue_iter_helper_type<
KeyIterator, ValueIterator>::value_type,
std::random_access_iterator_tag,
typename sort_keyvalue_iter_helper_type<
KeyIterator, ValueIterator>::reference,
typename std::iterator_traits<KeyIterator>::difference_type>
{
public:
sort_keyvalue_iterator() {}
sort_keyvalue_iterator(KeyIterator key_iter, ValueIterator value_iter)
: m_key_iter(key_iter), m_value_iter(value_iter) {}
private:
KeyIterator m_key_iter;
ValueIterator m_value_iter;
friend class boost::iterator_core_access;
void increment()
{
++m_key_iter;
++m_value_iter;
}
void decrement()
{
--m_key_iter;
--m_value_iter;
}
bool equal(const sort_keyvalue_iterator& other) const
{
return (m_key_iter == other.m_key_iter);
}
typename sort_keyvalue_iter_helper_type<
KeyIterator, ValueIterator>::reference dereference() const
{
return (typename sort_keyvalue_iter_helper_type<
KeyIterator, ValueIterator>::reference(
*m_key_iter, *m_value_iter));
}
void advance(
typename std::iterator_traits<KeyIterator>::difference_type n)
{
m_key_iter += n;
m_value_iter += n;
}
typename std::iterator_traits<KeyIterator>::difference_type
distance_to(const sort_keyvalue_iterator& other) const
{
return std::distance(m_key_iter, other.m_key_iter);
}
};
template<typename KeyIterator, typename ValueIterator, typename Compare>
struct sort_keyvalue_iter_compare
: public std::binary_function<
typename sort_keyvalue_iter_helper_type<
KeyIterator, ValueIterator>::value_type,
typename sort_keyvalue_iter_helper_type<
KeyIterator, ValueIterator>::value_type, bool>
{
public:
typedef typename sort_keyvalue_iter_helper_type<
KeyIterator, ValueIterator>::value_type T;
sort_keyvalue_iter_compare(Compare comp) : m_comp(comp) {}
bool operator()(const T& left, const T& right)
{
return m_comp(boost::get<0>(left), boost::get<0>(right));
}
private:
Compare m_comp;
};
template<typename KeyIterator, typename ValueIterator>
sort_keyvalue_iterator<KeyIterator, ValueIterator>
make_sort_keyvalue_iterator(
KeyIterator sort_iter, ValueIterator permute_iter)
{
return sort_keyvalue_iterator<KeyIterator, ValueIterator>(
sort_iter, permute_iter);
}
} // namespace detail
template<typename KeyIterator, typename ValueIterator, typename Compare>
void sort_by_key(
KeyIterator keys_first, KeyIterator keys_last,
ValueIterator values_begin, Compare comp)
{
std::sort(
detail::make_sort_keyvalue_iterator(
keys_first, values_begin),
detail::make_sort_keyvalue_iterator(
keys_last, values_begin + std::distance(keys_first, keys_last)),
detail::sort_keyvalue_iter_compare<
KeyIterator, ValueIterator, Compare>(comp));
}
template<typename KeyIterator, typename ValueIterator>
void sort_by_key(
KeyIterator keys_first, KeyIterator keys_last,
ValueIterator values_begin)
{
sort_by_key(
keys_first, keys_last, values_begin,
std::less<typename std::iterator_traits<KeyIterator>::value_type>());
}
template<typename KeyIterator, typename ValueIterator, typename Compare>
void stable_sort_by_key(
KeyIterator keys_first, KeyIterator keys_last,
ValueIterator values_begin, Compare comp)
{
std::stable_sort(
detail::make_sort_keyvalue_iterator(
keys_first, values_begin),
detail::make_sort_keyvalue_iterator(
keys_last, values_begin + std::distance(keys_first, keys_last)),
detail::sort_keyvalue_iter_compare<
KeyIterator, ValueIterator, Compare>(comp));
}
template<typename KeyIterator, typename ValueIterator>
void stable_sort_by_key(
KeyIterator keys_first, KeyIterator keys_last,
ValueIterator values_begin)
{
stable_sort_by_key(
keys_first, keys_last, values_begin,
std::less<typename std::iterator_traits<KeyIterator>::value_type>());
}
template<typename KeyIterator, typename ValueIterator, typename Compare>
void partial_sort_by_key(
KeyIterator keys_first, KeyIterator keys_middle, KeyIterator keys_last,
ValueIterator values_first, Compare comp)
{
std::partial_sort(
detail::make_sort_keyvalue_iterator(
keys_first,
values_first),
detail::make_sort_keyvalue_iterator(
keys_middle,
values_first + std::distance(keys_first, keys_middle)),
detail::make_sort_keyvalue_iterator(
keys_last,
values_first + std::distance(keys_first, keys_last)),
detail::sort_keyvalue_iter_compare<
KeyIterator, ValueIterator, Compare>(comp));
}
template<typename KeyIterator, typename ValueIterator>
void partial_sort_by_key(
KeyIterator keys_first, KeyIterator keys_middle, KeyIterator keys_last,
ValueIterator values_first)
{
partial_sort_by_key(
keys_first, keys_middle, keys_last, values_first,
std::less<typename std::iterator_traits<KeyIterator>::value_type>());
}
template<typename KeyIterator, typename ValueIterator,
typename OutputKeyIterator, typename OutputValueIterator,
typename Compare>
void partial_sort_copy_by_key(
KeyIterator keys_first, KeyIterator keys_last,
ValueIterator values_first,
OutputKeyIterator result_keys_first, OutputKeyIterator result_keys_last,
OutputValueIterator result_values_first, Compare comp)
{
std::partial_sort_copy(
detail::make_sort_keyvalue_iterator(
keys_first, values_first),
detail::make_sort_keyvalue_iterator(
keys_last,
values_first + std::distance(keys_first, keys_last)),
detail::make_sort_keyvalue_iterator(
result_keys_first,
result_values_first),
detail::make_sort_keyvalue_iterator(
result_keys_last,
result_values_first +
std::distance(result_keys_first, result_keys_last)),
detail::sort_keyvalue_iter_compare<
KeyIterator, ValueIterator, Compare>(comp));
}
template<typename KeyIterator, typename ValueIterator,
typename OutputKeyIterator, typename OutputValueIterator>
void partial_sort_copy_by_key(
KeyIterator keys_first, KeyIterator keys_last,
ValueIterator values_first,
OutputKeyIterator result_keys_first, OutputKeyIterator result_keys_last,
OutputValueIterator result_values_first)
{
partial_sort_copy_by_key(
keys_first, keys_last, values_first,
result_keys_first, result_keys_last, result_values_first,
std::less<typename std::iterator_traits<KeyIterator>::value_type>());
}
template<typename KeyIterator, typename ValueIterator, typename Compare>
void nth_element_by_key(
KeyIterator keys_first, KeyIterator nth_keys, KeyIterator keys_last,
ValueIterator values_first, Compare comp)
{
std::nth_element(
detail::make_sort_keyvalue_iterator(
keys_first, values_first),
detail::make_sort_keyvalue_iterator(
nth_keys,
values_first + std::distance(keys_first, nth_keys)),
detail::make_sort_keyvalue_iterator(
keys_last,
values_first + std::distance(keys_first, keys_last)),
detail::sort_keyvalue_iter_compare<
KeyIterator, ValueIterator, Compare>(comp));
}
template<typename KeyIterator, typename ValueIterator>
void nth_element_by_key(
KeyIterator keys_first, KeyIterator nth_keys, KeyIterator keys_last,
ValueIterator values_first)
{
nth_element_by_key(
keys_first, nth_keys, keys_last, values_first,
std::less<typename std::iterator_traits<KeyIterator>::value_type>());
}
} // namespace aoba
view raw sortings.hpp hosted with ❤ by GitHub
実装したといっても，実際には『Sorting two arrays simultaneously』の内容を若干手直しするだけなので基本的にはそんなに大変じゃないし，ただ利用するぶんには単純にsort_by_key()を呼び出すだけでよい．

しかし，なんでこんなにC++は行数が多くなってしまうのか．haskellなんか一行で済むのに．
投稿時刻 21:19 3 コメント
ラベル: ,

2012/08/21

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

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

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

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

#pragma once
#include <boost/cstdint.hpp>
#include <boost/config.hpp>
#include <cmath>
namespace aoba {
struct halton_sequence_engine {
public:
typedef double result_type;
halton_sequence_engine(): m_index(1), m_base(2) {}
halton_sequence_engine(uint32_t index): m_index(index), m_base(2) {}
halton_sequence_engine(uint32_t index, uint32_t base)
: m_index(index), m_base(base) {}
result_type operator()() {
result_type result = 0;
result_type f = 1 / static_cast<result_type>(m_base);
uint32_t i = m_index;
while(i > 0) {
const uint32_t div_i_base = i / m_base;
const uint32_t mod_i_base = i % m_base;
result = result + f*mod_i_base;
i = div_i_base;
f = f / m_base;
}
++m_index;
return result;
}
void seed(uint32_t index) { m_index = index; }
static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return 0; }
static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () { return 1; }
private:
uint32_t m_index;
uint32_t m_base;
};
} // namespace aoba
view raw halton_sequence_engine.hpp hosted with ❤ by GitHub
具体的には、対象のファンクタがUniform Random Number Generatorのコンセプトを満たすためには以下の記述が必要となる:
  • X::result_typeにoperator()が返す型を指定
  • 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の手法を用いることにする。
投稿時刻 23:58 3 コメント
ラベル: ,

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の式は比較的詳しいですが，実際に計算したところ微妙に間違えている箇所を数ヶ所発見しています
投稿時刻 22:58 6 コメント
ラベル:
Copyright 2009 映像奮闘記. Powered by Blogger.
Blogger Templates created by Deluxe Templates
Designed by grrliz