ウェーブレット木の世界

岡野原 大輔

2013-01-09 20:43:44

岡野原です。ウェーブレット木の解説を統数研チャンネルにて行いました。

統数研チャンネル(プレミアム会員ならしばらくタイムシフト視聴可能)。

ウェーブレット木は万能のデータ構造であり、系列データ、全文検索、グラフ、二次元情報、フィンガープリントなど様々なデータに対して多くの操作をサポートします。

本解説では大規模データの背景、ウェーブレット木の作り方、使い方、様々なデータへの適用、最前線(ウェーブレット行列)などを紹介しています。本解説は拙著「高速文字列解析の世界」とあわせてみていただけたらと思います。

NIPS2012に行ってきました

preferred

2013-01-08 10:57:31

先日、NIPS (Neural Information Processing Systems)という学会に参加してきました。今回はその報告です。

続きを読む »

機械学習と自然言語処理とビッグデータ

岡野原 大輔

2012-12-25 11:06:59

岡野原です。

情報処理学会主催の連続セミナー「ビッグデータとスマートな社会」での機械学習の回、自然言語処理の回での講演資料を公開しました。

今年はビッグデータという言葉が広まったということで、このテーマで話す機会が多かったです。今はビッグデータというとそれを支えるインフラ、クラウド、DBなどがまず注目されていますが、我々としては実際それを使って何をするのか、何が実現できるのかというところを注目しています。

PFIは元々こうしたデータを分析して価値を提供する(検索エンジンとかもその範疇に入ると思います)ことをずっと続けてきたわけですが、ビッグデータという言葉が広まってくれたおかげでこの考えがより受け入れられ様々な業界の方と随分と話がしやすくなったと思います。

以下の講演資料では、今ビッグデータの中でも機械学習と自然言語処理の分野において我々がどこに注目しているのかを話をしました。

bigdata2012ml okanohara from Preferred Infrastructure Inc,
  • リアルタイム分析が重要な事例の紹介、
  • それを支えるオンライン機械学習の多値分類の技術例
    (昨年のIBIS2011のチュートリアルからの抜粋、雰囲気がわかれば)
  • 大規模リアルタイム解析Jubatusについて

bigdata2012nlp okanohara from Preferred Infrastructure Inc,
  • 自然言語処理を取り巻く世界の変化(多言語化・大規模リアルタイム化)
  • 情報フィルタリングの重要性の増加
  • 業界における自然言語処理
  • 次の自然言語処理を支えるツール

Compressed Permuterm Index: キーワード辞書検索のための多機能&省メモリなデータ構造

maruyama
リサーチャー

2012-11-06 14:00:23

はじめましてこんにちわ。
4月からPFIで働いているまるまる(丸山)です。最近のマイブームはスダチです。
リサーチブログの更新が再開されたので、私も流れに乗って初ブログを書いてみようと思います。

今回は社内の情報検索輪講で少し話題にあがったCompressed Permuterm Indexを紹介したいと思います。

続きを読む »

Burrows Wheeler TransformとLF mapping

preferred

2012-11-02 13:12:58

最近オープンウォーターダイバーのライセンスを取りました。徳永です。

今日はBurrows Wheeler Transform(BW変換もしくはBWT)の逆変換において用いられるLF mappingを説明します。

続きを読む »

ニューラルネットの逆襲

岡野原 大輔

2012-11-01 16:37:03

岡野原です。Deep Learningが各分野のコンペティションで優勝し話題になっています。Deep Learningは7、8段と深いニューラルネットを使う学習手法です。すでに、画像認識、音声認識、最も最近では化合物の活性予測で優勝したり、既存データ・セットでの最高精度を達成しています。以下に幾つか例をあげます。

続きを読む »

中心性:始まりから最近まで

preferred

2012-03-14 19:35:26

PFI に入社して二ヶ月ちょっとの伊藤です。

ソーシャルネットワークサービスが一般的になるにつれ中心性という概念が注目されてきました。情報科学を専攻されている場合、Google PageRank や HITS アルゴリズムで算出されるグラフの節点に付与される重要度と言うと分かりやすいとのではないか思います。呼び方こそ違いますが、この中心性と重要度は同一の概念、つまりグラフの節点に重み(点数)をつける尺度として知られています。以下、PageRank とHITS が提案された論文です。

続きを読む »

Tree Edit Distanceと自然言語処理への応用

海野 裕也
リサーチャー

2012-02-13 20:25:22

海野です。ちょっと時間があいてしまいましたが、昨年の12月に開催されたNTCIR-9という会議のRecognizing Inference in TExt (RITE)というタスクに、前職の方々と共著で出場しました。

Syntactic Difference Based Approach for NTCIR-9 RITE Task.
Yuta Tsuboi, Hiroshi Kanayama, Masaki Ohno and Yuya Unno. NTCIR-9, 2011. [pdf]

含意関係認識といわれるこのタスクは、大雑把に言うと与えられた2つの文が同じ意味のことを言っているかどうか判定しなさいというタスクです(厳密には一方からもう一方が帰結できるかの判定です)。今日は、その中で使ったTree Edit Distance (TED) について解説します。

続きを読む »

EaselJSでインタラクティブなグラフを描こう

祢次金 佑
エンジニア

2011-12-04 23:35:36

先日、paper.jsによるグラフ描画について触れましたが、今回はflashのようにcanvasを使うことのできるJavascriptライブラリ「EaselJS」を使ったグラフ描画について少しご紹介したいと思います。

EaselJSでは、ShapeやBitmap、TextといったDisplayObjectをStageにaddChildしてディスプレイリストを作ることで、Stageに紐付けられたcanvasにその内容が描画されます。 ActionScriptに慣れている開発者には馴染みやすいやり方です。onClickなどのイベントハンドラもDisplayObjectごとに設定することができ、アニメーションも勿論可能。

<!DOCTYPE html>
<html>
  <head>
    <script type="text/javascript" src="easel.js"></script>
    <script type="text/javascript">
      window.onload = function() {
        var canvas = document.getElementById("myCanvas");
        var stage = new Stage(canvas);

        var shape = new Shape();
        shape.graphics.beginFill('#f00').drawCircle(100, 100, 100);
        stage.addChild(shape);

        var label = new Text("hoge", "30px Arial", "#000");
        label.x = 70;
        label.y = 110;
        stage.addChild(label);

        stage.update();
      };
    </script>
  </head>
  <body>
    <canvas id="myCanvas" width="300" height="300"></canvas>
  </body>
</html>

先日の記事と同様、クリックに反応する棒グラフを実装してみました。見た目にはほとんど変わりませんが、EaselJSで実装しています。

bar graph using EaselJS – jsdo.it – share JavaScript, HTML5 and CSS

paper.jsと同じく、プロジェクトサイトにはデモやAPIドキュメントが揃っています。(冒頭の画像はEaselJSによるgameデモのスクリーンショットです。)

文書解析のための簡潔データ構造

岡野原 大輔

2011-12-02 18:41:30

岡野原です。

12/1〜12/2に高松で開催されたALSIP2011で文書解析のための簡潔データ構造の最近の進展について話をしてきました。

ここの業界の進展は速く毎年様々な方法が出てきますが、要点だけを上げると

– Wavelet Treeがアルファベットサイズが大きい場合のRank/Select操作だけではなく、2D矩形探索、最頻要素列挙など様々な問題を効率的に解けることが分かってきて非常に重要なデータ構造であることが分かってきた。2D探索も、もはや数億 x数億とかでも解けてしまうので2D探索を利用するような様々な手法が全部現実的になった。

– Top-K Queryが盛り上がっている。検索などデータ構造に問い合わせをする際に、該当する結果を全部を列挙することの高速化は理論的にも難しいが、スコアが高い順(例えばterm frequencyやPageRankなど)にk個だけ列挙するだけなら非常に高速にできる。この場合も大体Wavelet TreeのGreedy Searchが使われるが、Top-Kを効率的に実現するためのデータ構造(グリット上の優先度付キュー)も研究が盛ん

– CFG (Straight Line Program)をベースにしたGrammer Compressionが実用的になって、いろいろなところで使われ始めている。元々Navarroらのグループが多く利用していたRePairだけではなく、九大の研究グループが中心となってやっている方法などはかなり実用的になってきた。現実的な時間での文法抽出だけでなく、抽出した後のデータに対する簡潔データ構造表現も盛ん。

ちなみに高松ということで、ご飯は、うどん、うどん、鍋+うどん、徳島ラーメンでした。