この記事は abicky.net の HMM, MEMM, CRF まとめ に移行しました
以前縁あって小町さんと一緒に仕事をさせてもらい論文に名前を載せてもらったのですが、会社だけでなく自宅でもちょっと使いたいなーということもあり、実装してみることにしました。 参考にしたのは以下の論文です。 ラプラシアンラベル伝播による検索クリックスルーログからの意味カテゴリ獲得 元論文と違うのは、インスタンス-パターン行列の要素を単純な頻度から別の尺度に変えている点です。 元々そのまんま実装してみたところ、非常にレアな場合なのですが、ジェネリックパターン1つのみと共起するようなインスタンスがあった場合に、これが上位に出やすくなるという問題が発生し、どうにかできないかなと模索していたところ、小町さんからアドバイスを頂き、それを基に手を加えています。 とりあえず動作検証のためにMovieLens Data Setsを使って実験してみました。 最初にデータのフォーマットをツールの入力形式へ変更。
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
動的計画法の説明は常に再帰関数で書き表すことにしています.いやゆるメモ化再帰です.参照透過な関数は,同じ引数に対して同じ値を返すので,保存しておけばいいという感覚です.計算量の見積もりも簡単で,引数の異なり数に関数中のループの上限をかければおしまいです.特に再帰で書くことに慣れていれば自明に書けますし,テーブルを使ったDPと違って,ループの順番を意識する必要がありません.このテクニックは学部時代に@ohkuraに教えてもらいました.関数型言語に触れた今でこそ当たり前に見えますが,当時は目から鱗だったのを覚えています. メモ化再帰と不動点に関する@kinabaさんの日記や,プログラミングコンテスト的には@chokudaiさんの記事が参考になります. 今更ですが,ちょっと例で説明します.フィボナッチ数を計算する関数fib(x)は再帰式で,fib(x) = fib(x - 1) + fib(x
PCAを試す に続いて確率的主成分分析(Probability Principal Component Analysis)。 解析的に解けてしまって、閉形式の解がわかっているので実装としてはたいしておもしろくない(いや、いいことなんですけどね)。 M <- 2; directory <- "."; argv <- commandArgs(T); if (length(argv)>0) directory <- commandArgs(T)[1]; if (length(argv)>1) M <- as.integer(commandArgs(T)[2]); oilflow <- as.matrix(read.table(sprintf("%s/DataTrn.txt", directory))); oilflow.labels <- read.table(sprintf("%s/DataT
誤り許容カウント法(lossy count method)のサンプルプログラム 2010-05-12-1 [Programming][Algorithm] 1行1ラベル形式で、 1万種類のラベルを持つ、 100万行のデータがあるとします (ラベルの頻度分布はジップの法則にだいたい準拠するとします)。 各ラベルの頻度をハッシュを使ってカウントするとなると、ハッシュエントリ1万個分のメモリ容量が必要になります。(1万じゃたいしたことないな、という人はもっと大きな数に置き換えて読んでください。) しかし、カウント後に高頻度のものしか使わないということも多いと思います。例えば頻度5000以上のもののみ取り出してあとはいらない、とか。 そうなると、全部のラベルのカウントデータを最後まで保持するのは無駄に思えます。 そこで登場するのが「誤り許容カウント法(lossy count method)」。 低
素性選択といえば、古典的な話だが、 最近は冗長性を排除する素性選択というのがちらほら出てきている。 たとえば、素性の数を100個に限定したいとき、 クラスとの相関性(相互情報量など)が大きい順に 上位100個だけ使うというアイデアを思いつくだろう。 しかしこれはうまくいかない、取り出された素性集合間の 相関が強く、冗長性が高いからだ。たとえ100個とれても どれもこれも素性として似ていれば効果がない。 できるだけ異なる観点の素性を集める必要がある。 これは実応用で極めて有効に働く。素性数がすくなければ すくないほど、計算機にやさしいし、速度も高速になる。 できるだけ少ない素性で最大の精度を実現というのは 達成すべきゴールとしても興味深い。 さて、相関性まで注目した素性選択アルゴリズムとしては以下がある。 どれも クラスとの相関性と、素性間の相関性を 見ながら greedy に素性選択を行う
データ構造 Javaを使うなら必ず覚えておきたいデータ構造 - 配列・リスト・マップ PHPなら覚えるべきデータ構造はひとつだけ? - 配列 Perlで覚えたいデータ構造 - 配列・ハッシュ VBAで覚えておくデータ構造 - 静的配列・動的配列・ディクショナリ JavaScriptで覚えておくとよいデータ構造 - 配列・オブジェクト Bashで覚えておくとよいデータ構造 - 配列 - 何かしらの言語による記述を解析する日記 アルゴリズム Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト&マップ編) Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト&ビーン編) PHPを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 VBAを使うなら理解しておきたいアルゴリズム - 抽出・結合・集計 Javascr
overlasting.net 2020 Copyright. All Rights Reserved. The Sponsored Listings displayed above are served automatically by a third party. Neither the service provider nor the domain owner maintain any relationship with the advertisers. In case of trademark issues please contact the domain owner directly (contact information can be found in whois). Privacy Policy
JAVAでデータマイング! 『情報工学の難しいそうなアルゴリズムをJAVAで実装して、ひたすらその結果を公開する』ブログになる予定。 PR Calendar <<April>> S M T W T F S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Theme NaiveBayes ( 2 ) スムージング ( 0 ) はじめに ( 1 ) 計算テクニック ( 0 ) 整数列圧縮 ( 2 ) 外れ値除去 ( 0 ) LSH ( 4 ) 協調フィルタリング ( 0 ) ブースティング ( 0 ) Kmeans ( 0 ) 階層的クラスタリング ( 2 ) EMアルゴリズム ( 0 ) BM ( 0 ) SVD ( 0 ) PLSI ( 0 ) LDA ( 0 ) パーセプトロ
ワークショップ中の夕食で話したのですが、今のところ日本で(素性関数ベース&線形識別器)機械学習のいろいろな手法をまとめて体系的に教えてる資料などがあまりないなぁという話をしていました。 で、探すと、このあたりの大部分をまとめて説明しているいいチュートリアル(英語)がありました。 夏の学校資料[pdf] その他のコードやリンク ちょっとだけ解説 現在自然言語処理の多くで使われている学習器は線形識別器です。 入力x(例:単語、文、文書)から出力y(例:品詞、品詞列、文書のトピック)を予測したいという場合は、(x,y)のペアからいろいろな値を取り出し(x,yのペアから値を取り出す関数を素性関数と呼ぶ)、その値を並べたベクトルを素性ベクトルと呼び、f(x,y)とかきます。そして、その素性ベクトルf(x,y)と同じ次元数を持つ重みベクトルwとの内積を測って、その値が正か負か、または大きいか小さいかを
SMOよりも優れたアルゴリズムにSimple SVMというのがあるそうだ。SSVM : A Simple SVM Algorithmhttp://www.stat.purdue.edu/~vishy/papers/VisMur02b.pdf しかし、このアルゴリズムを理解してC#で実装したいんだけれど、なんだか論文がすごく難しくて挫折を繰り返してしまう。誰か素人でもわかるように教えてください(´・ω・`) 余談だけれど、このSimple SVMとやらは10回以下で収束するって書いてある。オンライン学習というのが研究されているが、オンライン学習はsimple SVMの10倍以下の高速化しか望めないし、解の質もよくわからないということなのかな?
2. はじめに • 「動的計画法」は英語で 「Dynamic Programming」 と言います. • 略して「DP」とよく呼ばれます. • スライドでも以後使います. 4. ナップサック問題とは? • n 個の品物がある • 品物 i は重さ wi, 価値 vi • 重さの合計が U を超えないように選ぶ – 1 つの品物は 1 つまで • この時の価値の合計の最大値は? 品物 1 品物 2 品物 n 重さ w1 重さ w2 ・・・ 重さ wn 価値 v1 価値 v2 価値 vn 5. ナップサック問題の例 品物 1 品物 2 品物 3 品物 4 U=5 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v2 = 2 v3 = 4 v4 = 2 品物 1 品物 2 品物 3 品物 4 答え 7 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v
きっかけはPythonでpLSA(pLSI)を実装している人がいたので、文書クラスタリングに使えないかな、と考えたことでした。satomacoto: PythonでPLSAを実装してみるただpLSIはいわゆるソフトクラスタリングで、以下のような問題がありました。 結果の解釈が直接しづらい 処理時間がかかるこのうち1つ目の問題は文書が与えられたときのクラスタへの所属確率 P(z|d) の最大値を取ってハードなクラスタリングの結果を得れば解決します。しかし、処理時間のほうはEMアルゴリズムの途中で0でないパラメータが多いことが原因なので、単にP(z|d)をハード化しても他のパラメータ (P(z|w,d)など) がなくならないのでイマイチでした。そこで P(z|w,d), P(w|z), P(d|z) の各パラメータをハード化することで高速化できないかなと考えたのですが、結果はかなり劣化してしま
以前実装した構築速度重視の動的ダブル配列 (表中 dda) の構築速度を Darts, darts-clone (0.32g beta5, 0.32e5), DASTrie (1.0), doar (0.0.10),簡潔データ構造を利用したトライ (tx 0.16) ,STL コンテナ (std::map, std::tr1::unordered_map) 辺りと比べてみた.キー集合としては,中規模で疎な集合(Wikipedia 英語版記事タイトル)と小規模で密な集合(郵便番号辞書)を用いた. ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Search* | Size [bytes] =================
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く