Não Aqui!

darts-cloneというダブル配列の実装が公開されているのに気づきました．DASTrieで採用しているコンパクトなダブル配列構造を提案されたYata様の作品です．ただ，インタフェースの設計思想はかなり違っていて，DASTrieはstd::mapやstd::setに類似したインタフェース，darts-cloneはDartsに類似したインタフェースになっています．

Web1T unigramでdarts-clone-0.32cをテストしてみると，構築時間が140[sec]くらいで，データベースサイズが223,290,696バイトでした．DASTrieの構築時間（182[sec]）よりも速いので，DASTrieはもう少し高速化の余地がありそうです．DASTrieのデータベースサイズ（131,542,283バイト）よりも大きいのは，HugeDoubleArrayにおける要素サイズが8バイトになっているからだと思います（データベースのサイズ比が0.59で，5/8に近い値になっている）．

また，SVNのバージョン（0.32d）では，構築時間が30[sec]に高速化されています．データベースのサイズが226,293,064バイトに増加していますが，BASE値の検索をやや緩く行う戦略のようです．

このように実装の性能を比較していると，DASTrieの何処を修正すべきなのかはっきりしてくるので，大変有り難いです．ただ，今年度は時間が無さそうなので，更新は来年度に持ち越しになるかもしれません．

デバッグで３時間くらいはまったのでメモ．Python 2.5からSQLiteがデフォルトで使えるようになったので，SQLを使ったデータ処理が楽にできると思っていたが，思わぬ落とし穴が．

こちらのブログに書いてあるように，Pythonのsqlite3はデータを書いたら，必ずcommitメソッドを呼び出す必要がある．そうしないと，せっかく挿入したレコードが消失する恐れがある．Python 2.5のドキュメントには，なぜかclose()メソッドやcommit()メソッドが説明されていないが，2.6以降のドキュメントのclose()メソッドの説明には，

This closes the database connection. Note that this does not automatically call commit(). If you just close your database connection without calling commit() first, your changes will be lost!

とある．この仕様を回避し，自動的にコミットされるようにするには，Connectionオブジェクトのisolation_levelをNoneに設定する．

Pythonみたいな言語は何もしなくても必要な終了処理をしてくれるイメージなので，デフォルトがこういう仕様になっていると，はまる人が続出すると思う．

libLBFGS 1.6をリリースしました．変更点は以下の通りです．

• 今道様より頂いた，backtrackingアルゴリズムにおいて，strong Wolfe conditionを満たすようにステップ幅を決定する実装を取り込みました．これにより，サンプルプログラムにおいてbacktrackingアルゴリズムを使っても，途中でコケることなく，最小化が行えるようになりました（すばらしい！）．なお，この実装を頂いたのは，だいぶ前のことになるのですが，私がサボっていたためにリリースがかなり遅れました．今道さま，どうもありがとうございました．
• OW-LQNを適用する変数の範囲を，lbfgs_parameter_t::orthantwise_start と lbfgs_parameter_t::orthantwise_end で設定できるようにしました（以前はorthantwise_startだけでした）．
• C++のサンプルプログラムが欲しいという人がいるので，配布パッケージに同封しました．C++のクラスの中からlbfgs関数を呼び出すときは，lbfgs関数のinstanceパラメータの使い方，staticメンバ関数を経由したコールバックの実装など，ちょっと経験が必要かも知れませんね．

また忙しい時期に突入していくので，今のうちにソフトウェアをリリースしておかねば…．

libLBFGS 1.5をリリースしました．変更点は以下の通りです．

• OW-LQN法を使うときに，変数の中でノルムの計算に用いるものと，用いないものを区別出来るようにした．具体的には，lbfgs_parameter_t::orthantwise_startというパラメータで変数のインデックス番号を指定できるようにして，このインデックス番号よりも前の変数はL1ノルムの計算から除外し，このインデックス番号以降の変数はL1ノルムの計算に用います．つまり，orthantwise_start = 1ならば，x0はL1ノルムの計算から除外され，x1, …, xNの変数のみでL1ノルムの計算を行うことになります．
• 初期変数がすでに目的関数を最小化しているとき（すなわち勾配が0になっているとき），ゼロ除算などで変なことが発生するので，L-BFGSの反復計算を行う前に，勾配をチェックするようにした．
• LBFGS_SUCCESSという変数を0のシノニムとして定義した．
• void*からのキャストを忘れている箇所を修正した

最初の変更点は，ロジスティック回帰を行うときに，バイアス項は正則化しない方が良いので，追加した機能です．これについては，岡野原氏のブログエントリやBishop本に書かれています．つまり，x0をバイアス項として，orthantwise_start = 1を設定すればOKです．ちなみに，L2正則化に関してはL-BFGSは何も面倒を見ていないので，目的関数や勾配の計算を自由に変えてください．

２番目の変更点は，以前からバグ報告をしていただいている今道様よりご指摘があった問題の修正です．自然言語処理などのアプリケーションではかなり希なケースですが，せっかくminimizerをL-BFGSに入れているのに，正常な動作をしないのはマズいですね．

それ以外の変更点は，かなり軽微です．

あるコードを書いていて，Visual C++ 2008ではコンパイルが通るのに，g++では通らないケースで悩む．Visual C++ 2008はtypenameキーワードまわりが緩く，g++では付け忘れを大量に指摘されるのが常だ．そんなVisual C++ 2008のぬるま湯に浸かっているためか，今日は以下のようなコードがコンパイル出来なくてびっくりした．

template <class T>
class base
{
public:
    T var;
};

template <class T>
class derived : public base<T>
{
public:
    void set(const T& x)
    {
        var = x;    // error: `var' undeclared.
    }
};

int main(int argc, char *argv[])
{
    derived<int> x;
    x.set(2);
    return 0;
}

Visual C++ 2008ではエラー・警告無しだが，g++ 3.4では，”error: `var’ undeclared” というエラーが，派生クラス (derived) の var = x; という箇所で発生する．変数varは基底クラスbaseでpublicメンバとして定義されており，derivedはbaseをpublic継承しているので，deriveクラス内部からvarにアクセスできるのは，当然のはず．それがg++では，認められない．

こういうエラーは検索キーワードを見つけるのが難しいが，ほどなく C++ Template FAQ というページに辿りつく．これによると，テンプレート化されている派生クラスが，同じくテンプレート化されている基底クラスのメンバをアクセスするには，this->var = x; または，base<T>::var = x; みたいにしなければならない．このルールは，メンバ変数，メンバ関数のどちらにも当てはまるらしい．テンプレート化されていなければ，こういうことは起きないし，Visual C++では問題なくコンパイルが通っていたので，ちょっと驚きだった．

C++のコードは，フィーリングで何となく書けているけど，正確なコードを書くのは大変なんだなぁと改めて実感．

Google Search REST API は，利用中止になっていた SOAP Search API を正式に置き換えるもので，外部のウェブアプリケーションから，Google の検索エンジンを利用するためのRESTインタフェースです．上に貼ったリンクの説明が詳しいですが，

• ライセンスキー不要
• クエリ数に関する制限がない
• 以前よりも簡単に使える
• Web検索，イメージ検索，ニュース検索，ビデオ検索，ローカル（地図）検索，ブログ検索，ブック検索が利用可能
• 有効，かつ正確なHTTP Refererヘッダを送信する必要がある
• 一つのAPI呼び出しで，最大8件までしか検索結果を得られない
• 検索結果は最大でも32件までしか得られない．
• 利用規約が厳しい

という特徴があります．サービスの基本的な使い方は，クエリを引数として埋め込んだ検索サービスのURLにアクセスし，返ってくるJSONオブジェクトを解析するというものです．私の名前（Naoaki Okazaki）で検索サービスを呼び出す例です．

面白そうなので，早速Pythonから呼び出すコードを書いてみました．動かすためには，jsonlibをインストールする必要があります．モジュールとしてはsearch関数のみをエクスポーズしています．コマンドラインから動かす場合は，引数をクエリとして，RESTのレスポンスのすべてを表示し，さらに，その中から検索ヒット件数を抜き出しています．

#!/bin/env python

import urllib
import urllib2
import jsonlib  # http://pypi.python.org/pypi/jsonlib/

# CHANGE the referer URL below FOR YOUR OWN.
REFERER = 'http://www.change-this.org/'

BASEURLS = {
    'web': 'http://ajax.googleapis.com/ajax/services/search/web',
    'local': 'http://ajax.googleapis.com/ajax/services/search/local',
    'video': 'http://ajax.googleapis.com/ajax/services/search/video',
    'blog': 'http://ajax.googleapis.com/ajax/services/search/blogs',
    'news': 'http://ajax.googleapis.com/ajax/services/search/news',
    'book': 'http://ajax.googleapis.com/ajax/services/search/books',
    'image': 'http://ajax.googleapis.com/ajax/services/search/images',
}

def search(query, referer=REFERER, type='web', **kwargs):
    # Find the URL for the specific type of Google AJAX Search API.
    baseurl = BASEURLS.get(type)
    if baseurl is None:
        raise TypeError

    # Add the necessary arguments.
    kwargs.update({
        'v': 1.0,
        'q': query,
    })

    # Build the URL.
    url = '?'.join((baseurl, urllib.urlencode(kwargs)))

    # Add a referer HTTP header to the request.
    req = urllib2.Request(url)
    req.add_header('Referer', referer)
    f = urllib2.urlopen(req)

    # Translate the JSON response to a Python object.
    return jsonlib.read(f.read())

if __name__ == '__main__':
    import sys
    query = sys.argv[1]

    res = search(query, hl=’en’)
    # Show the full response from the service.
    print res
    # Show the Google count for the query.
    print res['responseData']['cursor']['estimatedResultCount']

上のサンプルプログラムを使うときは，

• REFERERのアドレスを自分のものに置き換えること
• Googleが出している利用規約を守る

ことに注意してください．

search関数のオプショナル引数は，Googleのサービス側にパラメータとして素通りさせています．各サービスに対して，どのような引数が使えるのか（例えば言語を設定するhlなど）は，リファレンスマニュアルを参照してください．

RESTインタフェースは，今回初めて使いましたが，SOAPと比べるとかなりお手軽ですね．JavaScriptで扱うのが簡単なのは当たり前ですが，Pythonから使う場合でも，JSONライブラリがあればすぐに出来ます．Pythonでは，すでにSOAPのライブラリよりもJSONライブラリの方が充実している感じになっています．やっぱりXMLはコンピュータが交換するフォーマットとして，まだシンプルさが欠けていたのかも知れませんね．