DO++ : 線形識別器チュートリアル
ワークショップ中の夕食で話したのですが、今のところ日本で（素性関数ベース＆線形識別器）機械学習のいろいろな手法をまとめて体系的に教えてる資料などがあまりないなぁという話をしていました。 で、探すと、このあたりの大部分をまとめて説明しているいいチュートリアル（英語）がありました。 夏の学校資料[pdf] その他のコードやリンク ちょっとだけ解説 現在自然言語処理の多くで使われている学習器は線形識別器です。 入力x（例：単語、文、文書）から出力y（例：品詞、品詞列、文書のトピック）を予測したいという場合は、(x,y)のペアからいろいろな値を取り出し（x,yのペアから値を取り出す関数を素性関数と呼ぶ）、その値を並べたベクトルを素性ベクトルと呼び、f(x,y)とかきます。そして、その素性ベクトルf(x,y)と同じ次元数を持つ重みベクトルwとの内積を測って、その値が正か負か、または大きいか小さいかを
博士生活振り返り - DO++
ずっとドタバタしていたのですが、ようやく新しい生活のリズムがでてきました。 無事、情報理工学の博士号を取得して卒業し、4月からPreferred Infrastructureでフルタイムで働いています。 研究方面からのお誘いもいろいろあったのですが、会社一本に専念しております。 ただ、研究活動はこれからも会社のバックアップのもとしていきます。 また、3月に結婚もしました。 年明けから博士卒業、結婚の二本柱に加えてNLPチュートリアル、会社の仕事とテンパってました。 なんとか体を壊さず乗り越えられたのはみなさんの助けです。 しかし、喉元過ぎると熱さ忘れるという言葉通り、「これはもうだめだろう」と追い詰められていた時の気持ちを既に忘れつつあります。 誰かの参考になるかもしれませんので、この時の気持ちも含め博士３年過ごして感じたことや、研究の話とかを思い出せる範囲で書いてみます。 --- 私が修
DO++: AND検索の最尤推定
検索技術においてAND検索、つまり二つの単語を指定して、それが両方出現している文書数の推定を高速に行うのは難しい問題です。 問題を正しく書くと単語w_xが出ている文書番号(x1,x2,x3,..,xn)とw_yが出ている文書番号(y1,y2,y3,...,ym)が与えられたら | {(i,j)|x_i = y_j} | の数を求める問題です。 これは前もって全通り求めて保存しておくにも単語種類数の二乗のオーダー分必要なのでできません。 これは機械学習でも特徴関数が0/1の値しかとらないとき、二つの要素の特徴ベクトルの内積を求める問題と同じで、またデータベースでもJOINの順番を決めるときにでてくる問題です。 普通は全体の文書からサンプルをとって、その中で数えてみて、それを元のサイズにスケールさせることをします。例えば全体文書1億件の中から文書1000件だけとってきて、その中でw_xとw_y
SODA2010 ALENEX2010＠テキサス - DO++
先日までTexas Austinで開催されていたALENEX2010とSODA2010に参加してきました。 一緒に行った吉田さんの感想もありますのでそれも参照してください まず一応自分のALENEXでの発表資料は以下にありますので参照ください "Conjunctive Filter: Conjunctive Filter: Breaking the Entropy Barrier"論文、発表スライド(pptx pdf) 他に聞いた中で印象的だったものを下に書いてみます。ただ、大部分の発表は私の基礎知識が足りなくてついていけませんでした。残念 昨年末の研究開発セミナーでも紹介しましたが、簡潔木とよばれる限界まで圧縮した上で（ノード数がnの時2n+o(n) bit）様々な木上での操作（親を辿る、子を辿る、共通祖先を探すなど）のあらゆる操作を統一された操作の組み合わせで実現するというものの理論的
PFIセミナー資料: 研究開発2009 - DO++
昨日ありました、PFIでのセミナーでの発表資料です。 研究開発のチームの紹介の後に、2009年サーベイした論文の中で面白かった論文を 機械学習、データ構造、画像処理で紹介してます 紹介した話は - Multi-class CW (Multi-class Confidence Weighted Learning,) - AROW (Adaptive Regularization Of Weight Vector) - Online-EM algorithm - 全備簡潔木 (Fully-functional Succinct Tree) - 圧縮連想配列 (compressed function) - PatchMatch です。 ＃資料中の簡潔木の表現方法のDFUDSの紹介でtxも使用と書いてあるのは、公開しているtxでは、 LOUDSのみをつかっていますので正確ではありませんでした。これ
トーナメントと多値分類 - DO++
今やってる研究で、トーナメント問題を調べる機会がありました。 トーナメントは私も知らなかったのですが、勝者や順位を決める方式のことを指し、いわゆる二人ずつ戦って生き残っていく方式はノックアウトトーナメントといわれるそうです(wikipedia)。 ＃10000人戦う時にノックアウトトーナメントでは何回試合が行われるかというのはよくある質問ですね。 で、このトーナメント方式というのは調べてみると非常に様々なものがあります 例えばスイス式トーナメントは、最初はランダムな組み合わせで対戦、次は勝者同士と敗者同士、その次は全勝・１勝１敗・２戦全敗のそれぞれが・・というふうに同じ成績の人同士で戦う方式です。レーティングを計算して、レーティングが近いもの同士を戦わせるような拡張もあります。近いのは将棋でやってるようなものですね。 利点は全ての人が同じ試合数で戦い、また厳密な順位が決めやすいことがありま
連想配列の進化 - DO++
キーに対して値を結びつける連想配列は多くのアプリケーションの肝であり、コンパクトかつ高速な処理が可能な連想配列を追い求め日夜研究が進められています。 特に非常に巨大な連想配列を高速に処理するというのが重要な課題となっています。例えば、音声認識・文字認識・機械翻訳などで使われている言語モデルでは、非常に大量のN個の単語列の情報（特に頻度）を格納することが重要になります。 この場合、キーが単語列であり、値が単語列のコーパス中での頻度に対応します。 例えばGoogle N-gram Corpusからは数十億種類ものN-gramのキーとその頻度などが取得できます。これらを主記憶上に格納し、それに関する情報（頻度や特徴情報）を操作することが必要になります。 そのほかにも大規模なデータを扱う問題の多くが巨大な連想配列を必要とします。 ここではこのような連想配列の中でも、キーの情報を格納することすら難し
全文検索エンジン Miniseをリリース + WEB+DBで全文検索の特集記事 - DO++
全文検索エンジンの Minise: MIni Search Engineをリリースしました． このエンジンは全文検索の基本的な機能をサポートしたもので，索引手法は逐次検索（索引無），N-gram，転置ファイル，接尾辞配列をサポートしており，そこそこ最適化を行ってます．Wikipedia日本語版を実験で使ったもので20万文書で構築時間が500秒前後，検索時間が一クエリあたり数msとなっています． BSDライセンスで公開しています． 割りきって，機能を絞ってシンプルな構成にしていますので改造したりしやすいようになっています。まだ、ドキュメントはないですが、C++ APIとして利用しやすいようにもなっていますので、研究用途などで新しい索引やランキングとかでの利用も想定しています（実際に研究用で使ってます）． --- 今回の全文検索ライブラリを開発する機会になったのが，私が担当した今月号のWEB+
天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
SPIRE2009 - DO++
フィンランドのサーリセルカという場所で開催されたSPIRE2009で発表してきました。 サーリセルカは北極圏で、百夜ではなかったですが夜暗くなったのは４時間ぐらいでした。天候が悪く残念ながらオーロラはみれませんでした。トナカイを見て、トナカイを食べてきました。 エクスカーションでイナリというところにいき、またワークショップの後に山にハイキングに行きました（ハイキングといっても６時間ぐらい歩く結構本格的なもの）。誰も声を出さないと耳がおかしくなるくらいの無音になるとにかく静かなところでした。冬に行くとクロスカントリーとかが楽しいらしい。 聞いたメモ - "Novel and Generalized Sort-based Transform for Lossless Data Compression", Kazumasa Inagaki, Yoshihiro Tomizawa, and Hid
netflix prize is over, 時間経過による嗜好性の変化 - DO++
米国のオンラインDVDレンタルサービス「Netflix」が、現在利用しているレコメンデーションシステムの性能をはじめに10%改善したチームに100万ドルの賞金を与えるという触れ込みで始まったnetflix prizeは当初の予想よりも時間がかかったが、つい最近最初からトップを走り続けていたbellkorと、上位陣のコラボレーションのチームが10%の壁を破った（leaderboard）。 彼らの手法は「非常に多くの様々な種類のレコメンデーションシステムの結果を混ぜ合わせる」という愚直だがいかにも精度が出そうだという方法を採用している（、と昨年度の結果からは思われる。近々詳細は出るだろう。） 実際に使ってとどめになったかどうかは分からないが、彼らのチームの主要メンバーがKDDで新しい手法を発表しており、単一の手法による最高精度を達成している。ちなみに今年のKDD（データマイニング系の学会の最高
Burrows-Wheeler変換の線形時間アルゴリズム - DO++
研究紹介です。今夏のSPIRE 2009という学会で "A Linear-Time Burrows-Wheeler Transform using Induced Sorting", D. Okanohara, K. Sadakane, SPIRE 2009 pdf(draft) というのを発表します。これは与えられた文字列に対し接尾辞配列を経ないでBurrows-Wheeler変換を直接行うというもので、アルファベットサイズによらず入力長に対して線形時間で行えます。基本的なアイディアは昨年のInduced Sortingによる接尾辞配列の線形時間構築アルゴリズム（いわゆるSAIS）を接尾辞配列を使わないでシミュレートするものです。pushとpop操作だけからなり、そのまま外部記憶上での構築とかにも対応できるようになっています。 Burrows-Wheeler変換（BWT, Block S
NAACL/HLT 2009報告 - DO++
コロラド・ボルドーで開催されたNAACL/HLT 2009に行ってきました。 NAACLは自分の中での分類では自然言語処理の学会で統計的な手法とかが多い学会に思える（それに対しヨーロッパではEACLでは文法とか言語理論とかが多い）。比較的自分にあう学会。 開催地となったコロラド大ボルダー校はとてもきれいなキャンパスで（、「全米で最も美しいキャンパス」の4位にランキング）、宇宙飛行士をたくさん輩出してたり、ノーベル物理学賞を４名輩出するなど、研究レベルも高いそうです。 で、学会は適当に休みながらまったり聞いていたのですが全体的に教師無学習に関する話が多かったような気がします。教師有学習による言語処理がある程度成熟してきているのに対し、教師無の方はまだまだ伸びしろが多いので研究がしやすいのでしょう。教師無に利用するモデルも、単純な混合分布から、様々な分布が入り乱れる複雑なグラフィカルモデルにな
DO++: 海外のブログのお勧め
海外のブログでお勧めはどういうのありますかとよく聞かれるのでかいてみます。 といってもそんなないけど。 Terence Tao 非常に幅広い分野の第一線で活躍している数学者のテレンスタオ[jawiki]のブログ．ブログで毎回新しい定理を証明しちゃったり、突然、相対性理論の分かりやすい証明をしたりとすごい．コメントでの議論も丁寧． ブログで書いたのをまとめた本が出るそうですが、目次を読むとブログ本の範疇をこえてる・・ natural language processing blog 自然言語処理ではたぶん一番有名なブログ. による．いろいろな手法の解説から現在ある問題（自然言語処理以外にもアカデミック的な問題とかも含め）．守備範囲が大体私と似ていて読んでいて楽しい．ちなみにHal Daumeはハスケラーで、そこそこ有名なhaskel tutorialかいてたりする Google Resear
自然言語処理の学会 - DO++
プログラミング言語の学会に触発された作った。私視点で書いたので、間違ってたりしたら突っ込んでください。 自然言語処理は、情報検索、ウェブ、機械学習とかとの境界領域だったりするのですが、そういうのは除いてます。 大体の学会情報はACL wiki 論文はACL anthology から得られると思います ACL The Association for Computational Linguistics ACL2008 自然言語処理の一番でかい会議。理論からアプリケーションまで何でも集まるが、強いて言えば 機械翻訳、構文解析が多い。いろいろなワークショップ（１０ぐらい）も併設される。 EMNLP Conference on Empirical Methods in Natural Language Processing EMNLP2008 言語情報から統計的な情報を取り出して機械学習を使って自然
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
大規模データを基にした自然言語処理 - DO++
人工知能基本問題研究会 (SIG-FPAI)でタイトルの題目で一時間ほど話してきました。 発表資料 [pptx] [pdf] 話した内容は - 自然言語処理における特徴ベクトルの作り方と、性質 - オンライン学習, Perceptron, Passive Agressive (PA), Confidence Weighted Learning (CW) 確率的勾配降下法 (SGD) - L1正則化, FOLOS - 索引を用いた効率化, 全ての部分文字列を利用した文書分類 で、スライドで70枚ぐらい。今までの発表とかぶっていないのはPA CW SGD FOLOSあたりでしょうか オンライン学習、L1正則化の話がメインになっていて、その両方の最終形の 確率的勾配降下法 + FOLOSの組み合わせは任意の損失関数に対してL1/L2正則化をかけながらオンライン学習をとても簡単にできるという一昔前
DO++: いろんな学会
ICML/UAI/COLTのaccepted paperが出揃い、ざーっと面白そうなのを片っ端から読んでみました。 ICMLの読んでみた、読んでみたいリスト そのうちピックアップします。 ICMLは強化学習系が多くなっているなぁという気もしたのですがそうでもないかな。 ついでに、私が興味を持ってみている機械学習の学会（と一個ジャーナル）紹介を。これも境界領域なので他の学会で面白い話が発表されたりすることも多いです。 機械学習系 JMLR Journal of Machine Learning Research 機械学習の一番メジャーなジャーナルで出るスピードも速い（その年に学会発表されたものがその年のうちに出てくることも珍しくない）。全部web上からタダで論文を落とせる。よいですね ICML International Conference on Machine Learning 機械学習
昨年の論文をふりかえる - DO++
新年すっかりあけてました。 今年もよろしくお願いします。 年末年始はドタバタして昨年を振り返られなかったのですが、せっかくなので2008年に読んだ論文で私個人のベスト５を以下に列挙してみます。 D. Sontag, et. al. "Tightening LP Relaxations for MAP using Message Passing", UAI 2008 [pdf] Graphical ModelのMAP推定問題で従来解けなかった規模の複雑さの問題を高速にしかも最大であるという保障付きで解けるようにした。書いたメンバーはこの問題に関するオールスターのような感じ。解く問題は、n個の頂点からなるグラフで、各頂点には変数x1...xnがついていて、各頂点と各枝に対し関数gi(xi)、gij(xi,xj)が与えられた時、∑i gi(xi) + ∑ij gij(xi,xj)が最大となるよう
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
大規模文字列解 析の理論と実践＠IBISML - DO++