Não Aqui! » 10行強で書けるロジスティック回帰モデル学習
ロジスティック回帰（logistic regression）の学習が，確率的勾配降下法（SGD: stochastic gradient descent）を使って，非常に簡単に書けることを示すPythonコード．コメントや空行を除けば十数行です． リストの内包表記，条件演算子（Cで言う三項演算子），自動的に初期化してくれる辞書型（collections.defaultdict）は，Python以外ではあまり見ないかも知れません． リストの内包表記は，Haskell, OCaml, C#にもあるようなので，結構メジャーかも知れません． [W[x] for x in X] と書くと，「Xに含まれるすべてのxに対し，それぞれW[x]を計算した結果をリストにしたもの」という意味になります．sum関数はリストの値の和を返すので，変数aにはXとWの内積が計算されます． Pythonでは，三項演算子を条
PythonでA*(A-Star)アルゴリズム - Pashango’s Blog
今回はA*アルゴリズムをPythonでやってみます。 ゲームプログラマの間では、もはや常識となりつつある最短経路問題解決アルゴリズムです。 A*は、古典的手法である「ダイクストラ法」を改良したものです。 スタート地点からノードnを通ってゴールに辿り付くとき、最短距離をf(n)とすると、 f(n) = g(n) + h(n) とすることができます、g(n)は「スタートからノードnまでの最短距離」、h(n)は「ノードnからゴールまでの最短距離」です。 でも、最初から適切なg(n)とh(n)が判ってるなら苦労しませんよね。 だから、テキトーな予測値を使って、最短経路をある程度予測して効率的に経路探索をしてみようという事です。 テキトーな予測値を使った最短経路距離をf*(n)とすると f*(n) = g*(n) + h*(n) となります、f*(n)を求めるためにテキトーなg*(n)とh*(n)を
PythonでPLSAを実装してみる
probabilistic latent semantic analysis (PLSA)は、 ・文書dがP(d)で選ばれる ・潜在変数zがP(z|d)で選ばれる ・語wがP(w|z)で生成される というプロセスを経て、結果として(d,w)のペアが観測されるという文書と語の生成モデル。 式で表すと (1) となる。P(d,w)の尤もらしい確率分布を見つけたい。対数尤度関数は (2) となる。n(d,w)は語wが文書dに出現する回数。この式は訓練データn(d,w)（;どの語がどの文書に何回出現したか）が尤もらしい確率分布P(d,w)に従うとき最大になる。ベイズの定理を用いると (3) となることを利用して、この尤度関数を最大化するためにEMアルゴリズムを用いて実装してみる。（過学習を回避するために文献ではTempered EM (TEM)を用いている。）尤度関数が収束するまで以下のE-ste
ダイクストラ法 - Bug's Groove
前回のアルゴリズムイントロダクション輪講の話題、単一始点最短路問題から。詳しくは アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー へ。その中で丁度前回 書いたプリム法と同じく、ダイクストラ法が最小優先度付きキューを使うので、ちょっといじったらかけるのでは？と思って書いてみました。(相変わらずの乱プログラムご容赦...)。対象のグラフは教科書通り。 実装的には、minheap クラスは前回のプリム法と全く一緒。MinPriorityQueue は前回と使い方が違うので一部実装し直し。(といっても relax の周り)。実行するとこんな感じになるはずです。 s -> y -> t (8) s -> y -> t -> x (9) s -> y (5) s -> y -> z (7) 教科書のヒープソート (6章) にもあったように、優先度付きキュー
クラスカルのアルゴリズム - naoyaのはてなダイアリー
昨年からはじめたアルゴリズムイントロダクションの輪講も終盤に差し掛かり、残すところ数章となりました。今週は第23章の最小全域木でした。辺に重みのあるグラフで全域木を張るとき、その全域木を構成する辺の合計コストが最小の組み合わせが最小全域木です。 アルゴリズムイントロダクションでは、クラスカルのアルゴリズム、プリムのアルゴリズムの二点が紹介されています。いずれも20世紀半ばに発見された古典的なアルゴリズムです。 二つのうち前者、クラスカルのアルゴリズムは、コスト最小の辺から順番にみていって、その辺を選んだことで閉路が構成されなければ、それは安全な辺であるとみなし、最小全域木を構成する辺のひとつとして選択します。これを繰り返しているうちに最小全域木が構成されるというアルゴリズムです。 今日はクラスカルのアルゴリズムを Python で実装してみました。扱うグラフは書籍の例を使ってみました。以下
B木の Copy-Modify 方式での実験的コード - Tociyuki::Diary
id:naoya さんの Python 版B木に触発されて、Ruby 版の insert・delete だけを実装した B 木を書いてみました。 実装にあたり、標準的な教科書に良く掲載されている Overwrite 方式ではなく、現代的な Copy-Modify 方式、すなわち B 木の葉から根に向かって更新のおこなわれるノードを複製してから修正をおこなっていき、最後に根をすげ替える方式に挑戦してみました。こうすることにより、更新の途中でなんらかの例外が発生したとしても、直前の B 木を壊さずにすみ、安全にロール・バックすることができるようになります。また、更新の途中の元の B 木はいっさいがっさい元のままですから、根を変更バージョンごとに持つようにすれば、現代的なデータ・ベース・マネジメント・システムに採用されている Multi-Version Concurrency Control(M
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Blog - Mikula Beutl - SEO Consulting