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

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だけではなく、九大の研究グループが中心となってやっている方法などはかなり実用的になってきた。現実的な時間での文法抽出だけでなく、抽出した後のデータに対する簡潔データ構造表現も盛ん。

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

オンライン凸最適化と線形識別モデル学習の最前線

岡野原 大輔

2011-11-11 23:54:13

岡野原です。

今日まで奈良女子大で行われていたIBIS2011で表題についての講演をしてきました。

続きを読む »

和と極限を交換したい時に用いる定理

大野 健太
エンジニア

2011-10-24 18:46:01

(読んでいただいた方からの指摘を受けて訂正しました.またtwitterでも感想や指摘を頂きました.ありがとうございます.)

はじめに

 こんにちは,大野(@delta2323_)です.今日はルベーグの収束定理についてお話をしたいと思います.

続きを読む »

averaged stochastic gradient descentのご紹介

preferred

2011-10-20 18:07:58

そろそろ寒くなってきましたね。早速風邪を引きました。徳永です。

今日は私の使っている自作の足置き(制作費600円)の紹介でお茶を濁そうと思っていたのですが、途中で方向転換しました。今日は機械学習の話をします。

Léon Bottouという研究者(彼はまたDjVuというドキュメントフォーマットの開発者でもあります)が開発・公開しているsgdというソフトウェアのバージョン2.0が公開されました。sgd 2.0ではaveraged stochastic gradient descent(ASGD)という手法が実装され、これまでのSGDと比べて性能が向上しました。今日はこのASGDを紹介したいと思います。日本語に訳すと平均化確率的勾配降下法でしょうか。漢字が多くて読みづらいので以下ではASGDと呼びます。

続きを読む »

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

祢次金 佑
エンジニア

2011-10-11 15:20:21

canvasベースのベクターグラフィクス描画用jsライブラリとして、既に各所で紹介されているpaper.jsですが、これを、ウェブに載せるグラフの描画に使ってみましょう、というお話です。

続きを読む »

機械学習の数学記号に慣れる ー初めの一歩で躓かないためにー

大野 健太
エンジニア

2011-09-29 21:32:15

 初めまして,大野と申します.今回から自分もリサーチブログを書く事になりました.これを期に定期的に投稿が出来ればと思っています.

続きを読む »

研究・企業・生き方について – 情報科学若手の会2011

岡野原 大輔

2011-09-19 12:59:00

岡野原です。

2011/9/17〜2011/9/19に熱海で行われた情報科学若手の会2011に参加し、講演をしてきました。
テーマを決めるに当たって、参加者の年齢、興味分野、スキルの幅が非常に広いということもあり、若手の会参加者のみなさんから質問を前もって聞いておき、それについて回答するという形にしました。
続きを読む »