Home > 11月, 2008

2008.11.29

NOW 71

NOW71をアマゾンUKで£11.98にて購入.購入時の為替レートが£1=141.5円だったので,日本円に換算にすると1,695円.ちなみに,NOW71を日本のアマゾンで購入すると2,486円,HMVで購入すると4,530円もする.

アマゾンUKからの日本への送料(CDとDVDの場合)は,1回の配達あたりの固定費が£2.09,CD/DVD1枚につき£1.49.今回は他に3点購入のまとめ買いで,送料は£8.05=1,139円だった.洋楽のCDやイギリスのDVDをまとめ買いするなら,日本のアマゾンよりもお得になることがある.イギリスのバブル崩壊・景気後退,恐るべし.

恒例の聴いたことあった率は,Disc 1で83%,Disc 2で59%と低め.

Disc 1のお気に入り曲は,#1, #2, #4, #5, #9, #12, #16, #17, #22

先頭を飾ったのはGirls Aloudの「The Promise」.どこかで聞いたことがあるような無難な曲作りだが,オリジナル曲らしい.日本のアイドルもまともな音楽を歌って欲しい.

#2は今年一番物議を醸したと思われる,Katy Perryの「I Kissed A Girl」.歌詞に自分が共感することはないけど,別に特殊なことではなく,「まぁそんなもんだろ」という感じは同意.曲もカッコイイし,PVもそれっぽくてインパクトがある.Youtubeには早速”boy”バージョンのパロディがあって,ウケた.

#5のKid Rock「All Summer Long」は,カントリー調の緩めのロックナンバー.夏頃ラジオでヘヴィー・ローテしていて,イギリスなどのヨーロッパ各国やオセアニアで週間チャート1位を獲得.たまにこういう曲を聴くのも,新鮮でリフレッシュされますね.

#9,Madconの「Beggin’」は,The Four Seasonsが1967年に発表した曲のカバー.完全に今風の曲に生まれ変わってます.The Four Seasonsと言えば,「Sherry」と「君の瞳に恋してる(Can’t Take My Eyes Off You)」が非常に有名.同じくThe Four Seasonsの「Rag Doll」を久々に聴いて,懐かしさがこみ上げてきました.

#12の「You Make It Real」はJames Morrisonらしい曲.

#15を歌っているのはコメディアンのPeter Kay.スター発掘番組「X Factor」のパロディ.曲を作っているのはTake ThatのGary Barlowなのか.すげぇ.Peter Kayは,これまでにも「Is This the Way to Amarillo」や「I’m Gonna Be (500 Miles)」など,楽しいカバー曲で有名.

#16はベースがカッコイイ! #17を歌っているThe Saturdaysは,比較的最近結成された女性5人組グループ.

#22は,「Call On Me」や「Proper Education」で有名なスウェーデンDJ,Eric Prydzの「Pjanoo」.Youtubeで話題になり,イギリスの週間チャートで2位に.こういう曲がちゃんと売れるのはいいことだ.

Disc 2のお気に入り曲は#1, #2, #3, #4, #9, #10, #19

#1は,日本でもCMが流れているColdplayの「Viva La Vida」.文句の付けようが無い.#2はThe Scriptの「The Man Who Can’t Be Moved」.アルバムを買ってしまいそう.#3はRazorlightの新曲.PVでは,炎の前にしたJohnny Borrellがハンサムすぎ.#4は日本で聴いたことがあるように思っていたが,気のせいか.

#6の「Shut Up and Let Me Go」は,個人的にツボにはまっている,The Ting Tingsのサード・シングル.前のシングルの「That’s Not My Name」もそうだが,これで曲にしてしまうスリル感がたまらない.最初のシングルは「Great DJ」で,サントリーのダイエットビールのCM曲だったのか.知らなかった・・・.

#10は,Guru Joshが1989年に発表した「Infinity (1990s… Time for the Guru)」のセルフ・リミックス.このバージョンはカッコイイが,1989年バージョンは,かなりダサダサのアレンジ.PVは女の人が踊るありがちな系.

2008.11.27

dartsのクローン

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の何処を修正すべきなのかはっきりしてくるので,大変有り難いです.ただ,今年度は時間が無さそうなので,更新は来年度に持ち越しになるかもしれません.

2008.11.19

CRFsuite 0.5 released

CRFsuiteのバージョン0.5をリリースしました.変更点はバグ修正のみです.

  • liblbfgsに該当する部分のソースコードを削除し,外部からリンクする仕様に変更した.*NIXな環境でCRFsuiteをビルドするには,liblbfgsを別途ダウンロードし,ビルドもしくはインストールする必要があります.
  • L-BFGSの収束判定に関するパラメータ(lbfgs.stopとlbfgs.delta)を追加した.このパラメータは,${lbfgs.stop}回前から現在の反復において,対数尤度の改善率が${lbfgs.delta}を下回った時に,L-BFGSのアルゴリズムを終了させることができます.これらのパラメータのデフォルト値は,lbfgs.stop = 10, lbfgs.delta = 1e-5 です.
  • L-BFGSの直線探索のアルゴリズムを指定するパラメータ(lbfgs.linesearch)を追加した.利用可能なアルゴリズムは,”MoreThuente”, “Backtracking”, “LooseBacktracking”で,”MoreThuente”がデフォルトです.
  • 訓練データやテストデータにおいて,item:valueの形式をきちんと読みこめていなかったバグを修正
  • タグ付け時の精度の計算が一部間違っていた問題を修正
  • タグ付け時に,あるアイテムの素性が空(訓練時にその素性が出現しなかった場合を含む)だったときに,そのアイテムを無視してしまい,シーケンスの長さが変わってしまう問題を修正

Pythonのsqlite3を使うときはcommitをお忘れなく

デバッグで3時間くらいはまったのでメモ.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みたいな言語は何もしなくても必要な終了処理をしてくれるイメージなので,デフォルトがこういう仕様になっていると,はまる人が続出すると思う.

2008.11.14

How to Tell if Your Cat is Plotting to Kill You

How to Tell if Your Cat is Plotting to Kill You

猫は本当は頭が良いのに,バカなふりをしてたんですね.なかなかやるなぁ.”kneading on you” と “Bringing you dead animals” が,特に興味深い.イラストもかわいい.

GIGAZINEより

2008.11.10

DASTrie 1.0 released

Static Double Array Trie (DASTrie) という静的ダブル配列のライブラリをリリースしました.ダブル配列の実装はいろいろありますが,このライブラリの特徴を以下に挙げます.

  1. C++テンプレートを利用して,std::mapのような連想配列,std::setのような集合を簡単に実装できる.
  2. ダブル配列の要素を4バイト,もしくは5バイトで表現し,データベースをコンパクトにする(通常の実装では要素サイズは8バイト).
  3. 最小接頭辞トライを実装し,データベースのサイズをコンパクトにする.

よくあるダブル配列の実装では,レコードのキーとユニークなIDがトライの中に格納され,レコードのデータは配列などで独自に管理する必要があります.DASTrieはC++のテンプレートで,任意のデータ型をレコードとして使い,レコードをトライの中に格納するので,連想配列として簡単に利用できます.もちろん,トライを(レコードの値がない)集合として使うこともできます.

2番目の特徴は,A compact static double-array keeping character codesという論文に記述されているアイディアを実装したものです.通常のダブル配列は,int(4バイト)を要素サイズとして,BASEとCHECKと呼ばれる2つの(同じ要素数の)配列を使います.つまり,BASEとCHECKをまとめて考えると,ダブル配列の要素のサイズは8バイトということになります.この論文で提案されているのは,CHECKにBASE配列へのバックリンク(インデックス)を作るのではなく,ノード遷移に用いられた文字を格納すれば,CHECK配列は1バイトで済むという提案です.ただし,ダブル配列をこのように修正すると,すべてのBASE値は異ならなければならないという制約が付きます.元々の論文では,BASEを3バイト,CHECKを1バイトで表現して,BASEとCHECKをint(4バイト)で表現することを提案しています.ただし,BASEを3バイトで表現すると,格納できるデータのサイズにかなりの制限がかかるので,DASTrieではBASEを4バイト,CHECKを1バイトとして,従来通り大規模なデータが格納できるトライも実装しました.

せっかくなので,Google Web 1TコーパスとUMLS SPECIALIST Lexiconを用いて,パフォーマンスを評価してみました.Google Web 1Tコーパスは,レコードの数が多いので,ダブル配列の要素を5バイトで表現したDASTrieを用いました.実験結果によると,DASTrieのデータベースは,従来のトライの実装と比べて,1/3~2/3くらいのサイズで格納できることが示されました.

Darts: Double-ARray Trie Systemと比べると,DASTrieのデータベース構築時間がかなり長いですが,これはデータベースのサイズを小さくするために犠牲にした部分です.ダブル配列の構築で一番時間がかかるのは,「あるノードの下のすべての子ノードを格納できるBASE値を探す」という処理です.これは,あるノードのすべての子ノード集合を「クロスワードパズルのピース」のようなもので表現し,そのピースがぴったりはまる「未使用箇所」を,ダブル配列の先頭から探すという操作になります.ダブル配列が断片化されていないときは,格納可能場所を速く見つけることができますが,ダブル配列が断片化されてくると,ぴったりはまる箇所を見つけるのが大変になります.Dartsは,最小接頭辞トライとして実装されていないので,子を一つしか持たないノードを大量に格納し,断片化されたダブル配列の隙間を埋めことができます.また,Dartsはダブル配列の断片化の度合いを計測し,ある程度断片化されたら,その領域を諦め,今後使用しないようにするというヒューリスティックが実装されています.Dartsのデータベースサイズが大きいのはこのためで,速さと引き替えにデータベースサイズが大きくなります.DASTrieは,ダブル配列の空きスペースをできるだけ減らすように頑張るので,Google Web 1Tコーパスのような分枝数が大きいレコードを格納しようとすると,時間がかかります.

DASTrieはダブル配列の実装の中では,かなり頑張っているのですが,Level-Order Unary Degree Sequence (LOUDS) を実装した Tx: Succinct Trie Data structure には,データベースサイズで大きく水をあけられています.Txはすごいですね.ダブル配列は,この辺が限界なのかなぁと思っています.

2008.11.08

ランニング

嫁に顔がぷっくりしていると言われ,体重や体脂肪率が自己ワーストの水準なので,石神井川の畔をランニング.とりあえず1時間走ると決めて,30分走ったあたりで折り返して帰ってきた.途中通過した目印は,埼京線,中山道(国道17号),中板橋(東武東上線),川越街道(国道254号)で,環状7号線と交差するところで折り返し.

家に帰ってから地図で距離を測ってみると,往復で11kmだった.走った時間は信号待ちを除いて1時間なので,時速11kmくらいで走っていたことになる.高校のときの学校のマラソンでは,17kmを1時間半くらいで走っていたので,そのときよりは遅いペースだが,年齢と体重が12くらい増えていることを考えると,自分でも驚くぐらい速い.今日の二倍の距離を走ると,豊島園が折り返し地点になるので,当面はこれを目標にしよう.

石神井川沿いの道は,意外とでこぼこしているので,足に負担がかかる.あと,橋の手前と後で上り坂と下り坂になるので,これも結構しんどい.信号は3カ所くらいだったが,道を渡る毎にスピードを落として,他の交通に気を遣わなければならないので,ペースが作りづらい.ただ,秋の涼しい風を切って走れるし,いろいろ景色が変わるので,御殿下のトレーニングルームよりは全然楽しい.ただ,30分くらいの軽めのランニングなら,王子中央公園や十条自衛隊の周辺の方が,走りに集中できて快適かなぁ.

消費カロリーはだいたい700~800kcal.ラーメン大盛り一杯分,生中4杯分くらいに換算してしまうと,ちょっと悲しくなる.

2008.11.06

Attacking Decipherment Problems Optimally with Low-Order N-gram Models

Sujith Ravi; Kevin Knight. Attacking Decipherment Problems Optimally with Low-Order N-gram Models.

文字列置換による暗号化は,平文が”decade”のときに,{(d→Q), (e→W), (c→B), (a→S)}という文字置換操作を行い,”QWBSQW”という暗号文を得るという操作である.本研究は,”QWBSQW”のような暗号文を受け取ったときに,その平文を解読する方法として,低次なn-gram言語モデルと,整数計画法を用いる手法を提案している.

整数計画法による定式化は,bi-gram言語モデルで近似された平文Mの生成確率 P(M) を目的関数とし,変数として,平文のi番目の文字がpで,(i+1)番目の文字がrかどうかを表現する0–1変数 link_{ipr},平文の文字pを暗号文の文字qへ置換するかどうかを表す0-1変数 key_{pq} を決定する.整数計画法の制約条件として,「平文と暗号文の文字の間に一対一の対応が取れていること」「あるノードの左側のエッジと右側のエッジの数が同じであること(平文のbi-gramをエッジとして一つのパスができることを保証する)」「エッジ変数群 link_{ipr} が,置換変数群 key_{pq} と矛盾しないこと」を導入している.

本論文では引用されていないが,CRFで確率を最大にするラベルシーケンス(argmax)を求める際,「それぞれのラベルはシーケンスの中に一回しか出現してはいけない」など,マルコフ性に反する制約を導入したいとき,整数計画法でargmaxを求める方法が提案されている(Roth and Yih. Integer linear programming inference for conditional random fields. ICML, 2005).本研究は,これと類似のアイディアで,文字の置換を表す変数とその制約を追加した手法と捉えることができる.

Summarizing Spoken and Written Conversations

Gabriel Murray; Giuseppe Carenini. Summarizing Spoken and Written Conversations.

本論文は,会話文の要約システムを提案し,AIMコーパス(会議の議事録),及びメールのログ(Enronコーパス)において評価をしている.要約システムは,ある文を抽出すべきかどうかを判別する二値分類器(ロジスティック回帰)から構成されている.

分類器の素性として,文の長さ(SLEN, SLEN2),文の位置(TLOC, CLOC),発話された時間(TPOS1, TPOS2),発話前後の空白時間(SPAU, PPAU),発話者の発話の多さ(DOM),現在の発話者が会話を始めたかどうか(BEGAUTH),特定の発話者もしくは発言ターンで頻繁に用いられている語を重視する重み付けで文のスコアを計算したもの(MXS, MNS, SMS, MXT, MNT, SMT),直後の発話内容との類似性(COS1, COS2),会話全体との類似性(CENT1, CENT2),エントロピーに基づく重み付け(THISENT, PENT, SENT)を用いている.

Topic-Driven Multi-Document Summarization with Encyclopedic Knowledge and Spreading Activation

Vivi Nastase. Topic-Driven Multi-Document Summarization with Encyclopedic Knowledge and Spreading Activation.

本論文は,Document Understanding Conferences (DUC) のquery-focused summarizationタスクのように,要約対象文書集合と検索欲求が与えられているとき,その検索欲求に含まれるエンティティに関連するエンティティを収集し,検索クエリ拡張を行う手法を提案している.クエリ拡張のためのリソースとして,WikipediaとWordNetを比較している.

Wikipediaを用いたクエリ拡張では,検索欲求に含まれるエンティティをタイトルに含むWikipedia記事を検索し,その記事の最初のパラグラフに含まれるアンカーテキストを,拡張されたクエリと見なし,文書を収集する.収集された文書に対して,係り受け解析を行い,ノードを語,エッジを係り受け関係としたグラフ上で,PageRankアルゴリズムを適用し,活性値の高い語を拡張トピック語として取り出す.重要文抽出では,トピック語,拡張クエリ語,拡張トピック語,係り受け関係に関するスコアの和を,文のスコアとしている.

Next »