中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
レーティングシステム
本番付の根拠であるレーティングシステムは、チェスの世界に由来する。 プレイヤーAとBの対戦成績が3 - 5（Aの3勝5敗）、B vs Cが2 - 6であるとき、AとCは対戦するまでもなくCのほうが強いといえる。 B vs Dが5 - 3なら、AとDはおそらく互角である。 この理屈を延長していくと、プレイヤー間の相対的な棋力を数字で示すことができる。 チェスのレーティングシステムは、そのような数字を得ることを目指して発展してきた。 レーティングシステムの基本的な性質を以下に示す。 プレイヤーのそれぞれが持ち点を与えられ、勝敗によって増減する 勝てば持ち点が増え、負ければ減る。 順当な結果では持ち点の移動が少なく、番狂わせでは大きい つまり、金星と白星の重みが違う。ザコを何匹倒しても、大物を仕留めたプレイヤーには敵わない。 勝負の重み付けの方法 金星と白星の重みが違うといっても、点数としては具
pythonでskip list - yattのブログ
skip listというデータ構造をpythonで実装しました。listとありますが、実際には探索木のような構造で、 要素の挿入時に木をバランスさせる必要が無い lock-free なアルゴリズムだそうです。バランス操作が不要だと、並列プログラムと相性がよさそうというのは感覚的にわかります。まだ高度な実装は読んでないけれど。 画像は木構造用の画像化モジュールでskip listを画像化したものです。 'hello' => 'world' 'tic' => 'tac' 'hoge' => 'fuga' 'foo' = 'bar' の3組を格納した状態で出力させています。 追記：削除実装するの忘れてました。挿入とほぼ同じだからいいよね^^;
中里一日記: 正規表現マッチングはMap-Reduceできる
正規表現マッチングはMap-Reduceできる グレゴリオ暦で新年を祝われる皆様、あけましておめでとうございます。 今日のお題は正規表現。ただしチューリング完全なPCREではなく、有限オートマトンにもとづく本来の正規表現である。 一個の巨大な文字列に対する正規表現マッチングをMap-Reduceで分散計算することはできないと思い込んでいるマヌケな子はいねーがー？ できそうな気はするけれどアルゴリズムがわからないアホな子はいねーがー？ 大丈夫、このエッセイを読むまで私にもわからなかった。アホはあなただけではない。といってもなんの慰めにもならないが。 （このエッセイは正規表現のインクリメンタルマッチングの計算量について論じているが、分散計算のほうが例として自然と思ったのでそうした） 英語とHaskellができてモノイドとfingertreeが常識な人なら元のエッセイを読めばすべて一目瞭然だと思
私のブックマーク ： 簡潔データ構造
田部井靖生（科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員) はじめに 近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、 しかし、圧縮するとランダムアクセスをすることができないという欠点があります。 簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。 近年、集合、文字列、木、グラフデータを扱うための簡潔データ構造が提案され注目を集めています。 私たちの身近なアプリケーションとして、Google日本語入力では簡潔木LOUDSの実装が使われ、実際に使われはじめています。 また、有志によるそれらを解説したサイトやライブラリなども利用可能になりつつあります。 そこで、このページでは簡潔データ構造を用いた研究開発のためのいろいろなリソースを紹介します。 解説記
人工知能 - 粒子群最適化
このブラウザーはサポートされなくなりました。 Microsoft Edge にアップグレードすると、最新の機能、セキュリティ更新プログラム、およびテクニカル サポートを利用できます。 粒子群最適化 James McCaffrey コード サンプルのダウンロード 粒子群最適化 (PSO: Particle Swarm Optimization) は人工知能 (AI) の技術で、解決が極めて困難または不可能に思える、数値の最大化および最小化問題の近似解法を見つけるために使用します。今回の記事で説明する PSO のバージョンは、J. Kennedy 氏と R. Eberhart 氏が 1995 年に発表した研究論文で初めて紹介されました。PSO は、鳥の群れや魚の群雄などのグループ行動に基づいて大まかにモデル化されます。PSO の感触をつかみ、この記事の目的を理解するため、まず図 1 をご覧くだ
最近傍探索2011 - Preferred Networks Research & Development
こんにちは、二台目のmbaを買うのをためらっている岡野原です。 アイテム集合に対し、与えられたアイテムと似ているアイテムを求める、という近傍探索問題は古典的な問題でありながら、現在でも多くの改善がされています。特に言語情報、画像情報、行動履歴情報、生物情報、購買情報などありとあらゆるデータが高次元中の点として表現されるようになってきており、こうしたデータの最近傍探索は広い分野で応用範囲がある技術になっています。 アイテムが低次元（例えば2, 3次元）の場合はkd木や最近だとwavelet木を使う方法がありますが、今回扱うケースは各アイテムが高次元（数百万次元）中の点であったり、アイテム間の距離のみが定義されている場合（カーネル関数など）です。アイテム数は数万から数億ぐらいを想定しています。 最近傍探索問題はいくつかありますが、例えばk近傍グラフ構築問題では、 「アイテム集合X = x1,
GitHub - DEAP/deap: Distributed Evolutionary Algorithms in Python
DEAP is a novel evolutionary computation framework for rapid prototyping and testing of ideas. It seeks to make algorithms explicit and data structures transparent. It works in perfect harmony with parallelisation mechanisms such as multiprocessing and SCOOP. DEAP includes the following features: Genetic algorithm using any imaginable representation List, Array, Set, Dictionary, Tree, Numpy Array,
「R言語による Random Forest 徹底入門−集団学習による分類・予測−」− #TokyoR #11 で講師をしてきました - hamadakoichi blog
2011/01/29 第11回R勉強会＠東京(Tokyo.R #11) で講師をしてきました。 「R言語による Random Forest 徹底入門 −集団学習による分類・予測−」。 Random Forest は"機械学習"の方法論で、集団学習により精度高い判別・予測を実現します。 双方向の進行で、質疑応答・議論含め 合計60分で話しました。 「R言語による Random Forest 徹底入門 −集団学習による分類・予測−」 - #TokyoR #11View more presentations from Koichi Hamada. 隠れ Random Forest 祭り 今回のTokyo.R、実は「隠れ Random Forest 祭り」。直前の３トーク、「3. caretパッケージの紹介」(id:dichika [Twitter:@dichika])、「4. RにおけるHPC
dag_vector: ランダムアクセス可能な圧縮配列 - Preferred Networks Research & Development
こんにちは、この夏はシルキードライで乗り切りたい岡野原です。 今日は最近公開したC++のオープンソースであるdag vectorについて紹介します。 github: dag_vector ライセンスは修正BSDライセンスです。 dag vector (direct accessible gamma code vector) は値を圧縮して格納したまま任意の場所の値を高速に参照可能な配列ライブラリです。しかもデータ末尾への追記が可能です。 dag vectorはstd::vectorのように利用できます。下にいくつか例を見ていきましょう。 dag_vectorの例 #include "dag_vector.hpp" // dag_vectorは0以上の正整数の配列を扱う配列。 dag_vector dv; // 値はいつでも追加可能。追加された値は圧縮して格納される // 正整数xは2lg(
マルチコア時代の"データ構造とアルゴリズム"再入門
データ構造とアルゴリズム再入門 はじめに ・並{行|列} & {Lock|Wait}Free ・ABA & ABA' ・volatile ＆ メモリバリア ・プリミティブ ・CAS ・MCAS ・STM ・メモリ管理:free & GC ・Toots List & Skiplist [単方向List] ・リスト ・細粒度リスト ・Lazyリスト ・Lock-Freeリスト ・Lock-Freeリスト2 [SkipList] ・スキップリスト ・Lazyスキップリスト ・Lock-freeスキップリスト [双方向List] Queue & PriorityQueue [UnBounded Queue] ・Queue ・CAS based Lock-Free Queue ・LL/SC based Lock-Free Queue [Unbounded Priority Queue] ・Heap
MapReduce以外の分散処理基盤BSP, Piccolo, Sparkの紹介 - Preferred Networks Research & Development
どうも，実は今年から開発チームにjoinしていた中川です．可愛い犬の写真がなかったので，可愛いマスコットの画像を貼っておきます． 最近MapReduceとかその実装であるHadoopとかをよく聞くようになりました．これはつまり，それだけ大量のデータをなんとか処理したいという要望があるからだと思います．しかし当たり前ですが，MapReduceは銀の弾丸ではありません． ということで，最近気になっているMapReduceとは違ったアプローチを取っている分散処理基盤について，社内のTechTalkで話した内容を簡単にまとめて紹介したいと思います． Bulk Sychronous Parallel このアルゴリズム自体は1990年に誕生したものです．長いのでBSPと書きます．さて，グラフから最短経路を求める時，MapReduceは使えるでしょうか？このような論文が出るくらいですから出来ないことはあ
自然なアルゴリズム - 蜂コロニーのアルゴリズムを使用して困難な問題を解決する
このブラウザーはサポートされなくなりました。 Microsoft Edge にアップグレードすると、最新の機能、セキュリティ更新プログラム、およびテクニカル サポートを利用できます。 April 2011 Volume 26 Number 04 自然なアルゴリズム - 蜂コロニーのアルゴリズムを使用して困難な問題を解決する James McCaffrey | April 2011 蜂コロニーのシミュレーション (SBC: Simulated Bee Colony) アルゴリズムは、ミツバチの行動をモデル化するアルゴリズムで、解くのが困難または不可能に思える組み合わせ問題を解決できます。今回の記事では、SBC アルゴリズムとは何かを解説し、SBC アルゴリズムを使用して解決できる問題の種類について説明します。また、巡回セールスマン問題 (TSP: Traveling Salesman Pro
遺伝的アルゴリズムの紹介 - 人工知能に関する断創録
2001年の勉強会で発表した遺伝的アルゴリズムの紹介資料です。HDDをあさってたら見つけたので一応記録。ほんのさわりです。最近の研究ではどこまで進展したんでしょうね？遺伝的アルゴリズムって複雑系と人工生命の文脈で捕らえるのが面白いのに、研究だとただの探索アルゴリズムになっちゃうのが悲しかった。 はじめに 遺伝的アルゴリズム（Genetic Algorithm:GA）とは、生物進化（自然選択、突然変異）から着想を得た汎用的な探索手法です。探索というのは、たくさんの解の候補がある中から、最も良い解を探すことです。つまり、GAとは解の候補から最もよいものを探すのが目的と考えられます。 歴史的背景 GAは、1975年、Hollandによって初めて導入されました。当時は、「なぜ進化のような何十億年もかかるプロセスの真似をするのか？」という反応が多かったらしいです。しかし、その後のGoldbergの研
scipyを使ってPageRankを爆速計算する - SELECT * FROM life;
PythonPython用の科学技術演算用ライブラリとして有名なscipyに含まれている疎行列の計算用のモジュールを使ったPageRank計算用のモジュールを書きました。https://github.com/taka84u9/u9library/blob/master/link_analyser.py僕の研究室にある計算用サーバで動かしたところ、ノード数130万強のグラフに対しても30回の反復に対して約35秒程度で完了しました。詳しい使い方はdoctestとREADMEを参照してください。u9libraryには今後個人的に研究目的で作成したモジュールを順次追加していく予定です。関連エントリPageRankアルゴリズムの大規模実装における注意事項 - SELECT * FROM life;
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
この番付について
ネット学習して『モナー』も描ける、東工大のロボット
System Unavailable
CVXOPT: Python Software for Convex Optimization Programming
Archived MSDN and TechNet Blogs | Microsoft Docs