遥かへのスピードランナー

シリコンバレーでAndroidアプリの開発してます。コンピュータービジョン・3D・アルゴリズム界隈にもたまに出現します。

トップ > IT

WEB+DBプレスの「[速習]レコメンドエンジン」のサンプルプログラムを訂正してみる

レコメンド IT

プリファードインフラストラクチャーのid:tkngさんと岡野原さんがWEB+DBプレスvol.49に「[速習]レコメンドエンジン」という記事を書かれています。

WEB+DB PRESS Vol.49
WEB+DB PRESS Vol.49
posted with amazlet at 09.03.08

技術評論社
売り上げランキング: 359
Amazon.co.jp で詳細を見る

レコメンドエンジンには前々から興味を持っていたので、早速サンプルコードを自分でも書いてみるか、と思い誌面のソースをXCodeに打ち込んで動かしていたのですが、コンパイルが通らない。

なにぶんC++なんてほとんど書いたことがないので、自分のやり方が悪いのかと疑ったのですが、代入する変数が間違っていたりミススペルがあったりなど、おそらくこれは誌面のソースが間違っているのだろうという結論に至りました。
例えば・・・
p130 リスト２より

#include <vector>
typedef vector<pair<int, int> > SparseDoc;Svec; // ←コンパイルとおりません。
typedef SparseVec::iterator Svec::iterator sit; // ←コンパイルとおりません。

p130 リスト3より

float calcInp(sparceVec& Svec& il1, sparceVec& SVec& il2) {
// ↑コンパイルとおりません。さらにtypedefではSparseVecとなっているはずなのにsparceVecです。
...
}

などなど。

僕のように、自分のかき方が悪いんじゃないかと疑って苦労している人もいるのではないかと思い、修正したソースコードをさらしておきます。

ちなみに、内容としては以下のような縦軸にユーザ番号、横軸にアイテム番号を取り、値としてユーザのアイテムに対する評価点を持った行列が与えられたときに、アイテム間の類似度を計算するというものです。

ユーザ番号\アイテム番号 0 1 2 3 4
0   1     3
1 2     3
2 3   5    
3   2 2    
4 3     4  

以下が修正したソースコード。WEB+DBプレスvol.49の130ページ〜131ページあたりが修正の対象で、アイテム番号0に対する各アイテムの類似度を計算して出力する箇所をmain()関数として追加しています。
[main.cpp]

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef vector< pair<int,int> > SparseVec;
typedef SparseVec::iterator sit;

// 各ユーザごとにレビューしたアイテム番号とその結果を記録した結果
// idが昇順で並んでいる
vector<SparseVec> userLog;
// 各アイテムごとにレビューされたユーザ番号とその結果を記録した結果
vector<SparseVec> itemLog;

// il1とil2の内積を計算する
float calcInp (SparseVec& il1, SparseVec& il2) {
	sit it1 = il1.begin();
	sit it2 = il2.begin();
	int inp = 0;
	while (it1 != il1.end() && it2 != il2.end()) {
		int id1 = it1->first;
		int id2 = it2->first;
		if      (id1 < id2) ++it1;
		else if (id1 > id2) ++it2;
		else {
			inp += it1->second*it2->second;
			++it1;
			++it2;
		}
	}
	return inp;
}

// 各ベクトルの長さは前もって計算しておく
vector<float> norms;

void calcNorms () {
	for (size_t i = 0; i < itemLog.size(); i++) {
		float norm = sqrt(calcInp(itemLog[i], itemLog[i]));
		norms.push_back(norm);
	}
}

// i番目のアイテムとj番目のアイテム間のコサイン類似度を計算する
float calcCosSim (int i, int j) {
	float inp = calcInp(itemLog[i], itemLog[j]);
	return inp / norms[i] / norms[j];
}

// アイテムiと他のすべてのアイテムのコサイン類似度をまとめて計算してretに結果を返す
void calcMatchNum (int i, vector<float>& ret) {
	ret.resize(itemLog.size());
	SparseVec& sv(itemLog[i]);
	for (sit it = sv.begin(); it != sv.end(); it++) {
		// it->firstを購入したユーザを列挙する
		SparseVec sv2(userLog[it->first]);
		int val = it->second;
		for (sit it2 = sv2.begin(); it2 != sv2.end(); ++it2) {
			ret[it2->first] += val * it2->second;
		}
	}
	// 結果の正規化を行う
	for (size_t j = 0; j < itemLog.size(); j++) {
		ret[j] /= (norms[i] * norms[j]);
	}
	
	// ret[j]にはcalcCosSim(i,j)と同じ結果が入っている
}

int main (int argc, char * const argv[]) {	
	// itemLogを初期化
	itemLog.resize(5);
	itemLog[0].push_back(make_pair(2,3));
	itemLog[0].push_back(make_pair(4,3));
	itemLog[1].push_back(make_pair(0,1));
	itemLog[1].push_back(make_pair(1,2));
	itemLog[1].push_back(make_pair(3,2));
	itemLog[2].push_back(make_pair(2,5));
	itemLog[2].push_back(make_pair(3,2));
	itemLog[3].push_back(make_pair(4,4));
	itemLog[4].push_back(make_pair(0,3));
	itemLog[4].push_back(make_pair(1,3));
	
	// userLogを初期化
	userLog.resize(5);
	userLog[0].push_back(make_pair(1,1));
	userLog[0].push_back(make_pair(4,3));
	userLog[1].push_back(make_pair(1,2));
	userLog[1].push_back(make_pair(4,3));
	userLog[2].push_back(make_pair(0,3));
	userLog[2].push_back(make_pair(2,5));
	userLog[3].push_back(make_pair(1,2));
	userLog[3].push_back(make_pair(2,2));
	userLog[4].push_back(make_pair(0,3));
	userLog[4].push_back(make_pair(3,4));
	
	// 各ベクトルの長さを初期化
	calcNorms();
	
	// あるアイテムと他のアイテムとの類似度をそれぞれ個別に求める
	cout << "calcCosSim" << endl;
	for (size_t i = 0; i < itemLog.size(); i++) {
		cout << "itemNo:" << i << " similarity:" << calcCosSim(0,i) << endl;		
	}
	
	// あるアイテムと他のアイテムとの類似度をすべてまとめて求める
	cout << "calcMatchNum" << endl;
	vector<float> cosSimVec;
	calcMatchNum(0, cosSimVec);
	for (size_t i = 0; i < itemLog.size(); i++) {
		cout << "itemNo:" << i << " similarity:" << cosSimVec[i] << endl;
	}
	
    return 0;
}

ちなみに実行した結果は以下の通り。

calcCosSim
itemNo:0 similarity:1
itemNo:1 similarity:0
itemNo:2 similarity:0.656532
itemNo:3 similarity:0.707107
itemNo:4 similarity:0
calcMatchNum
itemNo:0 similarity:1
itemNo:1 similarity:0
itemNo:2 similarity:0.656532
itemNo:3 similarity:0.707107
itemNo:4 similarity:0

となり、calcCosSimでもcalcMatchNumでも同様の結果を得られていることが分かります。
またアイテム0と類似度が一番高いのはアイテム3だということも分かります。

なんだが揚げ足取りみたいになってしまいましたが、この記事自体はレコメンドのアルゴリズムを実際のソースコードや数式などを交えながら説明した数少ない一般紙での記事だと思いますし、LSHやSVD、RBMといった一歩踏み込んだレコメンドの手法も紹介されていて非常に面白いです。とってもすばらしい記事ですので、上のコードとかを参考により多くの人が理解を深めてくれるといいな、と思います。修正したら図書券とかもらえるかもしれないし。

id:tkngさん、岡野原さん、すばらしい記事をどうも有り難うございます！

Firefoxアドオンでちょっとコアにタブを扱う

IT Firefox

Firefoxのアドオンで、ちょっとコアにタブを扱う処理のメモ。

http-on-modify-requestなどのトピック発生時に、HTTPリクエスト発生元のタブを取得するサンプルコード

getTabFromHttpChannelでtry-catchしている部分は、リクエスト元がDOMWindowじゃない場合にExceptionが発生するのでキャッチしているが、あんまり綺麗じゃないので他にうまいやり方はないだろうか。

const Cc = Components.classes;
const Ci = Components.interfaces;
const Cr = Components.results;

//myHTTPListnerはhttp-on-modify-requestなどのトピックのObserverとして登録するオブジェクト
//Observer登録部分のソースは省略
function myHTTPListener() {};
myHTTPListener.prototype = {
  observe : function (subject, topic, data) {
    var httpChannel = subject.QueryInterface(Ci.nsIHttpChannel);
    var tab = getTabFromHttpChannel(httpChannel);
    if (tab) {
      //リクエスト元のタブに対する処理
    }
  }
};

function getTabFromHttpChannel (httpChannel) {
  var tab = null;
  if (httpChannel.notificationCallbacks) {
    var interfaceRequestor = httpChannel.notificationCallbacks
        .QueryInterface(Ci.nsIInterfaceRequestor);
    try {
      var targetDoc = interfaceRequestor.getInterface(Ci.nsIDOMWindow).document;
    } catch (e) {
      return;
    }
    var webNav = httpChannel.notificationCallbacks.getInterface(Ci.nsIWebNavigation);
    var mainWindow = webNav.QueryInterface(Ci.nsIDocShellTreeItem)
        .rootTreeItem.QueryInterface(Ci.nsIInterfaceRequestor)
        .getInterface(Ci.nsIDOMWindow);

    var gBrowser = mainWindow.getBrowser();
    var targetBrowserIndex = gBrowser.getBrowserIndexForDocument(targetDoc);
    if (targetBrowserIndex != -1) {
      tab = gBrowser.tabContainer.childNodes[targetBrowserIndex];
    }
  }
  return tab;
};
タブごとに値を保存・取得するサンプルコード

タブごとに任意の値を保存するには、単に独自プロパティを１つ追加してもよいが、sessionStoreを使うとFireFoxを再起動してタブ復元しても保存される。詳細はこのへん。

var tab = gBrowser.selectedTab; 
var ss = Cc["@mozilla.org/browser/sessionstore;1"].getService(Ci.nsISessionStore);

//タブに任意の値を保存
ss.setTabValue(tab, "your-attribute", "your-value");

//タブに保存した値を取得
var yourValue = ss.getTabValue(tab, "your-attribute");

QueryInterfaceとgetInterfaceの違い

Firefox IT

「Firefoxアドオンでちょっとコアにタブを扱う」を書いてみて、インターフェースを取得するのに、QueryInterface(Ci.nsIXXXXX)としている箇所と、QueryInterface(Ci.nsIInterfaceRequestor).getInterface(Ci.nsIXXXXX)としている箇所の違いが自分でもよく理解できなかったので、いろいろ調べてみた。

まず、MDCには以下の説明がある。
getInterface - MDCより

getInterface is very similar to QueryInterface. The main difference is that interfaces returned from getInterface are not required to provide a way back to the object implementing nsIInterfaceRequestor. The semantics of QueryInterface dictate that given an interface A that you QueryInterface on to get to interface B, you must be able to QueryInterface on B to get back to A. nsIInterfaceRequestor, however, allows you to obtain an interface C from A that may (or most likely) will not have the ability to get back to A.

QueryInterfaceは可逆だけど、getInterfaceは不可逆であるという説明だが、いまいち良く分からない。そこで、真実はソースコードのみ、ということでFirefoxのソースコードを調べてみた。
結果として、QueryInterfaceとgetInterfaceはプログラム上役割が決まっているというものではなく、実装に依ってその役割が異なってくる。しかし、ざっとソースを眺めたところのそれぞれのメソッドの役割はおおよそ固定化されており、以下の通りとなっていることが分かった。

  • QueryInterfaceはそのオブジェクト自身に、指定されたインターフェースを持っているかどうかを問い合わせるメソッドであり、返却値はキャストされた自分自身である（ことが多い）。
  • getInterfaceはそのオブジェクト自身に、指定されたインターフェースを持っている必要はなく、何らかの方法で（たとえばメンバ変数を返すなど）指定されたインターフェースを持つオブジェクトを返すメソッドである。従って返却値は自分自身ではないことが多い。

nsDocShellを例にあげて見ていくと、まずQueryInterfaceの実装は、以下の通り。
nsDocShell.cppより

NS_INTERFACE_MAP_BEGIN(nsDocShell)
    NS_INTERFACE_MAP_ENTRY(nsIDocShell)
    NS_INTERFACE_MAP_ENTRY(nsIDocShellTreeItem)
    NS_INTERFACE_MAP_ENTRY(nsIDocShellTreeNode)
    NS_INTERFACE_MAP_ENTRY(nsIDocShellHistory)
    NS_INTERFACE_MAP_ENTRY(nsIWebNavigation)
    NS_INTERFACE_MAP_ENTRY(nsIBaseWindow)
    NS_INTERFACE_MAP_ENTRY(nsIScrollable)
    NS_INTERFACE_MAP_ENTRY(nsITextScroll)
    NS_INTERFACE_MAP_ENTRY(nsIDocCharset)
    NS_INTERFACE_MAP_ENTRY(nsIScriptGlobalObjectOwner)
    NS_INTERFACE_MAP_ENTRY(nsIRefreshURI)
    NS_INTERFACE_MAP_ENTRY(nsIWebProgressListener)
    NS_INTERFACE_MAP_ENTRY(nsISupportsWeakReference)
    NS_INTERFACE_MAP_ENTRY(nsIContentViewerContainer)
    NS_INTERFACE_MAP_ENTRY(nsIEditorDocShell)
    NS_INTERFACE_MAP_ENTRY(nsIWebPageDescriptor)
    NS_INTERFACE_MAP_ENTRY(nsIAuthPromptProvider)
    NS_INTERFACE_MAP_ENTRY(nsIObserver)
NS_INTERFACE_MAP_END_INHERITING(nsDocLoader)

マクロになっているが、間違いなくQueryInterfaceの実装部分である。
マクロの実態はきわめて単純で、自分自身を指定されたインターフェースに対してキャストしているだけである。

nsISupportsImpl.hより

#define NS_INTERFACE_MAP_ENTRY(_interface)      NS_IMPL_QUERY_BODY(_interface)
//略...
#define NS_IMPL_QUERY_BODY(_interface)                                        \
  if ( aIID.Equals(NS_GET_IID(_interface)) )                                  \
    foundInterface = static_cast<_interface*>(this);                          \
  else

見ての通り、自分自身をキャストしているだけである。

一方で、nsDocShellにおけるgetInterfaceの実装は次のようになっている。
nsDocShell.cppより

NS_IMETHODIMP nsDocShell::GetInterface(const nsIID & aIID, void **aSink)
{
    //略...
    if (aIID.Equals(NS_GET_IID(nsIURIContentListener))) {
        //略...
    }
    else if (aIID.Equals(NS_GET_IID(nsIScriptGlobalObject)) &&
        //略...
    }
    else if ((aIID.Equals(NS_GET_IID(nsIDOMWindowInternal)) ||
              aIID.Equals(NS_GET_IID(nsPIDOMWindow)) ||
              aIID.Equals(NS_GET_IID(nsIDOMWindow))) &&
             NS_SUCCEEDED(EnsureScriptEnvironment())) {
        return mScriptGlobal->QueryInterface(aIID, aSink);
    }
    else if (aIID.Equals(NS_GET_IID(nsIDOMDocument)) &&
             NS_SUCCEEDED(EnsureContentViewer())) {
        mContentViewer->GetDOMDocument((nsIDOMDocument **) aSink);
        return *aSink ? NS_OK : NS_NOINTERFACE;
    }
    //略...
}

これを見ても分かる通り、たとえば、nsIDOMWindowをgetInterfaceで求められた場合、docShellは自分自身を返すのではなく、mScriptGlobalというメンバ変数に対し処理を丸投げしているといえる。

上記のようにQueryInterface可能なインターフェースとgetInterface可能なインターフェースはそれぞれに別々にハードコーディングされている。QueryInterface可能なインターフェースは、XPCOM Reference - XULPlanetなどを参照すればどうにか分からないでもないが、getInterface可能なインターフェースについては、少なくとも自分の調べた限りは参照できるドキュメントが存在しなかった。

ソースコードを参照するしかない、ということであれば何とも遺憾な話である。ドキュメントつくってほしいなぁ（他力本願）。

Ubiquityの日本語変換パッチが本家に取り込まれました

IT Firefox

Slashcolonさんのトラックバックで知りましたが、以前提出したUbiquityのパッチが、本家のバージョンに取り込まれていたとのこと。さっきtrac見たら4週間前に取り込まれたみたいですねー、全然気づきませんでした。。

僕も忘れかけてたんですが、どうやらUbiquityのメーリングリストでid:murky-satyrさんが催促してくれていたらしく、それを受けて取り込まれたみたいです。
どもです！！murky-satyr++！！

オープンソースの進め方が僕自身分かっていないところがあったのですが、単にパッチをアップするだけじゃ他の開発者の方には何のことやら分からないので、メーリングリストなどできっちりと必要性をアピールしないとダメですね。次回はこの辺踏まえてコミットしていこうと思います。

ともあれ、これで次のバージョン（0.2.0かな？）から正式に日本語変換がエンターキーで出来るようになると思われます。
で、いまさらなんですが最終野良バージョンということで現行のUbiquity0.1.5にもパッチあててみました。
以下に置いておきますのでご自由にどうぞ。
Ubiquity0.1.5エンターキーでの日本語入力対応版ダウンロード

OpenID Tech Night Vol.4に参加してきました

セミナー OpenID IT

id:ZIGOROuさんに誘われてOpenID Tech Night Vol.4に参加してきました。
tkudoさんの「ID技術　最新動向2009」のセッションは後半ちょっとしか聞けませんでしたが、ZIGOROuさんの「OpenID 認証 2.0 入門」のセッションはフルで聞けました。

OpenIDといえば、mixiとかYahooの認証が使えてNet::OpenID::Consumerとか使うと簡単に実装できるやつでしょ？くらいの認識しかない自分にとっては、大変聞きごたえのある内容。Discover〜Association〜Authentication〜Verificationの認証全体の流れも分かりやすく、モジュール使っているとほとんど意識しないAssociation（Indirect Communication）の部分の説明など自分にとっては参考になりました。

終了後にZIGOROuさんと話して、OAuthの話をされてましたが、この辺の区別が全然つかないんですよねー。OpenID、OAuthとかSAMLとか。
帰ってちょっと調べてみましたが、OpenIDはプロバイダからの認証結果といくつかの付随情報を受け取れる、OAuthはプロバイダのAPIに対する期間限定のアクセス権を取得できる、っていうくらいの認識でよいのですかね。モバイルみたいに認証が個体識別番号で簡単に済むUAの場合は、OAuthを使うといろいろと世界は広がりそうです。ZIGOROuさんもまさに世界を狙っているそうなので、今後の展開が非常に楽しみですw

Webデベロッパの祭典+ちょっとアキバ気分で。＠秋葉原UDXに行ってきました。

IT セミナー

久々にセミナー参加。
３セッションしか参加していないのですが、以下メモと所感。

どうするデベロッパ！？2009年プログラミング大展望/子飼弾氏

弾さんを弾さんと認識して話を聞くのはこれが初めて。（以前YAPCで話を聞いてたけど、そのときは弾さんと認識してなかった）「未来はどうなる？」じゃなくて「未来をどうするか」だというような弾さん節全開な内容。内容は激しく同意です。
意外だったのは、「弾さんは自分が裕福だと思いますか」という質問に対して、「自分はまだまだ学ぶべきことがたくさん残っているので、まだまだ十分に裕福とは言えない。むしろ学び方というものも、学んでいきたいと思っている。」ということをおっしゃられていたことです。ちょうど自分が、読書法とか学習法とかを模索している時期で、「弾さんのように既に地位を築いている人は、自分なりの学習法や生き方のスタイルというものは既に確立しているんだろうなあ」と勝手に思っていたので、弾さんのような人でもまだ「学び方を学びたい」と考えている事実に驚かされました。
弾さんご自身も、自分のプレゼンのスキルはまだ未熟だとおっしゃられていたように、いくら速読が出来て経験を積んでも、下手な勉強方法ではなかなか上達していかないんですね。いつか頭打ちになってしまう。そんな危機感を強く持ちました。やっぱり自分の注力すべき分野を絞って努力していくべきだと思うんですよ。人生短いしね。

国内最大規模のRuby on Railsサイト「クックパッド」の裏側見せます。/クックパッド（株）橋本健太氏

アクセス数遷移、インフラ構成からミドルウェア、開発環境、開発方法まで具体的なソフトウェア名（アプリケーションサーバーにmongrel、全文検索に未来検索ブラジルのTriton、ソースコードレビューにShinjikoなど）なども折り込みつつ話されていて、かなり参考になりました。最後に質問タイムがあるかなと思ってあれこれ考えていたのですが、無かったので自分が感じた疑問を書いておこうと思います。

  • 企画から開発までのプロセス、サイトの企画と開発の体制は分かれているのか、企画から開発、サービスインまでどのようなプロセスを経るのか。「やりたいこと」じゃなきゃやらないみたいな話が途中ありましたが、それが許される体制って羨ましいなとちょっと思ったので。
  • サイトをリニューアルされたということでリニューアル後にこれは失敗したなとか、逆にこれは良かったという点があれば教えてほしかった。リニューアルの仕様定義はどのように行ったのか、リニューアル時に削った機能はあるのか、リニューアル後にユーザーの反発を受けた部分があるのか、など。僕自身もサイトリニューアルの経験がありますが、既存サイトのドキュメントが無かったりとかで最初はうまく進みませんでした。おかげでリニューアル後に要件漏れが発覚、みたいなことも恥ずかしながらあったりして。こういうことをどうやって防止されたのかを聞きたかったです。
  • 「機能追加することを事前にユーザーに通知しない」というようなことをおっしゃられていましたが、じゃあその効果をどのように図っているのか。ユーザーからの明確なフィードバックが得られる機会ってそんなにないと思うんですよね。自分がFireMobileSimulatorを開発してても思うんですが、ブログの記事と直接公式サイトに寄せられる少数の投稿くらいしかフィードバックをもらえる機会がないんですよね。何か効果を図るノウハウがあるならば知りたかったです。

Java×ActionScriptで広がるWebアプリの世界/（株）電通国際情報サービス大谷晋平氏(id:shot6)

最初から最後までActionScriptの瑣末な言語仕様の説明に徹してしまったのが少し残念だなあと感じました。あれくらいならおそらく何か参考書を見れば分かる内容なので。
ただ、FlexというものがWeb開発業界に浸透してきているんだなあと認識できたのは良かったです（遅っ）。今自分がExtJSとかいじりながら実装していきていることはFlexでやればよかったのかなあと思ったり。今作っているものが一段落したらFlexにも手を出していきたいなあと思いました。

要望とか

あとはイベントとしてパソナさんに言いたいのが、飲み物で水を用意してほしいということ。いつもコーヒーしか置いてないんですけど、コーヒー苦手な人って僕も含めて結構いると思うんです。水分補給が気楽にできれば、もっと居心地のいいイベントになるかなあという感じです。

まあ、自分自身のやる気を刺激してくれたので、総じてよいイベントでした。
こういうイベントはしょっちゅうじゃなくて、たまに行って刺激剤にするのがよい。

CPAN Authorになりました

Perl IT

DBIx::Class::ForceUTF8というモジュールを作ってCPANにアップロードしました。

DBIx::Class::ForceUTF8 allows you to get columns data that have Unicode flag without specifying a column name. Best used with DBIx::Class::Schema::Loader.

DBIx::Class::UTF8Columnsとよく似ているんですが、DBIx::Class::UTF8Columnsを使っていると、utf8として扱いたいカラム名をSchemaクラスの中で指定しなければいけません。僕の場合、Schemaの生成はDBIx::Class::Schema::Loader を使って、ほとんど自動化しているので、カラム名を１個１個指定するのが非常に面倒です。

「DBIx::Class経由で取得する文字列にUTF-8 flagを付けたい」に書いてあるようなinflate・deflateの中でutf8フラグのオンオフを行うやり方もあるのですが、inflateはget_columnするときに通らないのであまりやりたくない。

というわけで、UTF8Columnsと同じようにget_columnの中でutf8のオンオフを行いつつ、カラム名を設定してなくても済むようなモジュールを作ってみました。

DBIx::Class::ForceUTF8 - Force UTF8 (Unicode) flag on columns

ほとんどDBIx::Class::UTF8Columnsのコピーで作者のtypesterさんにはとても恐縮なのですが、デビュー作ということで大目に見てもらえればと願うばかりです。。。

というわけでCPAN AUTHORデビューです。
今後ともよろしくお願いします＾＾