文字コード変換ライブラリICUの紹介

■はじめに
まずはじめに、「文字化けとは何か」と聞かれたらあなたは何と答えますか。それは、

日本に生を受けたプログラマが背負う宿命的な問題

と私なら答えるでしょう。(何、この冒頭w)

皆さん、Webページ制作の経験があったり、自然言語処理をかじった人なら必ず文字化けに苦しまれたことがあると思います。英語のようにアルファベットだけなら何の問題もないのですが、日本語のように漢字や仮名が混じっている場合には文字データを正しい文字コードエンコーディングしないと文字化けを起こします。このように文字コードには複数あり、その指定ミスが文字化けの原因となります。

例えば、日本語の文字コードには、大きく分けて以下の4つがあります。

  • JIS(ISO-2022-JP):JIS規格のX0208で定められた文字コード。7ビットコード2バイトで日本語文字を表現する。
  • Shift_JISMicrosoft社が決めた文字コード。パソコン上のファイル内で日本語文字を表現するために使われている。
  • EUC-JP:日本語UNIX環境で使用される文字コード。8ビットコード2バイトで日本語文字を表現する。
  • Unicode:すべての文字を2バイトで表現した文字コード。世界中の文字を表現しようとしている。

これにより、文字化けを直すには正しい文字コードに変換する必要がある訳ですが、個人的に使えそうだと思った文字コード変換ライブラリを発見したのでそれを紹介したいと思います。文字コード変換ライブラリと言ってもいろいろあるのですが、オープンソースという観点から今回はIBMUnicodeを扱うためのライブラリであるICU(International Components for Unicode)について紹介したいと思います。

ICU(International Components for Unicode)
ICUは、プログラムの国際化を支援するために作成された、世界中で使われている多くの文字コードUnicodeの相互変換を提供するライブラリです。オープンソースであるため、自作のアプリケーションに移植して配布することも可能です。C/C++Javaから使用することができます。

■ダウンロード
まずは以下のサイトからダウンロードします。
ICU - International Components for Unicode

「Download ICU」から辿って、各自の開発環境に対応した圧縮ファイルを選択して下さい。
C/C++版には「C」が、Java版には「J」がファイル名に付いているようです。
2012年11月現在の最新版はバージョン50.1です。

■インストール
Windowsの場合

    • 準備と環境設定
VC++Cygwinが必要になり、これらは前もってインストールされており、環境設定も済んでいるものとして説明していきます。
VC++ 2008 を立ち上げます。
次に、メニューの[ツール]->[オプション]でオプションダイアログを起動し、[プロジェクトおよびソリューション]->[VC++ディレクトリ]でICUディレクトリを設定します。
設定は、ダウンロードした圧縮ファイルを C:\ICU に解凍した場合、"インクルードファイル"に"C:\ICU\icu\source\common"を追記し、"ライブラリファイル"、"実行可能ファイル"に"C:\ICU\icu\source\lib"を追記します。
    • VC++のプロジェクトの設定
[プロジェクト]->[プロパティ]でプロパティダイアログを起動し、[構成プロパティ]->[リンカ]->[入力]で、"追加の依存ファイル"に"icuuc.lib"(デバッグモードの場合は、"icuude.lib")を追記します。今回は文字コードの変換処理だけを使用するので"icuuc.lib"(デバッグモードの場合は、"icuude.lib")だけです。
    • DLLの配置
ソリューションで、exeファイルが生成されるディレクトリに"icudt44.dll"と"icuuc44.dll"(デバッグモードの場合は、"icuuc44d.dll")をコピーします。今回は文字コードの変換処理だけを使用するのでこの2つだけです。
    • サンプルプログラムのビルド
VC++のプロジェクト作成で、空のコンソールアプリケーションを作成します。
作成したプロジェクトへ以下のソースコードを貼り付けたhppファイル、cppファイルなどを作成します。
ビルドして、コンパイルおよびリンクができれば完了です。

MacOSXの場合

    • 圧縮ファイルの解凍
ダウンロードした圧縮ファイル(ここではicu4c-49_1_2-src.tgzを選択)を好きなフォルダに入れて解凍します。
$ tar -xvzf icu4c-49_1_2-src.tgz /(好きなフォルダ)
$ cd /(好きなフォルダ)/icu/source
    • ライブラリの構築
次に、ICUライブラリを構築します。
$ ./configure
$ make
    • インストール
最後に、ICUライブラリとICUインクルードファイルをインストールして完了です。
$ sudo make install
ICUライブラリが /usr/local/lib に、ICUインクルードファイルが /usr/local/include にあることを確認して下さい。
    • パスの追加
環境設定でライブラリパスとインクルードファイルパスにICUのそれぞれのパスを追記します。
    • サンプルプログラムの実行
以下のソースコードを貼り付けたhppファイル、cppファイルなどを作成します。
コンパイルおよびリンクができれば完了です。
# 今は、コンパイルは通るがリンク時にエラーが発生して実行できていない状態です。
# それが解決したら追記するので、もう少し待って下さい。

実は、ターミナルで、

$ sudo port installed

として確認すれば分かるように、MacOSXにはもともとOSが内部で使用するためにICUが組み込まれています。しかし、これをアプリケーション側から利用することはできないため、今までのような事を行う必要があるという訳です。
もし、ICUソースコードにバンドルされていない場合は、portコマンドなどでインストールしておいて下さい。ついでに最新のlibxml2パッケージも必要となるのでここでインストールしておきましょう。

$ sudo port icu install
$ sudo port libxml2 install

■サンプルプログラムの説明
ここでは、文字コード変換プログラムを理解するために必要なAPIの説明を行っていきます。さらに詳しく知りたい人はICUのドキュメントを参照して下さい。

●前準備

文字コード変換APIを使用するためにインクルードします。ソースコードの先頭付近に
#include
を記述します。
    • UErrorCode : エラーコード
処理中に発生したエラーは全てここに書き込まれるようになっています。

●UConverterの生成と解放

    • ucnv_open : UConverterの生成
ここで変換の対象となる文字コード名を指定します。
    • ucnv_close : UConverterの解放

●対Unicode変換

    • ucnv_toUnicode : マルチバイト文字列をUnicode文字列へ変換
あるマルチバイト文字列から別のマルチバイト文字列へ相互変換するために必要な前半のステップ
    • ucnv_fromUnicode : Unicode文字列をマルチバイト文字列へ変換
あるマルチバイト文字列から別のマルチバイト文字列へ相互変換するために必要な後半のステップ

●バッファの大きさ

    • ucnv_getMinCharSize(UConverter* converter) : 指定された文字コードにおける1文字を表現するために必要な最小のバイト数
マルチバイト文字列/Unicode文字列の相互変換をする場合に、変換結果を格納するバッファの大きさを求められます。
入力されるマルチバイト文字列のバイト数をこの値で割れば、出力Unicode文字列バッファに必要な文字数が得られます。
    • ucnv_getMaxCharSize(UConverter* converter) : 指定された文字コードにおける1文字を表現するために必要な最大のバイト数
マルチバイト文字列/Unicode文字列の相互変換をする場合に、変換結果を格納するバッファの大きさを求められます。
入力されるUnicode文字列の文字数にこの値を掛ければ、出力マルチバイト文字列バッファに必要な文字数が得られます。

■サンプルプログラム
以下に、ICU文字コード変換APIを用いてeuc-jpで書かれた"日本"をshift_jisに変換するプログラムを示します。ここで、出力バッファの確保や引数の設定を行うラッパが用意されているので、次のような各変換がシンプルな呼び出しで利用できるようになっています。

  • widen:マルチバイト -> Unicode
    • const char* -> std::wstring
    • std::string -> std::wstring
  • narrow:Unicode -> マルチバイト
    • const wchar_t* -> std::string
    • std::wstring -> std::string
  • convert:マルチバイト -> マルチバイト
    • const char_t* -> std::string
    • std::string -> std::string

使い方についてはヘッダ(UnicodeConverter.hpp)を参照して下さい。

●UnicodeConverter.hpp

#ifndef UNICODECONVERTER_H
#define UNICODECONVERTER_H

#include <unicode/utypes.h>
#include <exception>
#include <string>

struct UConverter;
enum   UErrorCode;

namespace s34 {
    // 'icu_error' exception
    class icu_error : public std::exception {
        UErrorCode error_;
    public:
        explicit icu_error(UErrorCode error)
            : error_(error)
        {}

        virtual const char* what() const throw();
        //virtual const char* what() const;

        UErrorCode code() const {
            return error_;
        }
    };

    // 'open_converter'
    UConverter* open_converter(const char* name, UErrorCode* error =0);

    // 'close_converter'
    void close_converter(UConverter*);

    // 'widen' : multibyte -> doublebyte
    std::wstring widen(const char* source,
                       size_t      sourceLength,
                       UConverter* converter,
                       bool        flush =true,
                       UErrorCode* error = 0);

    inline
    std::wstring widen(const char* source,
                       UConverter* converter,
                       bool        flush =true,
                       UErrorCode* error =0) {
        return widen(source,
                     std::char_traits<char>::length(source),
                     converter,
                     flush,
                     error);
    }

    inline
    std::wstring widen(const char* source,
                       const char* sourceLimit,
                       UConverter* converter,
                       bool        flush =true,
                       UErrorCode* error =0) {
        return widen(source,
                     sourceLimit - source,
                     converter,
                     flush,
                     error);
    }

    inline
    std::wstring widen(const std::string& source,
                       UConverter*        converter,
                       bool               flush =true,
                       UErrorCode*        error =0) {
        return widen(source.data(),
                     source.length(),
                     converter,
                     flush,
                     error);
    }

    // 'narrow' : doublebyte -> multibyte
    std::string narrow(const wchar_t* source,
                       size_t         sourceLength,
                       UConverter*    converter,
                       bool           flush =true,
                       UErrorCode*    error =0);

    inline
    std::string narrow(const wchar_t* source,
                       UConverter*    converter,
                       bool           flush =true,
                       UErrorCode*    error =0) {
        return narrow(source,
                      std::char_traits<wchar_t>::length(source),
                      converter,
                      flush,
                      error);
    }

    inline
    std::string narrow(const wchar_t* source,
                       const wchar_t* sourceLimit,
                       UConverter*    converter,
                       bool           flush =true,
                       UErrorCode*    error =0) {
        return narrow(source,
                      sourceLimit - source,
                      converter,
                      flush,
                      error);
    }

    inline
    std::string narrow(const std::wstring& source,
                       UConverter*         converter,
                       bool                flush =true,
                       UErrorCode*         error =0) {
        return narrow(source.data(),
                      source.length(),
                      converter,
                      flush,
                      error);
    }

    // 'convert' : multibyte -> multibyte
    std::string convert(const char* source,
                        size_t      sourceLength,
                        UConverter* sourceConverter,
                        UConverter* targetConverter,
                        bool        flush =true,
                        UErrorCode* error =0);

    inline
    std::string convert(const char* source,
                        UConverter* sourceConverter,
                        UConverter* targetConverter,
                        bool        flush =true,
                        UErrorCode* error =0) {
        return convert(source,
                       std::char_traits<char>::length(source),
                       sourceConverter,
                       targetConverter,
                       flush,
                       error);
    }

    inline
    std::string convert(const char* source,
                        const char* sourceLimit,
                        UConverter* sourceConverter,
                        UConverter* targetConverter,
                        bool        flush =true,
                        UErrorCode* error =0) {
        return convert(source,
                       sourceLimit - source,
                       sourceConverter,
                       targetConverter,
                       flush,
                       error);
    }

    inline
    std::string convert(std::string& source,
                        UConverter*  sourceConverter,
                        UConverter*  targetConverter,
                        bool         flush =true,
                        UErrorCode*  error =0) {
        return convert(source.data(),
                       source.length(),
                       sourceConverter,
                       targetConverter,
                       flush,
                       error);
    }
}

#endif

●UnicodeConverter.cpp

#include <unicode/ucnv.h>
#include "UnicodeConverter.h"

namespace s34 {

    const char* icu_error::what() const {
        return u_errorName(error_);
    }

    // make_converter
    UConverter* open_converter(const char* name, UErrorCode* error) {
        UErrorCode  innerError = U_ZERO_ERROR;
        UErrorCode* perror = error ? error : &innerError;
        UConverter* converter = ucnv_open(name, perror);

        if( U_FAILURE(*perror) && !error )
            throw icu_error(innerError);

        return converter;
    }

    void close_converter(UConverter* converter) {
        ucnv_close(converter);
    }

    // widen : multibyte --> wide
    std::wstring widen(const char* source,
                       size_t      sourceLength,
                       UConverter* converter,
                       bool        flush,
                       UErrorCode* error) {
        const size_t poolLength = 256;
        wchar_t      pool[poolLength];
        size_t       targetLength = sourceLength / ucnv_getMinCharSize(converter);
        wchar_t*     buffer = ( targetLength > poolLength ) ? new wchar_t[targetLength] : pool;
        wchar_t*     target = buffer;
        UErrorCode   innerError = U_ZERO_ERROR;
        UErrorCode*  perror = error ? error : &innerError;

        ucnv_toUnicode(converter,
                       &target, target + targetLength,
                       &source, source + sourceLength,
                       0, flush, perror);

        if(U_FAILURE(*perror) && !error) {
            if ( buffer != pool )
                delete[] buffer;

            throw icu_error(innerError);
        }

        std::wstring result(buffer,target);

        if(buffer != pool)
            delete[] buffer;

        return result;
    }

    // narrow : wide --> multibyte
    std::string narrow(const wchar_t* source,
                       size_t         sourceLength,
                       UConverter*    converter,
                       bool           flush,
                       UErrorCode*    error) {
        const size_t   poolLength = 256;
        char           pool[poolLength];
        size_t         targetLength = sourceLength * ucnv_getMaxCharSize(converter);
        char*          buffer = ( targetLength > poolLength ) ? new char[targetLength] : pool;
        char*          target = buffer;
        UErrorCode   innerError = U_ZERO_ERROR;
        UErrorCode*  perror = error ? error : &innerError;

        ucnv_fromUnicode(converter,
                         &target, target + targetLength,
                         &source, source + sourceLength,
                         0, flush, perror);

        if(U_FAILURE(*perror) && !error) {
            if(buffer != pool)
                delete[] buffer;

            throw icu_error(innerError);
        }

        std::string result(buffer, target);

        if(buffer != pool)
            delete[] buffer;

        return result;
    }

    // convert : multibyte --> multibyte
    std::string convert(const char* source,
                        size_t      sourceLength,
                        UConverter* sourceConverter,
                        UConverter* targetConverter,
                        bool        flush,
                        UErrorCode* error) {
        const size_t poolLength = 256;
        size_t       targetLength;

        targetLength = sourceLength / ucnv_getMinCharSize(sourceConverter);
        wchar_t  wpool[poolLength];
        wchar_t* wbuffer = ( targetLength > poolLength ) ? new wchar_t[targetLength] : wpool;
        wchar_t* wtarget = wbuffer;
        UErrorCode   innerError = U_ZERO_ERROR;
        UErrorCode*  perror = error ? error : &innerError;

        ucnv_toUnicode(sourceConverter,
                       &wtarget, wtarget + targetLength,
                       &source,  source  + sourceLength,
                       0, flush, perror);

        if(U_FAILURE(*perror)) {
            if(wbuffer != wpool)
                delete[] wbuffer;
            if(!error)
                throw icu_error(innerError);

            return std::string();
        }

        targetLength = (wtarget - wbuffer) * ucnv_getMaxCharSize(targetConverter);
        char     pool[poolLength];
        char*    buffer = ( targetLength > poolLength ) ? new char[targetLength] : pool;
        const wchar_t* wsource = wbuffer;
        char*    target = buffer;

        ucnv_fromUnicode(targetConverter,
                         &target,  target + targetLength,
                         &wsource, wtarget,
                         0, flush, perror);

        if(U_FAILURE(*perror) && !error) {
            if(wbuffer != wpool)
                delete[] wbuffer;
            if(buffer != pool)
                delete[] buffer;

            throw icu_error(innerError);
        }

        std::string result(buffer, target);

        if(wbuffer != wpool)
            delete[] wbuffer;
        if(buffer != pool)
            delete[] buffer;

        return result;
    }
}

●test.cpp

#include <iostream>
#include <unicode/ucnv.h>
#include "UnicodeConverter.h"

int main() {
    std::string euc_jp = "\xC6\xFC\xCB\xDC";

    try {
        UConverter* sourceConverter = s34::open_converter("euc-jp");
        UConverter* targetConverter = s34::open_converter("shift_jis");

        std::cout << s34::convert(euc_jp, sourceConverter, targetConverter) << std::endl;
        s34::close_converter(sourceConverter);
        s34::close_converter(targetConverter);
    }
    catch(s34::icu_error& ex) {
        std::cerr << ex.what() << std::endl;
    }

    return 0;
}

■おわりに
お分かりの通り、プログラム内で文字コード変換が必要になった場合に、特にICUを使わなくても別の方法で行うこともできます。しかし、ICUを利用するメリットとして、「コードの移植性が高い」という点が挙げられます。そのために、何らかのアプリケーションに組み込んで配布することを目的に使用する人にとっては必要になると思ったので、今回紹介することにしました。

■参考にしたページ
株式会社エス・スリー・フォー » ICUの文字コード変換を使いたいのですが…
株式会社エス・スリー・フォー » ICU 2.x : UnicodeString による文字コード変換
文字コード変換ライブラリ「ICU」セットアップ: プログラマーの雑記帳
ICU(1) ICU Unicodeライブラリを古いVC++で環境設定する : OFF-SOFT.net

GDD2011, DevQuizのスライドパズルの解答コードを公開しました

去年の話になりますが、Google Developer Day 2011(GDD2011)に参加するために、DevQuizに挑戦しました。
お分かりの通り、開催されてから1年以上は経っているのですが、つい最近になって探索アルゴリズムの復習でもしようと思って(研究とは全く関係ない…)、もう一度初めからDevQuizを解き直してブログを書くことにしました。参加してた時に書けよっていうツッコミは勘弁して下さい… あれから時間はかなり経っているとは言え一度やっている問題だからなのか、少しプログラミングの腕が上達しているからなのか、去年よりも少し短い期間で、しかも6つの探索アルゴリズムの動作を比較できるくらいまでに実装できてしまいました。

■DevQuiz
さて、そのDevQuizについてですが、去年の問題の構成は、

問題

  • ウォームアップクイズ
    • クイズ:40点
  • 分野別クイズ(最大2問が得点に加算)
    • Web Game:30点
    • Go!:30点
    • Android:30点
    • Google Apps Script:30点
    • 一人ゲーム:30点
  • チャレンジクイズ
    • スライドパズル:50点

となっており、全部で合計150点満点だったのですが、その中でも一番難しかったチャレンジクイズの「スライドパズル」について、今回は自分の解答を公開したいと思います。

■スライドパズル
スライドパズルの問題について説明しておくと以下のようになります。

  • 幅3〜6、高さ3〜6マスのボードが与えられる
  • ボードの各マスには、パネル、壁、空白のいずれかが存在する(壁は0個以上存在)
  • パネルは1〜9あるいはA〜Z、壁は=、空白は0で表記される
  • 空白は上下左右のパネルと入れ替えられるが、壁とは入れ替えられない
  • 空白を上下左右のパネルと入れ替えることをそれぞれU, D, L, Rと呼ぶ
  • ゴールの状態は、左上から右下に向かって1, 2, 3, ..., 9, A, B, ..., Zのパネルが順番に並んで、最も右下のマスに空白が配置された状態
  • 与えられた初期配置をゴール状態の配置にまで移動させる解をU, D, L, Rの文字列で解答する
  • 問題数は全5000問で、パズルを1問解くごとに0.01点が加算される(つまり全問解くと50点になる)
  • 解答に使えるU, D, L, Rの総数にはそれぞれ上限があり、いずれか一つでも超えていた場合には0点となる

■探索アルゴリズム
先ほども述べたように以下の6つの探索アルゴリズムを実装したので、それぞれについて簡単に説明したいと思います。

幅優先探索
幅優先探索ですが、最初に見つかる解が必ず最適解(最短手数の解)になるという手法です。全ての局面をまじめに探索するために計算時間が長くなってしまうだけでなく、局面をインデックス化して保存する場合にハッシュ値に変換しておかないと、ボードのパネル数が増えた場合に当然メモリが足らなくなってしまいます。おそらく普通にこの手法を使った場合、3×4あるいは4×3の11パズルを解くのが限界だと思います。

・双方向幅優先探索
双方向幅優先探索ですが、先ほど述べたように幅優先探索では膨大な計算時間が掛かってしまうので、スタートから探索するだけでなくゴールからも探索を行うことで、高速化を実現しようとする手法です。まだちゃんと試していないのですが、この手法なら4×4の15パズル以上を解くことも可能だと思います。

深さ優先探索
深さ優先探索ですが、これは別名「山登り法(hill-climbing method)」とも呼ばれ、幅優先探索のように全ての局面を保存するなどせずに、ゴールまでの距離(コスト)を示す何らかの評価値に従って、常に評価値が高くなるように次の局面状態を選択します(ヒューリスティック探索)。局面を保存する必要がないためにメモリ消費量は少ないのですが、運悪く探索が行き詰まってしまうと最短手数で最適解に辿り着けなくなるだけでなく、極大値などが存在すると真のゴールに辿り着くことができなくなってしまいます。

・反復深化深さ優先探索
反復深化深さ優先探索ですが、深さ優先探索ではメモリの消費量は少ないのですが、最初に見つかる解が最短手数になるとは限りません。そこで、深さ優先探索の「深さ」に上限値を設定して、解が見つかるまで上限値を段階的に増やしていこうとする手法です。ただ、お分かりのように同じ探索を何度も繰り返すことになるため計算時間が増大します。そのため、枝刈りによって下限値を上手く設定することでパズルを高速に解く必要性があります。

・A*探索
A*探索ですが、深さ優先探索では局所的な局面状態の中から評価値の高い状態を選んで次の探索を進めますが、スタートから現在地点までのコストは考慮していません。そこで、A*探索では、現在地点に到達するまでのコストと、そこからゴールまでに推定されるコストに基づいて次の局面状態を選択しようとする手法です。詳細な証明は割愛しますが、この時にある条件を満たしていると、最初に見つけた解が最適解になります。おそらく今まで説明してきた探索アルゴリズムの中で一番良い手法だと言えます。

・双方向A*探索
双方向A*探索ですが、幅優先探索と同じようにA*探索でもスタートとゴールの双方から探索する手法が適用できます。これにより高速化も実現できます。

■隣接行列と隣接リスト
隣接行列や隣接リストは、あるマスが次にどのマスに移動可能であるかを示した行列やリストです。隣接リストの方が消費するメモリが少ないのですが、今回は隣接行列を用いて、5×5のパズルにまで対応できるようにしています。本来なら前の局面状態から次に移動できるマスが分かると思うので、おそらくスマートな手法ではないと思いますが…

ヒューリスティック関数
深さ優先探索などで用いる評価値についてですが、最も有名なマンハッタン距離(全部のマスの最低限必要な手数の合計値)を評価値として利用することにしました。他にも下限値枝刈り法に利用できる評価値として転倒距離があります。まず転倒数と呼ばれる数字の並び順が逆になっている数を数えて、それを用いて最低限必要な上下動回数と最低限必要な左右動回数を計算します。それらの値を足し合わせたものが転倒距離になります。最終的にマンハッタン距離と転倒距離を比べてより厳しい方の値(大きい値)を下限値として採用するようにします。

■下限値枝刈り法
必要となる最低限の手数が明確に分かっている場合には、この手法は探索の計算時間に非常に大きな影響を与えます。パズルを解くのに最低限必要な手数を求めて、これを下限値として利用することにしました。1回に1つのパネルしか移動しないので、初期状態の下限値を求めておいて、動かしたパネルの差分だけ計算して下限値を更新するようにしています。

■その他
他にも、自作のハッシュ関数だったり、手数制限だったり、工夫していることはいくつかあったと思うのですが、思い出すのと説明するのがメンドイので気になる人はソースコードを見て下さい。

ソースコード
解答コードはgithubに公開してあります。
PythonのようなLL言語でも良かったのですが、今回は実行速度と省メモリの観点から開発言語はC++を選びました。
https://github.com/Goto-youthK/search_algorithm/tree/master/devquiz_2011/slide_puzzle

ファイル名と探索アルゴリズムの対応は以下のようになっています。

コードの解説は中にコメントとして記してあるので、それを参考にして下さい。

■参考にしたページ
ホームページ移転のお知らせ - Yahoo!ジオシティーズ
15パズル自動解答プログラムの作り方
blog.k11i.biz: GDD2011 DevQuiz のスライドパズルに挑戦してみました
DevQuiz 2011 - Coding Memorandum

今年はなぜかGDD2012はなかったのですが、来年はあるといいですね。
次はもう少し高得点を狙えるように頑張りたいです!!!

ドラえもん生誕100年前記念 〜現在と未来のひみつ道具の比較〜(後編)

ようやくこのタイトルでの話も後編を迎えることになりました。
今回は最後の11個について紹介していきます。

エスパーキャップ
・現在のエスパーキャップ(脳コントローラー)
ユーザーの脳波を読み取るヘッドセット。
現時点で既に念じるだけで、仮想物質を動かすことができる。

出典:www33.atwiki.jp
・100年後のエスパーキャップ
頭の上に乗せると、念力・瞬間移動・透視の3つの超能力が出せるようになる帽子。
■アンキパン
・現在のアンキパン(CREB遺伝子)
CREBとは記憶力を決定する遺伝子の一つ。
この遺伝子の働きを高めた遺伝子操作マウスは記憶能力が著しく向上した。

出典:www33.atwiki.jp
・100年後のアンキパン
暗記力を上げるパン。
パンに暗記したいものを写して食べればスラスラ覚えられる。
■強力においついせき鼻
・現在の強力においついせき鼻(バイオハイブリッドデバイス)
匂いを嗅ぎ分けることができるロボット。
匂い物質の検出には、蛾の触覚にあるフェロモン受容体を利用している。

出典:www33.atwiki.jp
・100年後の強力においついせき鼻
鼻に付けると、どんな些細な臭いも分かる高性能付け鼻。
その性能には車に乗った人の臭いまでも辿れるほど。
■コンク・フード
・現在のコンク・フード(爆破レンジ)
音波を超える衝撃波で食材を一瞬にして粉砕したり、柔らかくする装置。
外見の形を保ったまま中身だけ柔らかくする。

出典:www33.atwiki.jp
・100年後のコンク・フード
いろいろな食べ物が、半練り状態で入っている。
中身が濃いため1缶で30食分になる。海の中でも食べられる。
■エラチューブ
http://japanese.engadget.com/2006/01/31/artificial-gills/ ・現在のエラチューブ(人工エラ)
魚のように水中に溶存する酸素を取り込むことで、水の中での活動の幅を広げる人工エラシステム。

出典:www33.atwiki.jp
・100年後のエラチューブ
鼻に詰めると水中でも呼吸ができる。
くしゃみ防止ベルトと吸引ファンが付いている。
■ひらりマント
http://www.toyota.co.jp/jpn/tech/safety/technology/pre_crash/ ・現在のひらりマント(プリクラッシュセーフティシステム)
事前に衝突を予知し、衝突に対し身構えることによって、被害を軽減する技術。

出典:www33.atwiki.jp
・100年後のひらりマント
突進してきたものに、マントを向けるだけで方向転換させることができるマント。
ジャイアンの攻撃もかわせる。
■お天気ボックス
・現在のお天気ボックス(SNO-LA)
場所や天気を問わず、望み通りのタイミングで雪を降らすことができるスノーマシン。
必要なのは角氷と発電機のみ。

出典:www33.atwiki.jp
・100年後のお天気ボックス
自分の希望する天気のカードをボックスに入れると、必ず望み通りの天気になる。
遠足の時にも役に立つ。
コピーロボット
・現在のコピーロボット(Geminoid F)
世界一人間に似ているロボットとしてギネス認定されているアンドロイド。
操作する人の表情や動きも再現できる。

出典:www33.atwiki.jp
・100年後のコピーロボット
鼻を押すと、押した人そっくりに変わるロボット。
性格まで同じになる。
パーマンも使っている。
■お医しゃカバン
http://livelove.co.jp/yakuji-syorui/genri.html ・現在のお医しゃカバン(アラ!元気)
唾液で体調チェックができる診断装置。
綿棒をなめて、装置にセットするだけ。
およそ1分で結果が分かる。

出典:www33.atwiki.jp
・100年後のお医しゃカバン
どんな病気でもお医者さんのようにピタリと当てるカバン。
仮病も見破られてしまう。
■空気クレヨン
・現在の空気クレヨン(3Dモーションタグ)
AR技術を用いて空中に3Dグラフィティアートを描く。
描く人の動きを記録し、仮想空間で再描画する。

出典:www33.atwiki.jp
・100年後の空気クレヨン
空中に落書きができるクレヨン。
描いたものは、生きもののように動き始める。
■バタバタフライ
・現在のバタバタフライ(ウイングスーツ)
空を飛ぶことができる特殊ジャンプスーツ。
対地落下速度は50〜100km/h、水平平均飛行速度は最大250km/h以上。

出典:www33.atwiki.jp
・100年後のバタバタフライ
背中に付けると、チョウのように自由に空を飛び回ることができる羽。
両手をバタバタ動かすと羽が動く。

今までこうやってブログを書いてて思ったのですが、現在の最先端の科学技術でもかなりのところまで進歩してきているのは驚きでしたね。「みらいサーチ」という一見変わったサービスでこれからの技術の発達を感じさせてくれたGoogle先生にも感謝です。しかし、だからといって、人間がこのような便利な道具に頼りきってはいけないというのも事実で、それはのび太を見ていれば明らかな事でしょう。

もしかしたら、ドラえもんは、「科学技術が発達した現代においても、道具を使うのは人間であり、人間側が成長しなければどれだけ科学技術が発達しても問題は解決しない」というメッセージを100年以上も前から我々に伝えたかったのかもしれないですね。~~~-y(-。-)。oO○(キマった)

何となくいい話っぽくなってきた感じなので、そろそろひみつ道具紹介の方を終わりにしたいと思います。

次にブログを書くのはいつのことになるのでしょうか…(汗)

ドラえもん生誕100年前記念 〜現在と未来のひみつ道具の比較〜(中編)

前編では、33個あるひみつ道具のうち、最初の11個について紹介してきました。その時には見つけたひみつ道具をマイポケットにしまってコレクションできるとお話しましたが、実はひみつ道具を10個集めると特別なアイテム「ほんやくコンニャク」が貰えます。

この使い方は、翻訳したい言葉を入力して画面にあるほんやくコンニャクをタップするだけです。本当に翻訳してくれるので、実際の翻訳ツールとしても使えるようになっています。

それでは今回も引き続いてひみつ道具を紹介していきます。

■あっちこっちテレビ
・現在のあっちこっちテレビ(Google+ Hangouts)
10人まで同時に参加できるビデオチャット
世界中に内容をリアルタイム配信できるストリーミング機能搭載。

出典:www33.atwiki.jp
・100年後のあっちこっちテレビ
4つのカメラを使用し、同時に4つの画面で映像を映し出して見ることができる。
探し物にも便利。
■真水ストロー
・現在の真水ストロー(ライフストロー)
個人用水洗浄器。
汚れた水を吸い込むと、ろ過されて安全な飲み水になる。
15ミクロンもの小さな粒子をも取り除く。

出典:www33.atwiki.jp
・100年後の真水ストロー
海水を通すだけで真水になるストロー。
無人島で生活をする時にも役立つ。
■折りたたみハウス
・現在の折りたたみハウス(グローバルヴィレッジシェルター)
耐水・耐火加工された紙製のシェルター。
組み立てに部品は必要なく、約15分で組み立てできる。

出典:www33.atwiki.jp
・100年後の折りたたみハウス
好きな家や行きたい家の絵をかけば、すぐその場所に変わる壁紙。
見た目によらず室内は広い。
■とおりぬけフープ
http://www.jst.go.jp/kisoken/seika/zensen/09furusawa/index.html ・現在のとおりぬけフープ(量子テレポーテーション)
ある地点の粒子の状態に関する情報を量子力学特有の性質を利用して別の地点の粒子に瞬間的に移すこと。

出典:www33.atwiki.jp
・100年後のとおりぬけフープ
通り抜けたい所に当てると通り穴ができるフープ。
どんな扉や壁でも反対側へ抜けられるようになる。
■ラジコン粘土
・現在のラジコン粘土(シンキングパティ)
伸びたり、ちぎったり、弾ませることも出来るオフィス・トイ。
ミクロの鉄粒子入りで、磁石で操ることもできる。

出典:www33.atwiki.jp
・100年後のラジコン粘土
作ったものが、ラジコン操作で自由に動かせるようになる粘土。
専用の操縦機で操る。
■念写カメラ
・現在の念写カメラ(視覚経験の再現)
人が見ている映像を脳活動を元に復元するシステム。
実用化すれば夢を映像で再現できるかもしれない。

出典:www.miraisearch.jp
・100年後の念写カメラ
カメラを額に当てながら撮ると、頭の中で考えたことが写真になって出てくるカメラ。
■おすそわけガム
・現在のおすそわけガム(タグキャンディ)
音と振動を用いて食感を変えられるキャンディ。
様々な食感を一つのキャンディで味わえる。

出典:www.miraisearch.jp
・100年後のおすそわけガム
分け合って食べると、分けた人の食べた物の味が伝わってくるガム。
■XYZ線カメラ
・現在のXYZ線カメラ(ミューオグラフィー)
ミュー粒子を用いて地球内部を可視化する透視装置。
エジプトのピラミッド内部を透視する計画も進行中。

出典:www.miraisearch.jp
・100年後のXYZ線カメラ
包まれているものの中身を写して確認できるカメラ。
標準レンズ、望遠レンズ、接近レンズを完備。
■ハッスルねじ巻き
・現在のハッスルねじ巻き(ターボスピードスーツ)
最大0.023秒タイム短縮できるトラックスーツ。
ゴルフボールの表面形状を参考に空気抵抗を減らしている。

出典:www.miraisearch.jp
・100年後のハッスルねじ巻き
背中に当ててネジを巻くと、全ての動作が早くなるネジ巻き。
走ると新幹線と同じ速さになる。
■マリオネッター
・現在のマリオネッター(ウェアラブル行動誘導システム)
ARつきヘルメットを作業員が装着すれば、遠隔地にいる専門家(手袋を装着)が直接指示を送れるシステム。

出典:www.miraisearch.jp
・100年後のマリオネッター
人形を操るように、人を自在に操ることができる機械。
操作が下手だと、思い通りに動いてくれない。
■ジャック豆
・現在のジャック豆(完全人工光型植物工場)
LED、レーザー光を利用した植物栽培方法。
通常の方法で育てる農作物より早く育つ、甘いなどの成果が得られている。

出典:www.miraisearch.jp
・100年後のジャック豆
土に埋めると、あっという間に大きな木になる豆。
ビル火事などの時には緊急避難のはしご代わりになって便利。

さてさて、こんな便利な道具を持っているドラえもんですが、今から100年後の2112年の9月3日に誕生するのは周知の通りですが、製造された場所が「トーキョーマツシバロボット工場」である事はご存知でしょうか?明らかに松下と東芝をくっつけただけのネーミングですね…(^_^;)

それでは後編に続きます。

ドラえもん生誕100年前記念 〜現在と未来のひみつ道具の比較〜(前編)

ミクの5歳の誕生日の歓喜の余韻が冷め止まぬ内にドラえもんの−100歳の誕生日がやってきました。Googleでは、ドラえもんの生誕100年前を記念して、みらいサーチ(http://www.miraisearch.jp)というスマートフォン向けの面白そうなサービスを公開したようです。

同時に、みらいサーチのCMも2012年9月3日からYouTubeでも公開されていますね。因みに、このサービスはあくまでスマートフォン向けであることに注意して下さい。


これはスマートフォンの音声検索を使って「ドラえも〜ん」と呼びかけると、検索結果の上に「ひみつ道具」へのリンクが表示されるものです。自分が試してみたところでは、音声ではなく文字の入力による検索でも同じように動きますし、「ドラえもん」「どらえもん」「ドラえもーん」「ドラえも〜ん」などの多少の文字の違いがあっても問題ないようでした。

次に、表示されたひみつ道具をクリックすると、現在と未来のひみつ道具をそれぞれ紹介してくれます。それをマイポケットに入れれば集めたことになります。これを全部で33個あるひみつ道具分だけやれば終了です。

しかし、それでは大変なので、今回は前編、中編、後編の3つに分けて、まずは最初の11個を紹介したいと思います。

タケコプター
・現在のタケコプター(GEN H-4)
同軸二重反転ローター搭載の小型有人ヘリコプター。
コントロールバーで左右前後に移動、その場で旋回もできる。

出典:www.tv-asahi.co.jp
・100年後のタケコプター
気軽に空を飛ぶことができる道具。
連続8時間以上使うと、電池切れを起こしてしまう。
■とうめいマント
・現在のとうめいマント(再帰性投影マント)
光を照らした方向にはね返す布。
周りの風景をマントに映して身にまとえば、透明人間のように見える。

出典:www33.atwiki.jp
・100年後のとうめいマント
かぶると透明になるマント。
ジャイアンは、とうめいマントと騙されて、ビニール風呂敷を渡されたことがある。
■スーパー手ぶくろ
・現在のスーパー手ぶくろ(パワーエフェクタ)
人間のパワーを増幅する機械。
指にはめるとパワーが100倍になる。
最大握力は約200kg。

出典:www.drillspin.com
・100年後のスーパー手ぶくろ
手にはめると怪力の持ち主になれる手袋。
この手袋をはめれば、大木も軽々と持ち上げることができる。
バイバイン
・現在のバイバイン(榎本藻)
通常の1000倍の速さで増殖する藻。
藻類の中で燃料生産能力が最も高く、1ヶ月間培養で4000個に増える。

出典:iphone.appinfo.jp
・100年後のバイバイン
一滴たらすと、5分で2倍、また5分経つと、そのまた2倍にと、どんどん増えていく藻。
■デンデンハウス

出典:http://www.n55.dk/manuals/snail_shell_system/sss.html
・現在のデンデンハウス(スネイルシェルシステム)
水陸両用のシェルター。
ポリエチレン性。
シャワーやトイレ、発電機などのオプションが付いている。

出典:www.tv-asahi.co.jp
・100年後のデンデンハウス
一度入ると外からの衝撃を一切受けなくなる、快適な住まい。
エアコン完備。
■地球セット
・現在の地球セット(Google Earth)
自由自在に地球を探索できる3D地球儀。
3Dの地形、建物を見るだけでなく、名所・地域のお店やサービスの検索もできる。

出典:www33.atwiki.jp
・100年後の地球セット
宇宙台紙の上に、小さな地球が製造できるセット。
台風、カミナリ、オーロラなどをつくれる特殊ガスもある。
■トレーサーバッジ
・現在のトレーサーバッジ(Google Latitude)
お互いの現在地を共有できる位置情報サービス。
近くにいる友達の場所を地図上で確認できる。

出典:ameblo.jp
・100年後のトレーサーバッジ
バッジを付けていると、その人のいる場所が「レーダー地図」に示される。
■グルメテーブルかけ
・現在のグルメテーブルかけ(メタクッキー)
見た目と匂いを変化させることによって、体験者が食べた時に感じる味が変化するARクッキー。

出典:www33.atwiki.jp
・100年後のグルメテーブルかけ
食べたいものを口にするだけで、何でも出てくるテーブルかけ。
味も確かでのび太のパパも大絶賛。
■テキオー灯
・現在のテキオー灯(ファイヤーレジスタントスーツ)
12秒間1100度の炎の中にいても、やけどを追わないスーツ。
特殊な燃えないファイバーを使用している。

出典:htks.tk
・100年後のテキオー灯
どんな状況下の星でも生活できるようになる光線が出る。
ただし、効果は24時間で失われる。
■おおかみ男クリーム
・現在のおおかみ男クリーム(猫かぶる)
人の動きに連動して目と口が動かせる着ぐるみ。
赤外線センサーで動きを読み取り、それに合わせて着ぐるみを動かす。

出典:www33.atwiki.jp
・100年後のおおかみ男クリーム
狼男になるクリーム。
顔に塗って月のように丸いものを見ることで、効果が現れる。
■どこでもドア

出典:ストリートビューの概要と Google マップへの投稿方法について
・現在のどこでもドア(Googleマップストリートビュー)
地図上で自分の好きな場所を探すと、世界中のどこでもその街並みを360度のパノラマ写真で見て楽しむことができる。

出典:www.tv-asahi.co.jp
・100年後のどこでもドア
行きたい場所を声に出し開くだけで、どこにでも行くことができるドア。
ドラミのどこでもドアは模様が付いている。

このみらいサーチは2012年10月5日まで実施しているようなので、皆さんもぜひ色々なひみつ道具を集めてみてはどうですか?

それでは中編に続きます。

FOBOSを実装してみた(理論編)

■概要
利用可能な言語資源(Wikipedia, GSK Corpus, Google N-gram Corpusなど)が急激に拡大してきており、これに伴ってより多くの言語データを扱えるようになったことで統計的機械翻訳の翻訳精度は急激に上昇してきています。一方で,大量に保存されてきた言語資源を利用するデータマイニングなどで機械学習と呼ばれる技術が扱われるようになってきました。このような分野において、シンプルな線形識別モデルと凸最適化を組み合わせたオンライン学習により、大量のデータを利用した高速な学習と識別が可能になることが分かり、近年になって注目されるようになってきました。
ここでは、オンライン凸最適化アルゴリズムとして有名なFOBOSについて説明していきたいと思います。

■はじめに
そもそもこのブログを書こうと思ったきっかけは、大学の講義で

「オンライン凸最適化アルゴリズムの最近の手法(FOBOSやPegasos)の概要をまとめよ」

とレポート課題が出されたことがきっかけで、実装が簡単な割に高速で性能が良いことで有名だったFOBOSについてちょうど知っておきたかったこともあって、今回実装してまとめてみることにしました。
(ちなみに、提出期限は去年の年末で、提出してすぐにブログに書きたかったのですが、今まで更新をサボっており、今に至っているという訳です…)

具体的な説明に入る前に、FOBOSを知るために必要な構成要素についてまとめると、この手法を特徴付けるキーワードとして以下の4つが挙げられると思います。

  • オンライン学習
  • 凸関数
  • 劣勾配法
  • 正則化

少し細かい分類になってしまったかもしれませんが、今後の説明のためにそれぞれについてもう少し詳しく説明しておきます。

オンライン学習とバッチ学習
まず、オンライン学習とバッチ学習の違いについてですが、自分の中の定義では以下のようになっています。

・バッチ学習
  訓練データを全部読み込んでから重みパラメータを更新する、という処理を繰り返す手法のこと
・オンライン学習
  各訓練データ毎に重みパラメータを逐次更新する、という処理を繰り返す手法のこと

もちろん両方において長所と短所があります。
バッチ学習は、オンライン学習に比べて汎化性能は良いですが、欠点として蓄積した大量の訓練データを扱う必要があるため、処理が重く、使用するメモリ量も多くなります。また、オンライン学習は、先程も述べたように実装が簡単な場合が多く、訓練データを蓄積する必要がないので大量のメモリを必要とせず、新しいデータを入手した時にも再学習が容易になります。しかし、学習率を適切に設定しないと重みパラメータ収束が不安定になったり、訓練データの順番に偏りがあった場合に精度が不安定になります。

凸関数の性質
近年(?)になって、最適化問題を凸計画問題(convex programming problem)で表すことで比較的簡単に最適解を求められるということで注目が集まっていますが、それは凸計画問題の中で扱われる下に凸な凸関数(convex function)が以下のような性質を持っているからだと言えます。

  • 凸関数の線形和は凸関数になる
  • アフィン合成後の関数も凸関数になる
  • 凸関数の最大値は凸関数になる
  • 1次条件が成立する

\hspace{50}f(\cdot)が凸 \Leftrightarrow f({\bf y}) \geq f({\bf x}) + \nabla f({\bf x})^{T}({\bf y} - {\bf x)\forall {\bf x}, {\bf y}

  • 2次条件が成立する(ヘシアンが正定値)
  • 微分して勾配0になる局所最適解(停留点)は大域的最適解になる(SVMなどの目的関数の場合)

例えば、FOBOSでは最適化の目的関数として損失項(後述)と正則化項(後述)の和を最小化していく必要があるのですが、それらの両方が共に凸関数であれば、上述の性質により目的関数も凸関数になります。
このようにして凸関数は次に示す(劣)勾配法と組み合わせることによって最適解を求めることができます。

微分と劣勾配法
例えば、SVMの損失項として用いられるHinge-Lossの極値を求める場合、閉じた形で解を求めることができません。そこで、データから勾配を計算して次第に極値へと近づけていくこと(勾配法)を考えます。しかし、勾配法では目的関数が微分可能であるという前提条件があり、微分不可能な点では勾配は計算できないので、勾配法は使えません。そこで、劣微分や劣勾配法の考え方が必要になってきます。

・劣微分の定義
まず、凸関数の1次条件
\hspace{50}f({\bf x}) \geq f({\bf x}_{0}) + \nabla f({\bf x}_{0})^{T}({\bf x} - {\bf x}_{0})
を元に劣微分の定義を考えると、ある凸関数f{\bf x}における劣微分(subdifferential)は、以下のように表されます。
\hspace{50}f({\bf x}) \geq f({\bf x}_{0}) + {\bf g}({\bf x}_{0})^{T}({\bf x} - {\bf x}_{0})
ここで、{\bf g}はある凸関数f{\bf x}における劣勾配(subgradient)であり、上式を満たす{\bf g}は関数f{\bf x}における劣勾配になります。(ちなみに、微分可能な点における劣微分の値は1つに定まり、その値は微分の値と一致します。)

・劣勾配法
重みパラメータを更新するためのオンライン学習アルゴリズムの例として確率的勾配降下法(Stochastic Gradient Descent:SGD)が挙げられますが、通常のSGDでは微分不可能な点があると最適化できないので、劣微分を使った劣勾配法で最適化を行う必要があります。劣勾配法は、微分不可能な場合でも勾配を定義しようとするもの(何か擬似逆行列と似てますね…)で、微分不可能な点がない場合にはSGDと同じであることから、使える適用範囲が広い手法と言えます。

過学習正則化
最後に、過学習正則化の定義について説明しておきます。
一般的に、自然言語処理では過学習が問題になることはないようですが、重みパラメータの次元数が膨大になります。そのため、正則化によりスパース(Sparse)な解にすることで、重みパラメータを保持するメモリ量が少なくなり、高速な計算も可能になります。

過学習
  訓練データに過剰に適合してしまい、訓練データは分類できる(経験損失は小さくできる)が、未知のテストデータは分類できなくなってしまう(期待損失は大きくなってしまう)状態のこと
正則化
  学習モデルの複雑さに対してペナルティを与えること
  よく使われる正則化にはL1正則化(L1-norm)とL2正則化(L2-norm)があり、L0正則化(L0-norm)などもある。(数字が小さいほど重みパラメータベクトルの非0要素を減らそうとする力が働くが、最適化が困難になる。)

■従来のオンライン学習アルゴリズム
先程説明した微分不可能な点で効果のある劣勾配法ですが、損失項にL1正則化項を導入することで最適解では多くの重みパラメータが0になるはずですが、劣勾配法ではスパースな解が得られません。この現象は微分不可能な点で起こることが多く、さらに微分不可能な点が最適解であることが多いため、何とかしてL1正則化と劣勾配法を上手く組み合わせて最適解を求めることが必要になります。このような欠点を克服した手法としてFOBOSなどの手法が挙げられます。だいたいの話の流れは分かったでしょうか?

■FOBOS
まず、今回紹介しているFOBOSの論文についてですが、
http://jmlr.csail.mit.edu/papers/v10/duchi09a.html
で見ることができます。ただ、この論文はジャーナルで長いので2009年のNIPSに投稿された
http://www.cs.berkeley.edu/~jduchi/projects/DuchiSi09_folos.html
もあります。

FOBOSの特徴として、例えば目的関数J({\bf w}) = f({\bf w}) + r({\bf w})の損失項f({\bf w})(間違いに対して与えるペナルティ)と正則化r({\bf w})(過学習という状態に対して与えるペナルティ)について

とした時に、J({\bf w})を最小にする{\bf w}を確率的勾配法(SGD)で求めるという点で劣勾配法に似たオンライン学習アルゴリズムです。しかし、劣勾配法では損失項と正則化項の両方の勾配をまとめて計算していましたが、FOBOSでは最初に劣勾配法で重みパラメータを更新しながら損失項f({\bf w})のみを最小化し、次に更新した重みパラメータをなるべく動かさずに正則化r({\bf w})を最小化する{\bf w}を求めるようにして、重みパラメータの更新を2ステップに分けている点が従来の手法と異なります。

まず、損失項部分の処理に関しては、f({\bf x)の劣勾配を計算して最小になる方向に進みます。
次に、正則化項部分の処理に関しては、Proximal勾配法(Proximal作用素とかProximal最小化とか出てくるのですが、逐次最適化を行う方法のようです。これ以上詳しいことは知りません…)の式変形により正則化項を閉形式(closed-form)の重みパラメータ更新式に変形して最適な解を計算しています。ここでは、L1正則化とL2正則化の場合についてだけ示します。他にも論文では、L1正則化とL2正則化のハイブリッドであるBerhu正則化(0に近い部分ではL1正則化の影響でスパースな解が得られ、値が大きい部分ではL2正則化の影響で極端に大きな値はなくなります。)についても紹介しているのですが、今回は省略しますm(_ _)m

・L1正則化の場合
\hspace{50}{\bf v} = {\bf w}_{t} - \eta \nabla f({\bf w})
\hspace{50}{\bf w}_{t+1} = {\rm argmin}_{w} \left( \frac{1}{2} ||{\bf x} - {\bf v}||^{2} + \lambda ||{\bf w}||_{1}\right)
・L2正則化の場合
\hspace{50}{\bf v} = {\bf w}_{t} - \eta \nabla f({\bf w})
\hspace{100}r({\bf w}) = \frac{\lambda}{2} ||{\bf w}||^{2}_{2},勾配降下,幾何減少
\hspace{100}{\bf w}_{t+1} = \frac{{\bf v}}{1 + \lambda \eta}

\hspace{100}r({\bf w}) = \lambda ||{\bf w}||_{2},更新 有/無
\hspace{100}{\bf w}_{t+1} = \left( 1 - \frac{\lambda \eta}{||{\bf v}||_{2}} \right)_{+}{\bf v}

ここで、\eta\lambdaは学習率のことで、{\bf v}は勾配方向に少しだけ{\bf w}_{t}を進めたものになります。例えばL1正則化では、{\bf w}_{t+1}を求める場合の目的関数の値は非負の数の和であり、それぞれの項は独立しています。また、Proximal勾配法の式変形により重みパラメータ更新式を閉形式にしたことで、勾配法などでラグランジュの未定乗数法を使って重みパラメータ更新式の最適値を計算できるようになります。

このように微分不可能な問題を解析的に解ける2つの最小化問題に分離してそれぞれの項に関して最適値を計算すれば、それが{\bf w}に関しての最適解になるという訳です。


次の「FOBOSを実装してみた(実装編)」はもう少しお待ち下さい…(汗)

■おわりに
ブログを書いた後に見つけたのですが、この解説スライドがとても分かりやすいと思いました。

Sony GO FOR IT 5) 申告制エレベータ

就活のためエントリーしていたSonyから

「コードで世界を変えたいと思う方、現実の難しい課題をプログラミングによって解くことが好きな方向けに『GO FOR IT -コードで世界は変えられる-』を開催します。」

と題して以下のサイトでイベントを行なっているというメールで連絡が来てたので、特にプログラミング能力に自信があるという訳ではないですが、5番目の問題を解いてコンテストに応募してみる事にしました。

http://www.sony.co.jp/SonyInfo/Jobs/newgrads/sus/go_for_it.html

なお、このコンテストは2013新卒採用選考とは関係ないようです…

■5) 申告制エレベータ
実際の問題内容は以下をご覧下さい。
http://www.sony.co.jp/SonyInfo/Jobs/newgrads/sus/q05.html


問題i)

エレベータを1台、最大乗車人数を1人とします。
単純に入力データの識別番号順に、利用者を運ぶプログラムを作成してください。

回答i)

これを実現するためのアルゴリズムは以下のような規則に基づいています。

  • 初期値は(1,0,1,E,0,0,0,0,0)である。
  • B(開)とE(閉)は交互に起きる。
  • 降車させた階数に利用者がいれば乗車させる。
  • 以下の4つのパターンのどれかの繰り返しで成り立っている
    • Eで利用者が乗車したらBでその人は降車する(時刻:+2*移動階数)
    • Eで利用者が乗車しなかったらBで利用者は降車しない(時刻:いろいろと複雑になる)
    • Bで利用者が降車したらEでエレベータの扉を閉める(時刻:+5秒もしくは希望乗車時刻まで待つ)
    • Bで利用者が降車しなかったらEでエレベータの扉を閉める(時刻:+5秒もしくは希望乗車時刻まで待つ)
#include <cstdio>
#include <cstdlib>

const int MAX_N = 10;           // 利用者数
const int MOVE = 2;             // 移動時間

// 入力
int In1[MAX_N + 1];        // 入力データの識別番号
int In2[MAX_N + 1];        // 申告者の乗車希望時刻(開始してからの経過秒数)
int In3[MAX_N + 1];        // 申告者が乗車する階
int In4[MAX_N + 1];        // 申告者が降車する階

// 出力
int Out1 = 1;            // エレベータの識別番号(1)
int Out2 = 0;            // エレベータの動作時刻(開始してからの経過秒数)
int Out3 = 1;            // エレベータが動作した階
char Out4 = 'E';         // エレベータの動作
int Out5 = 0;            // 入力データの識別番号1
int Out6 = 0;            // 入力データの識別番号2
int Out7 = 0;            // 入力データの識別番号3
int Out8 = 0;            // 入力データの識別番号4
int Out9 = 0;            // 入力データの識別番号5

int main() {
    FILE *fin, *fout;
    fin = fopen("input_i.txt", "r");
    fout = fopen("output_i.txt", "w");

    // ファイル入力より入力
    for(int i = 0; i < MAX_N; i++)
        fscanf(fin, "%d,%d,%d,%d\n", &In1[i], &In2[i], &In3[i], &In4[i]);

//     for(int i = 0; i < MAX_N; i++)
//         printf("%d %d %d %d\n", In1[i], In2[i], In3[i], In4[i]);

    int t = 0, c = 0;

    while(1) {
        // 開くと閉じるを交互に行う
        if(Out4 == 'B') {
            Out3 = Out3;
            Out4 = 'E';

            if(Out5 == 0) {
                if(c != 0) t++;
                else c++;

                if(t > MAX_N - 1) break;

                if(Out2 + 5 > In2[t])
                    Out2 += 5;  // 閉時間
                else
                    Out2 = In2[t]; // 次の希望乗車時刻

                Out5 = In1[t];
            }
            else {
                if(In3[t + 1] == Out3) {
                    if(c != 0) t++;
                    else c++;

                    if(t > MAX_N -1) break;

                    if(Out2 + 5 > In2[t])
                        Out2 += 5; // 閉時間
                    else
                        Out2 = In2[t]; // 次の希望乗車時刻

                    Out5 = In1[t];
                }
                else {
                    Out2 += 5;
                    Out5 = 0;
                }
            }
        }
        else if(Out4 == 'E') {
            Out4 = 'B';
            Out5 = Out5;

            if(Out5 == 0) {
                if(t == 0 && c == 0) {
                    if(In3[t] == 1) {
                        if(In2[t] > 5) {
                            Out2 = In2[t] - 5;
                            Out3 = In3[t];
                        }
                        else {
                            Out2 = 0;
                            Out3 = In3[t];
                        }
                    }
                    else {
                        if(MOVE * (In3[t] - 1) > In2[t] - 5) {
                            Out2 = MOVE * (In3[t] - 1);
                            Out3 = In3[t];
                        }
                        else {
                            Out2 = In2[t] - 5;
                            Out3 = In3[t];
                        }
                    }
                }
                else{
                    Out2 += MOVE * abs(In3[t + 1] - In4[t]);
                    Out3 = In3[t + 1];
                }
            }
            else {
                Out2 += MOVE * abs(In4[t] - In3[t]);
                Out3 = In4[t];
            }
        }

        Out1 = Out1;

        // 出力
        printf("%d,%d,%d,%c,%d,%d,%d,%d,%d\n", Out1, Out2, Out3, Out4, Out5, Out6, Out7, Out8, Out9);
        fprintf(fout, "%d,%d,%d,%c,%d,%d,%d,%d,%d\n", Out1, Out2, Out3, Out4, Out5, Out6, Out7, Out8, Out9);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}

結果i)
実行すると利用者の乗降履歴とエレベータの動作履歴が出力されます。

$./elevator1
1,221,3,B,0,0,0,0,0
1,226,3,E,1,0,0,0,0
1,228,4,B,1,0,0,0,0
1,233,4,E,0,0,0,0,0
1,237,2,B,0,0,0,0,0
1,263,2,E,2,0,0,0,0
1,265,3,B,2,0,0,0,0
1,270,3,E,0,0,0,0,0
1,274,1,B,0,0,0,0,0
1,282,1,E,3,0,0,0,0
1,296,8,B,3,0,0,0,0
1,301,8,E,0,0,0,0,0
1,307,5,B,0,0,0,0,0
1,466,5,E,4,0,0,0,0
1,470,3,B,4,0,0,0,0
1,475,3,E,0,0,0,0,0
1,489,10,B,0,0,0,0,0
1,499,10,E,5,0,0,0,0
1,507,6,B,5,0,0,0,0
1,512,6,E,0,0,0,0,0
1,514,7,B,0,0,0,0,0
1,544,7,E,6,0,0,0,0
1,556,1,B,6,0,0,0,0
1,593,1,E,7,0,0,0,0
1,611,10,B,7,0,0,0,0
1,663,10,E,8,0,0,0,0
1,679,2,B,8,0,0,0,0
1,684,2,E,0,0,0,0,0
1,686,3,B,0,0,0,0,0
1,691,3,E,9,0,0,0,0
1,695,5,B,9,0,0,0,0
1,700,5,E,0,0,0,0,0
1,702,4,B,0,0,0,0,0
1,803,4,E,10,0,0,0,0
1,813,9,B,10,0,0,0,0
1,818,9,E,0,0,0,0,0
1,836,0,B,0,0,0,0,0


問題ii)

任意の入力データと出力データを読み込み、全ての申告が正しく満たされたこと、前述の動作制約を守ってエレベータが動作していることを確認するプログラムを作成してください。
また、希望乗車時刻から降車時刻までに掛かった全申告の時間を合計して出力してください。
プログラムの入力形式・出力形式は自由とします。

回答ii)

確認する項目をを分かりやすく捉えるために、以下の2つのチェックに分けて行なっています。

  • 全ての申告が正しく満たされているかの確認

入力データを上から走査していき、出力データのOut4がEの場合で識別番号が希望乗車時刻In2以降に申告した階で乗車したかを確認する。次に、それ以降で出力データのOut4がBで該当する識別番号が申告した階で降車したかを確認する。両方を満たした時に限り、Out2-In2を計算して今までの合計に加算していく。

  • 動作制約を守ってエレベータが動作しているかの確認

出力データを上から走査していき、Out4がEからBになっている場合には、現在の動作時刻+2*移動階数と希望乗車時刻との大小関係によりOut2が正しく変更されているかを確認する。また、Out4がBからEになっている場合には、現在の動作時刻+5と希望乗車時刻との大小関係によりOut2が正しく変更されているかを確認する。

この2つのチェック中にどちらかが満たされなくなると、システムがエラーをはくようになっています。
またエラーがない時の最終的な結果は、希望乗車時刻から実際の降車時刻までに掛かった全申告時間を出力するようになっています。

#include <cstdio>
#include <cstdlib>

const int MAX_N = 100;           // 利用者数
const int MAX_H = MAX_N * 4 + 1; // 履歴数
const int MOVE = 2;              // 移動時間

// 入力
int In1[MAX_N + 1];        // 入力データの識別番号
int In2[MAX_N + 1];        // 申告者の乗車希望時刻(開始してからの経過秒数)
int In3[MAX_N + 1];        // 申告者が乗車する階
int In4[MAX_N + 1];        // 申告者が降車する階

// 出力
int Out1[MAX_H];            // エレベータの識別番号(1)
int Out2[MAX_H];            // エレベータの動作時刻(開始してからの経過秒数)
int Out3[MAX_H];            // エレベータが動作した階
char Out4[MAX_H];           // エレベータの動作
int Out5[MAX_H];            // 入力データの識別番号1
int Out6[MAX_H];            // 入力データの識別番号2
int Out7[MAX_H];            // 入力データの識別番号3
int Out8[MAX_H];            // 入力データの識別番号4
int Out9[MAX_H];            // 入力データの識別番号5

int main(int argc, char *argv[]) {
    FILE *fin1, *fin2;

    if(argc != 3) {
        printf("Usage: %s input_file ouput_file\n", argv[0]);
        exit(1);
    }

    if((fin1 = fopen(argv[1], "r")) == NULL) {
        printf("input_i.txt do not exist!\n");
        exit(1);
    }
    if((fin2 = fopen(argv[2], "r")) == NULL) {
        printf("output_i.txt do not exist!\n");
        exit(1);
    }

    // ファイル入力より入力
    int n = 0;
    while(fscanf(fin1, "%d,%d,%d,%d\n", &In1[n], &In2[n], &In3[n], &In4[n]) != EOF) {
        n++;
    }
    int h = 0;
    while(fscanf(fin2, "%d,%d,%d,%c,%d,%d,%d,%d,%d\n", &Out1[h], &Out2[h], &Out3[h], &Out4[h], &Out5[h], &Out6[h], &Out7[h], &Out8[h], &Out9[h]) != EOF) {
        h++;
    }

    //printf("n = %d, h = %d\n", n, h);

    int c1 = 0;
    int sum = 0;
    // 入力データ
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < h; j++) {
            if(Out2[j] >= In2[i] &&
               Out3[j] == In3[i] &&
               Out4[j] == 'E' &&
               (Out5[j] == In1[i] || Out6[j] == In1[i] || Out7[j] == In1[i] || Out8[j] == In1[i] || Out9[j] == In1[i])) {
                for(int k = j + 1; k < h; k++) {
                    if(Out2[k] > Out2[j] &&
                       Out3[k] == In4[i] &&
                       Out4[k] == 'B' &&
                       (Out5[k] == In1[i] || Out6[k] == In1[i] || Out7[k] == In1[i] || Out8[k] == In1[i] || Out9[k] == In1[i])) {
                        c1++;
                        sum += Out2[k] - In2[i];
                    }
                }
            }
        }
    }
    if(c1 != n) {
        printf("user declaration error!\n");
        exit(1);
    }

    int c2 = 0;
    // 出力データ
    for(int i = 0; i < h; i++) {
        if(Out4[i - 1] == 'E') {
            if(i == 0) {
                if(Out2[i] >= 2 * Out3[i] &&
                   Out3[i] <= 10 &&
                   Out4[i] == 'B') {
                    c2++;
                }
                else {
                    printf("elevator's motion restriction error!\n");
                    exit(1);
                }
            }
            else {
                if(Out1[i] == Out1[i - 1] &&
                   Out2[i] == Out2[i - 1] + 2 * abs(Out3[i] - Out3[i - 1]) &&
                   Out3[i] <= 10 &&
                   Out4[i] == 'B') {
                    c2++;
                }
                else {
                    printf("elevator's motion restriction error!\n");
                    exit(1);
                }
            }
        }
        else if(Out4[i - 1] == 'B') {
            if(Out1[i] == Out1[i - 1] &&
               Out2[i] >= Out2[i - 1] + 5 &&
               Out3[i] <= 10 &&
               Out4[i] == 'E') {
                c2++;
            }
            else {
                printf("elevator's motion restriction error!\n");
                exit(1);
            }
        }
    }

    printf("sum = %d\n", sum);

    fclose(fin1);
    fclose(fin2);

    return 0;
}

結果ii)
実行方法は対応関係のある入力ファイルと出力ファイルを続けて入力します。
希望乗車時刻から降車時刻までに掛かった全申告の時間を合計が出力されます。

$./elevator2 input_i.txt output_i.txt
sum = 103 (エラーなし)


問題iii)

エレベータを1台、最大乗車人数を5人とします。
希望乗車時刻から降車時刻までに掛かった全申告の時間の合計ができるだけ小さくなるようなプログラムを作成してください。

回答iii)

おそらく、本来ならA*とかダイクストラ法とかを使って最小解を見つけるのでしょうが、半日考えても問題の当てはめ方が分からなかったので、ここでは愚直な方法で解いてしまっています(汗)
ちゃんとした回答を知りたい人は、同じように問題を解いて回答をアップしてあるブログを参考にするといいと思います…

やってることを簡単に説明すると、基本的に問題ii)のアルゴリズムにエレベータに最大5人まで乗せて利用者を効率的に運べるように改良したもので、時間順にソートした時に同じ階数から乗車する人が連続していれば後ろの人の希望乗車時刻まで待って一緒に乗ってそれぞれ目的の降車階数で降ろすような工夫をしています。

#include <cstdio>
#include <cstdlib>

const int MAX_N = 100;          // 利用者数
const int MOVE = 2;             // 移動時間

// 入力
int In1[MAX_N + 1];        // 入力データの識別番号
int In2[MAX_N + 1];        // 申告者の乗車希望時刻(開始してからの経過秒数)
int In3[MAX_N + 1];        // 申告者が乗車する階
int In4[MAX_N + 1];        // 申告者が降車する階

// 出力
int Out1 = 1;            // エレベータの識別番号(1)
int Out2 = 0;            // エレベータの動作時刻(開始してからの経過秒数)
int Out3 = 1;            // エレベータが動作した階
char Out4 = 'E';         // エレベータの動作
int Out[5] = {0, 0, 0, 0, 0};   // 入力データの識別番号

int main() {
    FILE *fin, *fout;
    fin = fopen("input_i3.txt", "r");
    fout = fopen("output_i3.txt", "w");

    // ファイル入力より入力
    for(int i = 0; i < MAX_N; i++)
        fscanf(fin, "%d,%d,%d,%d\n", &In1[i], &In2[i], &In3[i], &In4[i]);

//     for(int i = 0; i < MAX_N; i++)
//          printf("%d %d %d %d\n", In1[i], In2[i], In3[i], In4[i]);

    int t = 0, c = 0;
    int tt;
    int flg;

    while(1) {
        // 開くと閉じるを交互に行う
        if(Out4 == 'B') {
            Out3 = Out3;
            Out4 = 'E';

            if(flg == 0) {
                int j = 0;
                while(1) {
                    if(c == 0) t = -1;
                    if(In3[t + 1 + j] == Out3) {
                        for(int k = 0; k < 5; k++) {
                            if(Out[k] == 0) {
                                Out[k] = In1[t + 1 + j];
                                break;
                            }
                        }
                        j++;
                    }
                    else {
                        if(c != 0) {
                            t += j;
                        }
                        else {
                            t = 0;
                            c++;
                        }

                        if(Out2 + 5 > In2[t])
                            Out2 += 5; // 閉時間
                        else
                            Out2 = In2[t]; // 次の希望乗車時刻

                        break;
                    }
                }

                if(t > MAX_N - 1) break;
            }
            else {
                for(int k = 0; k < 5; k++) {
                    if(In4[Out[k] - 1] == Out3)
                        Out[k] = 0;
                }

                if(Out[0] == 0 &&
                   Out[1] == 0 &&
                   Out[2] == 0 &&
                   Out[3] == 0 &&
                   Out[4] == 0) {
                    flg = 0;
                }

                if(flg == 0) {
                    int j = 0;
                    while(1) {
                        if(c == 0) t = -1;
                        if(In3[t + 1 + j] == Out3) {
                            for(int k = 0; k < 5; k++) {
                                if(Out[k] == 0) {
                                    Out[k] = In1[t + 1 + j];
                                    break;
                                }
                            }
                            j++;
                        }
                        else {
                            if(j == 0) {
                                Out2 += 5;
                            }
                            else {
                                if(c != 0) {
                                    t += j;
                                }
                                else {
                                    t = 0;
                                    c++;
                                }

                                if(Out2 + 5 > In2[t])
                                    Out2 += 5; // 閉時間
                                else
                                    Out2 = In2[t]; // 次の希望乗車時刻
                            }

                            break;
                        }
                    }

                    if(t > MAX_N - 1) break;
                }
                else {
                    Out2 += 5;
                }
            }
        }
        else if(Out4 == 'E') {
            Out4 = 'B';
            for(int i = 0; i < 5; i++)
                Out[i] = Out[i];

                if(t == 0 && c == 0) {
                    flg = 0;
                    if(In3[t] == 1) {
                        if(In2[t] > 5) {
                            Out2 = In2[t] - 5;
                            Out3 = In3[t];
                        }
                        else {
                            Out2 = 0;
                            Out3 = In3[t];
                        }
                    }
                    else {
                        if(MOVE * (In3[t] - 1) > In2[t] - 5) {
                            Out2 = MOVE * (In3[t] - 1);
                            Out3 = In3[t];
                        }
                        else {
                            Out2 = In2[t] - 5;
                            Out3 = In3[t];
                        }
                    }
                }
                else{
                    if(Out[0] == 0 &&
                       Out[1] == 0 &&
                       Out[2] == 0 &&
                       Out[3] == 0 &&
                       Out[4] == 0) {
                        flg = 0;

                        // 他に目的の移動場所がなければ次の識別番号に移動する
                        Out2 += MOVE * abs(In3[t + 1] - Out3);
                        Out3 = In3[t + 1];
                    }
                    else {
                        flg = 1;

                        // 現在の階数から近い目的階数に移動する
                        int min = 10;
                        for(int i = 0; i < 5; i++) {
                            if(Out[i] != 0) {
                                if(abs(In4[Out[i] - 1] - Out3) < min) {
                                    tt = Out[i] - 1;
                                    min = abs(In4[tt] - Out3);
                                }
                            }
                        }

                        Out2 += MOVE * min;
                        Out3 = In4[tt];
                    }
                }
        }

        Out1 = Out1;

        // 出力
        printf("%d,%d,%d,%c,%d,%d,%d,%d,%d\n", Out1, Out2, Out3, Out4, Out[0], Out[1], Out[2], Out[3], Out[4]);
        fprintf(fout, "%d,%d,%d,%c,%d,%d,%d,%d,%d\n", Out1, Out2, Out3, Out4, Out[0], Out[1], Out[2], Out[3], Out[4]);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}

結果iii)
実行すると利用者の乗降履歴とエレベータの動作履歴が出力されます。

問題iii)の方法で行うと、問題i)の場合と比較して、全申告の合計時間がだいぶ小さくなっている事が分かります。このことから乗車階数の同じ利用者を同時に運ぶことの有効性が見て分かります。
ただし、まだまだ改善できる部分はあり、これが最小の合計時間という訳ではありません。

$./elevator3
長くなるので結果は省略します…

・問題i)の場合の全申告の合計時間
$./elevator2 input_i3.txt output_i1.txt
sum = 71321 (エラーなし)

・問題iii)の場合の全申告の合計時間
$./elevator2 input_i3.txt output_i3.txt
sum = 65193 (エラーなし)


問題iv)

エレベータを2台、 最大乗車人数を5人とします。
希望乗車時刻から降車時刻までに掛かった全申告の時間の合計ができるだけ小さくなるようなプログラムを作成してください。

回答iv)

時間がなくて解けませんでした…(汗)