乱択アルゴリズム紹介(Color-Coding) - Preferred Networks Research & Development
吉田です。今まで数解に渡って乱択アルゴリズムを紹介してきました。そろそろ解析やアイデアがシンプルかつ結果が綺麗な乱択アルゴリズムは尽きてきたかと思っていましたが、もう一つとても素敵な手法が有るのを思い出しましたので解説します。Color Codingと呼ばれる手法です。 \(G = (V, E)\)をグラフ、\(s,t\in V\)を\(G\)中の二頂点、\(k\geq 0\)を整数とします。\((s,v,k)\)パスとは、\(s\)と\(t\)を結ぶパスで内点の個数が丁度\(k\)個のものを指します。但しパスは同じ頂点や枝を二度使ってはいけません。例えば以下の図で赤い線で示されているパスは\((s,t,5)\)パスです。
なぜRubyをPythonよりもPHPよりも高速化できたか - 方向
最も有名なベンチマークサイト "The Computer Language Benchmarks Game" における最新のランキングで Ruby 1.9 は Python3, PHP, JRuby を追い抜きスクリプト言語としてトップクラスの値を叩き出しました。 5/4の時点では最下位に近かったので大きく前進しています。 1つのパッチで520%の高速化を達成 この高速化は私がfastaというベンチマークのプログラムを改善したことにより実現しました。 少し前Rubyのベンチマークを書くことにハマっていました。 他の人のプログラムや統計を眺めていたとき、fastaに関してPythonが異常に速いことに気づきました。 他のスクリプト言語のおよそ50倍速く、アルゴリズムが改良されていました。 fasta #6 fasta #7 この2つのコードを比較するとわかるのですが、処理が重複している箇所に
リニアハッシュ（Linear Hash）
今年の技術士二次試験には、Linear Hashに関する出題がありました。 恥ずかしながら、僕はLinear Hashって分からなかったのですが、Hashに関する一般的な知識から何とか回答することはできました。 木構造との比較でPros & Consを求めた出題ですので、Linear Hashを深追いする必要はないのでしょうけれど、分からなかったことをそのままにしないのが僕のPolicy。なぜかあまり情報が見つからなかったので、Memoっておくことにしました。 Linear HashのHash関数は他にもあるかも知れませんが、調べた感じでは．．． h[i](c) = c mod (2^i)N 式の意味は後で分かると思うので、実際の動きを追ってみます。 まず、Hash空間のSizeの初期状態が4だとします。（N=4） このとき、iは０としておきます。（今は深く考えないでください。） すると、
機械学習超入門IV 〜SVM(サポートベクターマシン)だって30分で作れちゃう☆〜 - EchizenBlog-Zwei
ニーズがあるのかさっぱりわからない機械学習超入門だけどひっそり続けていきたい。 前回は識別関数の基礎であるパーセプトロンの簡単な説明とPerlによる実装を解説した。実はこの時点でかの有名なSVM(Support Vector Machine、サポートベクターマシン)もほぼ完成していたのだ！というわけで今回はSVMをPerlで作ってしまうお話。 参考: これからはじめる人のための機械学習の教科書まとめ - EchizenBlog-Zwei 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBlog-Zwei 機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう！〜 - EchizenBlog-Zwei 機械学習超入門III 〜機械学習の基礎、パーセプトロンを30分で作って学ぶ〜 - EchizenBlog-Zwei さて
『徹底解剖「G1GC」 アルゴリズム編』発売！！ - I am Cruby!
g1gcGCLoverのみなさん、お待たせしました。 GC本のスピンオフとなる新著、『徹底解剖「G1GC」 アルゴリズム編』が発売中です！ 達人出版会様の以下のページからご購入下さい。 なんと600円です！！！ もうすぐにでもポチっちゃってください！！！！！ 徹底解剖「G1GC」 アルゴリズム編 - 達人出版会 どういう内容なの？まえがきをみるとよくわかります。 今回はOpenJDK7（いわゆるJava7）に新しく実装された「G1GC（Garbage First Garbage Collection）」というGCの謎を解明していきます。 G1GCの大きな謎として「GC停止時間を予測できる」というのがあります。本書 ではその謎の回答を何十ページもかけて解説しています。 G1GCについて書かれた資料として、Detlefsらの英語の論文（Detlefs04）があ ります。 ところが、これは謎
SVMの定番入門書「サポートベクターマシン入門(赤本)」の読み方 - EchizenBlog-Zwei
SVMを学びたい人にとっては「サポートベクターマシン入門」通称「赤本」は最適な入門書であるといえる。理論から実践までバランスよく解説されており、本書を読むだけでSVMの実装が可能になる。 しかし本書はSF小説を彷彿とさせる独特な翻訳の文体のため機械学習に不慣れな読者にとっては読みこなすのは苦しい戦いとなる。本来なら原書をオススメしたいところだが、そうはいっても英語はちょっとという人も多いはず。 そこで本記事では赤本のオススメな読み方を紹介してみる。 1.「わかパタ」で準備運動をしよう 泳ぎのうまい人でもいきなり水に飛び込むのは危険。まずは準備運動をして体を温める。これには「わかりやすいパターン認識」がオススメ。とりあえず2章まで、余裕があれば3章まで読んでおけば充分。 2.赤本を枕元において一晩寝よう さて準備運動が済んだら早速赤本にトライ！したいところだが赤本の放つ瘴気で心を蝕まれないよ
海風に揺れる一輪のTRIEライブラリ erikaを作ってみたよ - EchizenBlog-Zwei
注意：この記事の内容は古いものです。 最新版のerika-trieは erika-trie(実用版)とキーワード抽出ツールerika_extractを作ったよ - EchizenBlog-Zwei うっかり手が滑って自分で☆つけてしまいましたが自画自賛してるわけではないです・・・。 をご参照ください。 最近TRIE(トライ)に対する興味が高まってきたので勉強のためにライブラリを作っていた。一応完成したので公開しておく。普通のTRIEとLOUDSによるTRIEの二つを実装した。 名前はerika。もしくはerika-trie。以前作ったCompressed Suffix Arrayのライブラリがtsubomiだったので、今回はerikaにした。コードはGoogleCodeのtsubomiと同じところにおいてある。というかtsubomiの付属品状態。開発はlinuxで行ったが特に環境に依存した
アルゴリズム勉強中 - nokunoの日記
というわけでIntroduction to Algorithmsを最初から読み直しています。 今回はアルゴリズムを実装できるようになるだけでなく、できる限り演習問題を解いていて、数学的な部分も含めた理解が深まるように読んでみています。とはいえ、実装せずにひたすら紙とペンに向かっていると手が寂しくなってくるものです（プログラマなもので…）。というわけで、2章に出てきたアルゴリズムをいくつか実装してみました。どれも1度は書いたことがあるはずなのですが、pythonで書くのは初めてだったりしてなかなか興味深いです。 挿入ソート挿入ソートは素直なアルゴリズムなので書きやすくていいですね。もちろん計算量はO(n^2)なので実際に大きなデータセットに対して使うことはないわけですが、解析しやすいので比較対象としての存在価値は高いと思います。 #!/usr/bin/python def insertion
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
4chan BBS - Genius sorting algorithm: Sleep sort
1 Name: Anonymous : 2011-01-20 12:22 Man, am I a genius. Check out this sorting algorithm I just invented. #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 Oh god, it works. But I don't like to wait 218382 seconds to sort '(0 218382)
JAIST Repository: 孤立者検出のための立食形式パーティー映像のハンドアノテーション分析
学会の懇親会や結婚式の披露宴などの立食形式パーティーで会話の輪から孤立している人がいる． この会話の輪に入ることが出来ていない状態の人を 「孤立者」 と呼ぶ．本研究では立食形式パーティーの映像を使いハンドアノテーションを行う．そしてそこから得られたアノテーションデータを用いて孤立者の検出を行う．今回提案する検出手法は会話集団を見つけ，それ以外の人を孤立者とする方法である．人が映像を見て直感的に孤立者と判断したデータと提案手法で得られた結果との比較を行い，どれだけ孤立者が検出できたのかを明らかにする．またその結果から今後の課題についても検討を行う． : In this paper, we discuss a hand annotation method for video analysis of a buffet party toward detection of wallflowers.
livedoor Techブログ : decision tree (決定木) でユーザエージェント判定器を作ってみる
アクセスログのユーザエージェント(UA)からブラウザを判別するのって，みんな何使ってますか？ 自分が作ったアクセス解析システムでは HTTP::BrowserDetect と HTTP::MobileAgent にそれぞれ独自パッチをあてたものを使っています。これらはルールベースの判定器なので，新しいブラウザや新種の bot が登場するたびに手作業でルールを追加し，パッチを作って配布するという作業が必要になります。 この更新作業が大変面倒くさくて対応が遅れがちになるので，「このUA文字列はこのブラウザですよ、という例を大量に与えたら、自分で勝手に判定ルールを学習してくれるようになったら便利なのになぁ」と思い，decision tree (決定木)を使ってみることを思い立ちました。 目標は， "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1
プログラミングコンテストチャレンジブックを読みながらダイクストラ法を実装したよ - nokunoの日記
前回のベルマンフォード法から時間があいてしまいましたが、プログラミングコンテストチャレンジブック（通称アリ本）を読みながらグラフの最短経路を求めるためのアルゴリズム、ダイクストラ法を実装しました。 ベルマンフォード法 - nokunoの日記ダイクストラ法 - Wikipedia ダイクストラ法ではグラフ中のノードを次の3つに分類します。 未探索 探索済み 次の探索候補この「次の探索候補」の中から最もコストの小さいノードを選んで探索済みとし、その隣接ノードのコストを更新するというのがダイクストラ法の根本のアルゴリズムとなります。 最初の実装それでは実装を見ていきましょう。まず最初の実装では次に探索済みとなる要素を線形探索しているためあまり効率的ではありません。 #include using namespace std; #define MAX_E 20 #define MAX_V 7 #d
Zinnia: 機械学習ベースのポータブルな手書き文字認識エンジン
Zinnia: 機械学習ベースのポータブルなオンライン手書き文字認識エンジン [日本語][英語] Zinniaは機械学習アルゴリズム SVM を用いたポータブルで汎用的な オンライン手書き文字認識エンジンです。Zinniaは組み込みの容易さと汎用性を高めるために、 文字のレンダリング機能は持っていません。Zinniaは文字のストローク情報を座標の連続として受け取り、 確からしい順にスコア付きでN文字の認識結果を返すだけに機能を限定しています。 また、認識エンジンは完全に機械学習ベースであるために、文字のみならずユーザの任意のマウス・ペンストロークに対して任意の文字列をマッピングするような認識エンジンを小コスト作成することができます。 主な特徴 機械学習アルゴリズムSVMによる高い認識精度 ポータブルでコンパクトな設計 -- POSIX/Windows (C++ STLのみに依存) リエント
Luceneの曖昧検索を100倍高速化したアルゴリズム - nokunoの日記
@nobu_k さんのつぶやきでこのエントリを知りました。Changing Bits: Lucene’s FuzzyQuery is 100 times faster in 4.0Luceneで曖昧検索を効率化した話です。 最初の実装では、転置インデックスを全探索して編集距離がN以下の単語を拾っていたレーベンシュタインオートマトンという、編集距離がN以下の単語のみをアクセプトするオートマトンを利用することにした 単語ごとに構築したレーベンシュタインオートマトンをマージするという操作が必要になるが、なかなかうまくいかなかった 難解な論文を見つけたが、実装は難しかった良いライブラリを見つけたので、PythonからJavaに移植した 最後に1つだけ残ったバグは、移植の失敗ではなく元ライブラリのバグだった。報告すると1日で直ってきた。この前のエントリでは、有限状態トランスデューサを使った辞書の圧縮
SVM のチューニングのしかた（１） - ほくそ笑む
SVM のチューニング SVM(Support Vector Machine) はみなさん御存じ機械学習の手法です。 SVM はデフォルト設定でモデルを作ってもしょうがないです。gamma と cost というパラメータがあるので、これらの値に最適値を設定しなければなりません。R の SVM の Help にもこう書いてあります。 Parameters of SVM-models usually must be tuned to yield sensible results! (訳) SVM でいい結果出したかったらチューニングしろよな！ というわけで、SVM のチューニングのしかたについて説明したいと思います。 交差検証 おっと、その前に、交差検証の話をしなければなりません。 SVM モデルをチューニングする際、二つのパラメータでグリッドサーチをします。 すなわち、パラメータをいろいろ変
とある愚直のアロケータ - 神様なんて信じない僕らのために
前置き。dlmallocについて書くぞ！と言っておいて書いてなかったので。orz...すみません。 あろけーたをじぶんでかいてはいけません！！ なぜ、って大抵糞だからです。 例えば、こんな管理構造を持ったアロケータをよく見るんですが、 typedef struct _Allocator { unsigned char* pPool; // メモリプール int nPoolSize; // メモリプールのサイズ struct _SMemChain* pHead; // 番兵 struct _SMemChain* pTail; // 番兵 struct _SMemChain* pLast; // 最後に追加されたチェインタグ } Allocator; typedef struct _SMemChain { struct _SMemChain* pPrev; // 前のチェインタグ struct
A*アルゴリズムについて整理 - yasuhisa's blog
辞書を参考にしながら。NAISTのI期辺りでやったはずなんだが、かなりすっ飛んでいる。 デジタル人工知能学事典 [CD-ROM付] 作者: 人工知能学会出版社/メーカー: 共立出版発売日: 2008/05/16メディア: 単行本購入: 1人 クリック: 6回この商品を含むブログ (6件) を見る A*アルゴリズムとは?グラフ探索アルゴリズムの一つ。「開始ノードから現在位置に至るまでのコスト」と「現在位置からゴールまでの推定コスト」の2つのコストを用いてadmissibleな条件(後述)の元でコストが最小であるような経路を効率的に見つけることができるアルゴリズムである。1960年代に開発されたアルゴリズムであるが、50年経った今でもばしばし使われている。 現在いるノードをp、開始ノードからpまでの最小コストをg(p)、pからゴールまでの最小コストをh(p)と書くとすればpを経由して開始ノード
きれいなおねいさんのあつめかた：Bijostagramのはなし。 - TMBのおぼえがき
Bijostagram（びじょすたぐらむ）というWebサービスを作ってみました。 Bijostagram - Cute Girls on Instagram きれいなおねいさんは、好きですか？ Bijostagramとは？ Bijostagramは、きれいなおねいさんの画像がたくさん眺められるサービスです（個人的に作りました）。一番の大きな特徴は、Instagramから自動的にきれいなおねいさんの画像を集めてくる、というところです。Bijostagramでは、集めてきたおねいさん画像をランダムに表示しています。 Instagramは写真版Twitterで、しかも撮影した画像をオサレな感じで加工できてツイートできるというサービス。２月末に公式のAPIが公開されたので、いじってみました。→インスタグラムのAPIについてはこちら Bijostagramは、画像抽出と画像配置のアルゴリズムをPer
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Home - Make: DIY Projects and Ideas for Makers
