2009-10-29 - やた＠はてな日記 Succinct なトライの実験
実験の概要 Succinct な木構造を用いてトライを実装すると，コンパクトな辞書を構築できます．しかし，検索速度の面では，その他のデータ構造に劣るという欠点を持ちます．そこで，いくつかのトライを C++ で実装し，ちょっとした性能テストをしてみました．今回のテストで実装したトライは，以下のとおりです． BasicTrie 各ノードに「一つ目の子ノードの ID」，「兄弟ノードが存在するか」，「ラベル」を持たせたトライ 兄弟ノードが隣接するように配置 探索時，子ノードを線形探索して移動先を決定 TernaryTrie BasicTrie の各ノードに「子ノードの数」を加えたトライ 探索時，子ノードを二分探索して移動先を決定 DaTrie ダブル配列によるトライ 探索時，ラベルにより移動先を一意に決定 SuccinctTrie 「一つ目の子ノードを左の子」，「兄弟ノードを右の子」とする二分木に
遷移行列の冪乗根 - CatTail Wiki*
状態遷移確率行列を２乗することで，２時点先の状態遷移確率行列を得ます．ですから，１年間の状態遷移確率行列の12乗根を求めれば，１ヶ月間の状態遷移確率行列になります． ですが，SASの行列演算言語IMLでは，行列の冪乗演算子**は，-1以上の整数しか受付けません． そこで，以下に，行列を固有値と固有ベクトル行列に分解して，冪乗根を求める方法を示します． ここでは，平方根を求めていますが，##(1/2)を，##(1/12)にすれば12乗根が得られます． （注：##は，IMLでの，行列の「各要素」の冪乗演算子です．） 警告！：すみません．固有値が複素数になるケースに対応していませんでした． そのうち，直しますが，どなたか直してくれるとうれしいです（翔） →たねやさんが回答してくれました．（感謝感謝） ************************************************
SciPyを用いて潜在的意味解析(LSA) - 未来は僕以外の手の中
自然言語処理の技法の１つに、潜在的意味解析(LSA)というものがある。 単語文書行列Ａがあった場合、特異値分解(SVD)により Ａ=ＵΣＶ に分解し、特異値を大きいほうからk個使って Ａk=ＵkΣkＶk のように階数の低減を行うことで、階数kのＡへの近似を最小誤差で得ることができる。 つまり特異値分解の計算さえできてしまえばLSAもすぐできるわけだが、 pythonの数値解析モジュールScipyにかかれば特異値分解もあっという間である。 まずは特異値分解まで↓ from numpy import * from scipy import linalg A = matrix([ [5, 8, 9, -4, 2, 4], [2, -4, 9, 4, 3, 3], [-3, 4, 8, 0, 5, 6], [-2, 5, 4, 7, 0, 2] ]) u, sigma, v = linalg.sv
.:: General Purpose Hash Function Algorithms - By Arash Partow ::.
Introduction Hash functions are by definition and implementation generally regarded as Pseudo Random Number Generators (PRNG). From this generalization it can be assumed that the performance of hash functions and comparisons between other hash functions can be determined by modelling the functions as PRNGs. Analysis techniques such a Poisson distribution can be used to analyse the collision rates
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
「確率密度比」を用いた機械学習の新たなアプローチ - yasuhisa's blog
東工大の杉山先生の講演がすごく面白かったのでメモ。 やりたいこと、特徴p(x)とp'(x)という分布を推定しようという問題があったとする。このとき、二つの分布のパラメータを推定しないといけないので普通は大変。そこで、w(x) = p'(x) / p(x)を推定するという風に少し変形してやる。p(x)とp'(x)が分かればw(x)は求めることができるが、w(x)があってもp(x)とp'(x)は分からない。ということでw(x)のほうが簡単な問題になっている。 こういう風に「何か問題を解くときに、その過程で元の問題より難しい問題を解かないようにしないと!」というような考え方をVapnikの原理といったりするそうです。 この確率密度比の枠組みを利用すると非定常環境適応、ドメイン適応、マルチタスク学習、外れ値検出、時系列の変化点検知、特徴選択、次元削減、独立成分分析、条件付き確率推定などなどの問題を
kd-tree Visualization(2) - agwの日記
先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。 繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成したkd木を可視化したものは以下のようなものでした。 同じく、木構造として可視化したものは以下のようなものでした。 さて、では何故均衡の取れない木が構築されてしまうのでしょう? 座標群の初めの点、1番の点を挿入した直後の状態を可視してみましょう。 この可視と先ほどの木構造としての可視を比較すると不均衡な木が構築される理由がより明らかとなります。木構造の可視にて1番の左側にぶら下がっている2番以下の座標群は、この可視では1番によって空間分割された領域の下側、つまり、y座標値がより小さい側に分布しています。 同様に、木構造にて1番の右側にぶら下がってい
計算幾何学に出会う - 道化がつぶやく
最近棒探索について調べた 今作っている Ajax システムの中に 1000個オーダーの頂点を、マウスで選択できる仕組みを入れたくて 複数の点の中からマウスに一番近い点を探すアルゴリズムを調べていた なかなかうまい方法が見つからない。。。 でも、点の集合から最近点を見つけるなんて、よくありそうだしなぁ。。 絶対に何かジャンルがあるはずに違いない。。。 そう思い、はてなの人力検索 http://q.hatena.ne.jp/1239891135 本当に、たくさんの回答・アドバイスをいただきました！！ ブクマコメより paella 勉強, アルゴリズム 良い質問に良い回答（コメント欄も）。あとはこれが学校の宿題でないことを祈るのみ。 2009/04/19 学生ではないので、ご安心くださいｗ dan kogai さんにも取り上げていただいた！ http://blog.livedoor.jp/dan
le4 parallel programming
LU分解 (LU decomposition) 数学的定義 n×n 行列を考える． 行列積 C = A B ： (行列 C の i 行 j 列目の要素を c_ij と書けば) n c_ij = \xAD\xF4 a_ik b_kj k=1 行列・ベクトル積 b = A x ： (ベクトル bの i 行目の要素を b_i と書けば) n b_i = \xAD\xF4 a_ik x_k k=1 連立一次方程式の解： 与えられた行列 A と ベクトル b に対して、 A x = b を満たす ベクトル x を求める。 LU分解 とは 行列 A を、下三角行列 L、上三角行列 U を 用いて A = LU と分解すること。 ただし、 L については l_ij = 0 (1 ≦ i ＜ j ≦ n)， Uについては u_ij = 0 (1 ≦ j ＜ i ≦ n)である。 LU 分解を用いた連立一次
Introduction to Dynamic Programming
Dynamic programming is a method for efficiently solving a broad range of search and optimization problems which exhibit the characteristics of overlappling subproblems and optimal substructure. I'll try to illustrate these characteristics through some simple examples and end with an exercise. Happy coding! Contents Overlapping Subproblems Optimal Substructure The Knapsack Problem Everyday Dynamic
Low-Layer Hacks: P2Pアルゴリズム毎のメリット/デメリット
2009-10-10 P2Pアルゴリズム毎のメリット/デメリット Winny裁判で金子氏に無罪判決が下り、P2Pを実装したアプリケーションは今後増えてくると予想される。そこで、技術者向けにP2P構造化オーバーレイネットワークのアルゴリズム毎におけるメリット/デメリットを簡潔にまとめ、実装にあたり必要となるであろう参考資料を示した。 ・Chord DHT(分散ハッシュテーブル)の一種であるこのアルゴリズムはConsistent Hashingをベースとしており、名前の通り、分散されたコンピュータ間にハッシュテーブルを構築する。このアルゴリズムは多くのシステムに採用されているのでとても信頼性が高く、実装も容易である。 ただ、愚直な実装では耐障害性が低くなるので注意が必要だ。UnbreakableなChordを提案した論文もあるようなので、そういう文献も参考にすると良いかもしれない。 参
pLSIを試してみた - のんびり読書日記
これまでにK-means++とfuzzy c-meansを使用したクラスタリングを試してきましたが、今回はpLSI(probabilistic latent semantic indexing, 潜在的意味インデキシング)によるクラスタリングを試してみようと思います。 pLSIは確率・統計的な枠組みで次元縮約を行う枠組みで、なかなか精度がよいらしく色々な論文で見かけます。Google NewsのレコメンドでもpLSIを使用しており、MapReduceで処理を並列化させて高速に実行しているそうです(論文読んでないので間違っているかも)。また入力ベクトルをあらかじめ重み付けしておく必要がなく、文書であれば単語の頻度をそのまま入力として使用できるのもうれしいところです。 より詳しくは以下のWikipediaのエントリか、書籍をご参照下さい。(書籍は処理結果の表8.4が並びがグチャグチャになってる
pLSIのプログラムとか - とある研究者の日々
前にpLSIのプログラムを載せていたが、大規模データに対して実際に使ってみるとメモリを大量に消費するは計算時間がかかるはであまり使いものにならない。基本的な部分は問題がないと思うのだが。ということで、本格的にメモリ節約と時間高速化を目指す。 前に作ったプログラムでメモリを一番消費しているのはEMのExpectation部分なので、ここを全文書、全単語、全隠れ属性の値を保存しない形に修正する。速度アップを実現するにはメモリに結果を保存して再利用することで計算を減らせばよいが、今回の最終の目的からは無制限には認められない。ということで、CLAPACKを使って行列演算の高速化を実現することに。また、高速化の効果が期待できそうな場所をgprofにより検証しつつ、再計算の負荷を減少することにする。 ということで、少しは高速になったと思うのだが、CLAPACK版を使う前のプログラムで実験を始めたので、
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Workshop on Scheme: Merge sorting
SciPy Cookbook — SciPy Cookbook documentation
(Matlab) Codes and Datasets for Subspace Learning (Dimensionality Reduction)
Lua/組み込み - assari
IBM Developer
ヒビルテ(2007-12-30)
not found