研究紹介 - SketchSort（スケッチソート）法 - Yasuo Tabeiの日記
SketchSort(スケッチソート)法の論文が ACML2010にアクセプトされました。今年も採択率30%の難関でした。 http://sugiyama-www.cs.titech.ac.jp/ACML2010/ Yasuo Tabei, Takeaki Uno, Masashi Sugiyama, Koji Tsuda: Single Versus Multiple Sorting in All Pairs Similarity Search, The 2nd Asian Conference on Machine Learning (ACML2010), Tokyo, Japan, 2010. Link to the paper SketchSort法は、データー点の集合が与えられたら、集合中の２点間の距離がある閾値以内のペアー(近傍ペアー)を全て求める問題(全点間類似度検索)を高速
はじめてでもわかるベイズ分類器 －基礎からMahout実装まで－
This document discusses Mahout, an Apache project for machine learning algorithms like classification, clustering, and pattern mining. It describes using Mahout with Hadoop to build a Naive Bayes classifier on Wikipedia data to classify articles into categories like "game" and "sports". The process includes splitting Wikipedia XML, training the classifier on Hadoop, and testing it to generate a co
行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
Consistent Hashing を試す
Consistent Hashing は、 複数のノードにレコードを分散させる方法として、 Amazon Dynamo や Cache::Memcached::Fast などで使われているアルゴリズムです。 この文章では、Perl で実際に Consistent Hashing を実装し、 その特徴を理解することを目的とします。 更新履歴 2008-06-01: 公開 サーバー台数で割った余り (mod) を使用する まず Consistent Hashing と比較するために、レコードに対して整数のハッシュ値を求め、 ハッシュ値をノード数で割った余り (mod) で、ノードを選択するという方法を書いてみます。 ここでは、ハッシュ値の算出に CRC (Cyclic Redundancy Check) を使用しています。 use strict; use String::CRC; use Pe
第3回 ベイジアンフィルタを実装してみよう | gihyo.jp
さらに詳細な利用方法が知りたい方は、Yahoo!デベロッパーズネットワークのマニュアルを参照してください。 ベイジアンフィルタの実装 ここから本格的にベイジアンフィルタの実装に入っていきます。 その前に、まずは先程のリスト1のコードを利用して入力された文章をわかち書きし、単語の集合を返す関数を作成しnaivebayes.pyとして保存しましょう。こちらも先程のmorphological.pyと同様にutf-8で保存してください。 リスト2 文章の分割をする関数（naivebayes.py） # -*- coding: utf-8 -*- import math import sys #yahoo!形態素解析 import morphological def getwords(doc): words = [s.lower() for s in morphological.split(doc)
リンク解析とか: 重要度尺度と von Neumann カーネル - smly’s notepad
NAIST の入学手続を終えた. 残りの期間はサーベイするぞーということで shimbo 先生の講義資料「リンク解析とその周辺の話題」を読んでいます. 一日目, 二日目の資料は PageRank, HITS, SALSA などの重要度尺度の紹介と, von Neumann Kernels と HITS の関係についてのお話が中心. これらを実装してみた. 後半に進むほど力尽きて記述が適当になってます:)PageRankポイントはランダム遷移行列による random walk では定常分布に収束しない (エルゴード性 (ergodic) を満たさない) という点. どうして満たさないかというと. sink (出次数のない節点) が存在するとき, 明らかに既約 (irreducible) でないのでエルゴード性を満たさない. 複数の強連結成分を持つケース => 周期性を持つと考えてよい? 周期
Suffix Array向きのソートアルゴリズム - EchizenBlog-Zwei
Suffix Arrayのソートアルゴリズムは以前当ブログで紹介したSAIS(参考)など、Suffix Arrayの性質を生かしたものが多い。そして一般にSuffix Arrayはバイト単位でインデックスを与えるので、これを前提としている場合が多い。大抵の場合はそれでOKなのだが、問題がある場合がある。 それは、インデックスをUTF8の文字単位で与えたい場合や、単語単位で与えたい場合。この場合、大抵のSuffix Array向けソートアルゴリズムが使えない。そこで重要になってくるのが文字列に対する高速ソートアルゴリズム。これならばインデックスが飛び飛びでも使えるので汎用性がある(Suffix Arrayに特化した手法が使えないので速度面では劣るかもしれないが。) 例えば、SUFARY(参考)で使われているmultikey-qsortという方法は古くからある方法だがシンプルかつ高速で、とても
Hadoopを使わずにWikipediaのテキスト処理を400倍高速化 - tsubosakaの日記
タイトルは釣りです。id:mamorukさんの書いたHadoop で Wikipedia のテキスト処理を900倍高速化 - 武蔵野日記を読んで、そもそも1G程度のデータの単語頻度を数えるのに858分もかかるんだっけと思い、id:nokunoさんの資料を読んでみると単語頻度を求める際に a b a aみたいなデータを a 3 b 1に変形するのにsortしたファイルをuniq -cで処理するということをやっていた。これはあまり効率のよい方法ではなくて行数をNとしたときにO(N log N)の計算時間となる(文字列比較はO(1)でやれることにする)。 これに対して、単語の頻度をハッシュ表で保存すると理想的な条件の元ではO(N)の計算時間で頻度を求めることが出来、より高速に計算することが可能となることが期待される。 また、単語数をWとしたとき、C++のmapのような二分探索木を使ってもO(N
動的計画法を学ぶリソース・練習問題まとめ - フリーフォーム フリークアウト
移転しました http://please-sleep.cou929.nu/20100708.html
Micterの単語分割部の高速化を試してみた結果 - sileのブログ
tkngさんが作成したMicterという単語分割器の分割部を高速化できるような気がしたので試してみた。 そのメモ。 試した結果のソース一式はmimicという名前でgithubに保存しておくことにする*1。 結果 まず、結果から*2。 # 分割対象のテキスト(のサイズ) $ ls -lh /tmp/test.data -rw-r--r-- 1 user user 41M 2010-07-05 22:48 /tmp/test.data # MeCab $ time mecab -Owakati /tmp/test.data > /dev/null real 0m10.843s # 10秒 user 0m10.777s sys 0m0.068s # Micter $ ls -lh micter.model -rw-r--r-- 1 user user 1.8M 2010-07-06 08:30
オープンソースとアルゴリズムの特許 - ny23の日記
GPL で公開していた構文解析ライブラリで実装していたアルゴリズム（の一つ）について，特許が出ているという指摘を受けたので，GPL で公開するのは不適切だと判断して，当該アルゴリズムの実装を取り除いた．このアルゴリズムは，同じくオープンソースな解析器 (LGPL/BSD) でも実装され公開されていたので，すっかり ok だと油断していた．確かに企業研究者の提案手法なので，特許が取られている可能性は頭の隅にはあったのだけど，それにつけても非常に残念だ．今回のアルゴリズムは，かんたん特許検索で提案者名を入れてもそれこそ「かんたんに」出てくるので，自分自身の過失だろう．が，それで済ませていいのだろうか．[最後にオチあり] 以前，Bayesian Setsの特許について - のんびり読書日記 を読んだ時も思ったけど，アルゴリズム（あるいはソフトウェア）の特許というのは，オープンソース開発者にとって
ナイーブベイズを用いたブログ記事の自動分類 - 人工知能に関する断創録
カイ二乗値を用いた特徴選択（2010/6/25）の続きです。今まで使ってきた20 Newsgroupsというデータは英語文書でかつ元ネタがよく分からずあまり面白くなかったので、今回はこのブログ（人工知能に関する断想録）の記事を分類してみます。このブログの各記事には私の判断でカテゴリをつけています。たとえば、この記事は[機械学習][自然言語処理]です。カテゴリのリストはこのブログの左メニューにあります。この前、少し整理したので全部で18のカテゴリがあります。新しい記事を書いたとき自動でカテゴリを割り振ることはできるのでしょうか？ （注）プログラミング言語はPythonを使っています。シリーズもので以前作ったコードを再利用してるので検索で飛んできた人はナイーブベイズを用いたテキスト分類（2010/6/13）から順に読んでください。 はてなダイアリーデータのダウンロードと整形 まず、はてなダイア
基本となるDoubleArrayの実装 - sileのブログ
各種アルゴリズムを試す際のベースとなるような(シンプルな)DoubleArrayが欲しくなったので作成した。 構成など 多分、DoubleArrayとしては一番単純な構成*1。 ※ 以下で云う"ノード"は、"ノードのインデックス"の略のような意味合い 静的構築 各キーを改行区切り('\n')で保持するソート済みのファイルを入力に取り、DoubleArrayを構築する BASE配列とCHECK配列から成る BASE配列: 遷移情報およびキーのIDを保持する配列 BASE[ノード] = 遷移のベースとなるノード => 遷移先ノードは、BASE[ノード] + 遷移文字、で求める BASE[ノード]の値がマイナスの場合は、キーの終端を意味し、そのIDが格納されている => キーのIDは、BASE[ノード] x -1、で求める CHECK配列: 遷移の正当性をチェックするための配列 CHECK[ノー
パターン認識に関する公開プログラム
宇野毅明と有村博紀による公開プログラム（コード） このページでは、公開しているプログラムのコードがダウンロードできます。主に、列挙アルゴリズムやデータマイニングに関するものです。全て、宇野毅明、あるいは、良く一緒に研究をしてお世話になっている北海道大学の有村博紀先生によって作られたものです。各プログラムに使用言語とコード作成者が書いてありますので、質問、あるいはバグの報告などは、作成者にご連絡ください。宇野毅明は uno@nii.ac.jp、有村博紀先生は arim@ist.hokudai.ac.jp です。 !!! コードの最近のバージョンに、マッキントッシュのフォーマットではエラーが出るというバグがありました。現行バージョンではこのバグは治っています。 LCM (Linear time Closed itemset Miner) ver.2 (C言語、宇野毅明) [文献 1]
無題ドキュメント
次に、各Suffixにおける大小関係を定義します。この大小関係は辞書式順序です。辞書式順序とは、辞書に並んでいる通りの順番であり、簡単に言えば、 (1)両Suffixを頭（左）から順番に一文字ずつ比較していき、初めて違うところで、文字の大小関係で比較を行う (2)もし、二つを比較していき、片方のSuffixが終わりに達してしまったら、そちらの方が小さいと定義する。 例えば、(1)は上の例でいえば、 S5 と S7を比較するとすると S5 adabra S7 abra 一文字目は両方ともaで、同じなので二文字目（赤い部分）を比較すると、dとbであり、文字の大小関係で d > b なので S7 < S5 という大小関係がつきます。 (2)については、S0 と S7を比較すると S0 abracadabra S7 abra で、頭から4文字は同じであり、S7はデータの最後に達しました。この
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
特異値分解とLSIの意味 - あらびき日記
CiNii 論文 - アニメにおける人物顔画像の萌え因子特徴評価と検索分類システムへの応用(ITS画像処理,映像メディア,視覚および一般)
Larsson Sadakane
two-stage (二段階ソート法）
サービス終了のお知らせ