リンク解析とか: 重要度尺度と von Neumann カーネル - Standard ML of Yukkuri
リンク解析とか: 重要度尺度と von Neumann カーネル Algorithm NAIST の入学手続を終えた. 残りの期間はサーベイするぞーということで shimbo 先生の講義資料「リンク解析とその周辺の話題」を読んでいます. 一日目, 二日目の資料は PageRank, HITS, SALSA などの重要度尺度の紹介と, von Neumann Kernels と HITS の関係についてのお話が中心. これらを実装してみた. 後半に進むほど力尽きて記述が適当になってます:) PageRank ポイントは遷移確率行列による random walk では定常分布に収束しない (エルゴード性 (ergodic) を満たさない) という点. どうして満たさないかというと. sink (出次数のない節点) が存在するとき, 明らかに既約 (irreducible) でないのでエルゴード
最適化アルゴリズム - sonoshouのまじめなブログ
集合知プログラミングの第５章最適化の一部を自分なりにまとめます。 ヒルクライム法（傾斜上り法） ヒルクライム法は、ある地点から少し値を変更し、 変更後の値が変更前の値より低ければ採用する。 これを繰り返して行けば、最小値へ近づくことが出来る。 ヒルクライム法には致命的な弱点がある。 例えば、下図のようなグラフを考える。 このように、局所的最小解があるようなグラフでは、 大局的最小解を発見することはできない。 ヒルクライム法は非常に単純な方法で一般的に使われることは無いが、 この後の手法の比較のために説明する。 アルゴリズム＜初期化処理＞ ランダムな値で変数を初期化。カウントを初期化。 ＜反復処理＞ 変更する変数を一つ選ぶ。 変数の値を増加させるか、減少させるかを決定する。 変数の値を変更後、新たな変数でコストを算出する。 変更前と変更後のコストの大小を比較する。 変更後のコストが小さければ
線形SVM - 人工知能に関する断創録
下巻に入って7章のサポートベクトルマシン（Support Vector Machine: SVM）を実装してみます。SVMに関しては、有名なSVMのライブラリ（libsvm）を使ったことがあるだけで、アルゴリズム詳細はPRMLで初めて学習しました。なので変なことを書いていたらコメント欄で指摘してもらえると助かります。 まずは、一番簡単な線形SVMを実装してみます。今までと同様に直線（超平面）でデータが完全に分離できる場合です。PRMLの7章には特に説明がありませんが、カーネル関数に下の線形カーネル（データのただの内積）を用いた場合に相当するようです。このカーネル関数を多項カーネルやガウシアンカーネルに変更すると線形分離不可能なデータも分類できるようになるとのこと。非線形SVMは次回ためしてみます。 まず、SVMの識別関数は、式（7.1）で表せます。 今までと違ってバイアスパラメータをまとめ
AOJの問題を推薦――協調フィルタリングを試してみた - 唯物是真 @Scaled_Wurm
AIZU ONLINE JUDGE(AOJ)という競技プログラミングの問題を公開しているサイトがある。 AIZU ONLINE JUDGE: Programming Challenge 1年以上前にAOJを少しだけやっていた頃に、AOJの問題を推薦するスクリプトを書いたものの、特に公開も使用もせずに放置していたのでブログ記事にして供養(？)しておく。 AOJにはたくさんの問題があって、どれを解くべきかよくわからないので、とりあえず推薦システムを作ってみた(モチベーションがおかしい AOJではAPIが公開されていて、各ユーザーがどの問題を解いているかなどの色々な情報が得られる デモだけ試したい方はこちら 処理の概要 AOJのAPIを使って各ユーザーがどの問題を解いているかというデータを集める。 集めたデータを元に協調フィルタリングを用いて推薦する。 データの取得 APIの結果はXMLで返され
ナイーブベイズ分類器の実装とか 〜畑さん/こだまさん問題〜 - naoya_t@hatenablog
スパム判定などでお馴染みのナイーブベイズ分類器。 構造が比較的単純なのに割といい感じに分類できるので重宝がられています。 ナイーブベイズ分類器で用いる文書モデルとして、「言語処理のための機械学習入門」（奥村学 著）では 多変数ベルヌーイモデル (multivariate Bernoulli model) 多項モデル (multinomial model) がそれぞれ最尤（ML*1）推定、最大事後確率（MAP*2）推定の場合について説明されていて、まあ例題を追っていけば高校生でも文系の子でもわかる感じ*3なんだけど、そういえばちゃんと自分で書いたことなかったなあと思って、寒いのにソイあずき抹茶フラペチーノをすすりながらやってみたのでした。 # -*- coding: utf-8 -*- from math import log # # 多変数ベルヌーイモデル multivariate Ber
Pythonで構造化パーセプトロンを実装してみた - nokunoの日記
Web+DBの「作って学ぶ日本語入力」で紹介されていた，Rubyによる構造化パーセプトロンの実装をPythonに移植しました．WEB+DB PRESS Vol.64｜gihyo.jp … 技術評論社実装はgithubに置きました．python/webdb at master from nokuno/nokuno - GitHub common.py #!/usr/bin/env python # encoding: utf-8 from collections import defaultdict from optparse import OptionParser from sys import stdin, exit from re import match class Dic: def __init__(self, filename): self.ht = defaultdict(li
機械学習ライブラリ SHOGUN入門 – Rest Term
The machine learning toolbox’s focus is on large scale kernel methods and especially on Support Vector Machines (SVM) * The SHOGUN Machine Learning Toolbox サイトのデザインどうにかしたらいいのにとか将軍ってなんだよとかいろいろあるかと思いますけども、プロダクトとしては素晴らしいという噂を聞くので今回このSHOGUNという機械学習ライブラリを試してみました。目的は一般物体認識における分類タスクでMultiple Kernel Learning(MKL)やLatent SVMの実装を試すことなのですが、まずはインストール方法と簡単な使い方を調べるところから始めます。 また、この記事の内容はQiitaにも投稿しています。 * 機械学習ライブラ
Latent Dirichlet Allocations の Python 実装 - 木曜不足
LDA とは "Latent Dirichlet Allocation"。文書中の単語の「トピック」を確率的に求める言語モデル。 「潜在的ディリクレ配分法」と訳されていることもあるが、その名前だと「それってなんだっけ？」という人のほうが多そうｗ。 各単語が「隠れトピック」(話題、カテゴリー)から生成されている、と想定して、そのトピックを文書集合から教師無しで推定することができる。特徴は、果物の apple と音楽の apple とコンピュータ関連の apple を区別することが出来る(ことが期待される)という点。そのために、どのトピックを生成しやすいかという分布を各文章も持つ。細かい話は略。 結果の見方としては、定量的にはパープレキシティを見るし(一般に小さいほどいい)、定性的には各トピックがどのような単語を生成するか、その確率上位のものを見てふむふむする。この「各トピックが生成する単語」
PythonでLIBSVMを使う
導入方法 1．ここからLIBSVMのzipファイルもしくはtar.gzファイルをダウンロードし適当なディレクトリに解凍。（最新版3.1） 2．解凍したフォルダに移動し、makeコマンド実行。以下のファイルができるはず。 svm.o svm-train.exe svm-predict.exe svm-scale.exe 3．解凍したフォルダの中のpythonフォルダに移動し、makeコマンド実行。以下のファイルができるはず。 libsvm.so.2 使用例 適当に学習させてみる． svmtest.py from svm import * from svmutil import * prob = svm_problem([1,-1], [[1,0,1], [-1,0,-1]]) #訓練データ param = svm_parameter('-t 1 -c 3') #SVMのパラメータ設定 m =
SVMを実装してみた - xyz600の日記
授業でSVMについて習ったけど、実際に実装したことなかったからやってみた。簡単って言われてるけど、制約付き2次計画問題の実装が結構大変だった（収束しないケースとかたくさんあったり、制約条件を遵守したり） 参考にしたのは、以下の本やらページやら http://www.amazon.co.jp/%E3%82%B5%E3%83%9D%E3%83%BC%E3%83%88%E3%83%99%E3%82%AF%E3%82%BF%E3%83%BC%E3%83%9E%E3%82%B7%E3%83%B3%E5%85%A5%E9%96%80-%E3%83%8D%E3%83%AD-%E3%82%AF%E3%83%AA%E3%82%B9%E3%83%86%E3%82%A3%E3%82%A2%E3%83%8B%E3%83%BC%E3%83%8B/dp/4320121341/ref=sr_1_1?ie=UTF8&qi
ナイーブベイズを用いたテキスト分類 - 人工知能に関する断想録
今までPRMLを読んで実装を続けてきましたが、10章からは難しくて歯が立たなくなってきたのでここらで少し具体的な応用に目を向けてみようと思います。機械学習の応用先としては画像の方が結果を見ていて面白いんですが、当面は自然言語処理を取り上げます。そんなわけで一番始めの応用は機械学習と自然言語処理の接点として非常に重要なテキスト分類（Text Classification, Text Categorization）の技法たちを試していきたいと思います。テキスト分類は文書分類（Document Classification）という呼び方もあります。テキストと文書は同じ意味です。最初なので自分の知識の整理と入門者への紹介のためにちょっと丁寧にまとめてみました。 テキスト分類とは テキスト分類とは、与えられた文書（Webページとか）をあらかじめ与えられたいくつかのカテゴリ（クラス）に自動分類するタス
「Web本文抽出 using CRF」の学習用データの作り方 - 木曜不足
第２回自然言語処理勉強会＠東京が 9/25 に行われます。 前回よりキャパの大きい会場＆週末に参加募集が始まったばかりですが、早くもほぼ定員。 自然言語処理に興味のある人はぜひ。でも、計画的なドタキャンは運営の方にご迷惑がかかるのでやめてね。 今度の第２回でも出しゃばって発表させてもらう予定だが、第１回も「Web本文抽出 using CRF」という話をさせてもらった。 CRF(Conditional Randam Fields) を Web ページからの本文抽出に用いるという手法の提案という内容で、実際に動作する Python スクリプトもあわせて公開している。 資料: http://www.slideshare.net/shuyo/web-using-crf 実装: http://github.com/shuyo/iir/blob/master/sequence/crf.py http:
Lossy Countingを実装してみた - 省メモリな頻度計測 - 唯物是真 @Scaled_Wurm
大規模データで頻度を数えると、欲しいのはよく登場するアイテムの情報なのに、ほとんど出現しないアイテムの種類数が非常に多くて、それらがメモリを大量に必要としてしまうという問題がある これに対してアイテムの種類数の最大値に制限を加えたり、頻度に誤差を許すなどの条件のもとで、省メモリに頻度計測を行う方法がいくつも提案されている これらについては以下の記事が詳しい 大規模データで単語の数を数える - ny23の日記 今回はそういった手法の一つであるLossy Countingを実装した 日本語では上記の記事と以下の記事が詳しい [を] 誤り許容カウント法(lossy count method)のサンプルプログラム [O] イプシロン劣シノプス性を保持した頻度カウント lossy countingアルゴリズム - 機械学習の「朱鷺の杜Wiki」 元論文はこちら。年を見ると結構前なので、現在ではもっと
pythonの機械学習ライブラリscikit-learnの紹介 - 唯物是真 @Scaled_Wurm
scikit-learn(sklearn)の日本語の入門記事があんまりないなーと思って書きました。 どちらかっていうとよく使う機能の紹介的な感じです。 英語が読める方は公式のチュートリアルがおすすめです。 scikit-learnとは？ scikit-learnはオープンソースの機械学習ライブラリで、分類や回帰、クラスタリングなどの機能が実装されています。 また様々な評価尺度やクロスバリデーション、パラメータのグリッドサーチなどの痒いところに手が届く機能もあります。 インストール scikit-learnの他にもnumpyとかscipyとかが必要です。 Windows 64 bit版の人は以下のURLに色々なインストーラーがおいてあるのでおすすめ Python Extension Packages for Windows - Christoph Gohlke その他の人は以下のURLを見て
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
2013.07.15 はじパタlt scikit-learnで始める機械学習
サービス終了のお知らせ