Alias method - Wikipedia
A diagram of an alias table that represents the probability distribution〈0.25, 0.3, 0.1, 0.2, 0.15〉 In computing, the alias method is a family of efficient algorithms for sampling from a discrete probability distribution, published in 1974 by Alastair J. Walker.[1][2] That is, it returns integer values 1 ≤ i ≤ n according to some arbitrary discrete probability distribution pi. The algorithms typic
Walker's Alias Methodの箱の作り方のわかりやすい説明 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 指定された重みに従って離散的な値を確率的に選択したい、ということがよくある。例えば[1,4,5]という配列が与えられた時、確率10%で0、40%で1、50%で2というインデックスを返すような関数が欲しい。 普通に考えると部分和をとって乱数を一度振り、どの場所が選択されたか二分探索で調べる、というアルゴリズムが思いつくが、これは要素数Nに対して$O(\log(N))$の手間がかかる。logの手間というのは無視できることが多いが、この関数呼び出しが頻繁にある場合には無視できないコストになる。 さて、こんな用途のためにWalker'
蟻本シリーズ 2 ランダムウォーク - StatModeling Memorandum
今回は以下のランダムウォークの問題を考えます。 I×Jの大きさのグリッドがあります。(1,1)からスタートして、1ターンに上下左右4マスのうち移動できる方向にそれぞれ確率p1,p2,p3,p4で移動します。いくつかのマスには石が置いてあり、通行不可能になっています。(I,J)にはじめて辿り着くまでにかかるターン数の期待値を求めなさい。ただし、(1,1)から(I,J)に移動するパスが少なくとも1つは存在すると仮定します。 例：I = 3, J = 10 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [1,] 1 0 1 1 1 0 1 1 1 0 [2,] 1 0 1 0 1 0 1 0 1 0 [3,] 1 1 1 0 1 1 1 0 1 1 0が石があるマスで、1が移動できるマスです。以降ではこのグリッドを「グリッドA」と呼びます。
ソフトウェアのための統計学 – 前編 | POSTD
ソフトウェア開発の原点は可能性の追求であり、不可能を可能にすることです。ひとたび ソフトウェア が開発されると、エンジニアは次に 程度 という課題に向き合うことになります。企業向けのソフトウェアであれば、「速度はどれくらいか」と頻繁に問われ、「信頼性はどの程度か」という点が重視されます。 ソフトウェアのパフォーマンスに関する質問に答え、さらには正しい内容を語る上で欠かせないのが統計学です。 とはいえ、統計学について多くを語れる開発者はそうはいません。まさに数学と同じで、一般的なプロジェクトで統計学が話題に上ることなどないのです。では、新規にコーディングをしたり、古いコードのメンテナンスをしたりする合間に、手が空くのは誰でしょうか？ エンジニアの方は、ぜひ時間を作ってください。近頃は、15分でも貴重な時間と言えるでしょうから、 こちらの記事をブックマークに追加 しておいてもいいでしょう。とに
基本的なテンプレートマッチング
概要 テンプレートマッチングはテンプレート画像を入力画像で走査させ，入力画像上の各位置における類似度を算出し， 最大（もしくは，しきい値以上）の類似度をとる位置を検出する手法です． 本ページではテンプレートマッチングの基本的な類似度指標である，Sum of Abusolute Difference(SAD), Sum of Squared Difference(SSD)，Normalized Cross-Correlation(NCC)， Zero-means Normalized Cross-Correlation(ZNCC)について解説します． Sum of Abusolute Difference(SAD)，Sum of Squared Difference(SSD) SADはテンプレートfと入力画像gの濃度値の差の絶対値和，SSDは差の2乗和です． 「各画素値の違いの量」の累積値な
Otsu's method - Wikipedia
An example image thresholded using Otsu's algorithm Original image In computer vision and image processing, Otsu's method, named after Nobuyuki Otsu (大津展之, Ōtsu Nobuyuki), is used to perform automatic image thresholding.[1] In the simplest form, the algorithm returns a single intensity threshold that separate pixels into two classes – foreground and background. This threshold is determined by mini
How to calculate binomial probabilities
Suppose you’re doing something that has probability of success p and probability of failure q = 1 − p. If you repeat what you’re doing m+n times, the probability of m successes and n failures is given by Now suppose m and n are moderately large. The terms (m+n)! and m! n! will be huge, but the terms pm and qn will be tiny. The huge terms might overflow, and the tiny terms might underflow, even tho
NABENAVI.net
ゲーム理論，賭けの科学を中心としたサイトNABENAVI.netです． CONTENTS ゲーム理論のナビゲータ 研究活動 賭けの科学 じゃんけん研究 プロフィール リンク 連絡先・アクセス いろいろ このサイトは 更新履歴 新着情報 - 最近の更新 「じゃんけん研究」のページを更新．(2010.09.18) 待望の「じゃんけん研究」のコンテンツ作成へ踏み出しました．まず，話題の「わたなべじゃんけん」の解説とビデオを公開！(2008.04.26) ゼミナールゲーム理論に誤り・誤植が見つかっています（特に演習問題の解答）．皆様には御迷惑をおかけしています．正誤表と訂正を「ゼミナールゲーム理論入門」のページに掲載しています．(2008.04.23) 「ゼミナールゲーム理論入門」の発売に関して，コンテンツを整理しました．古い講義資料などはなくなりました．これまでの講義ノートは「ゼミナールゲーム理
Apache の mod_proxy_balancer のスケジューリングアルゴリズム - KoshigoeBLOG
まじめに調べた事がないと気づかされたので、ドキュメントを頼ってお勉強。 mod_proxy_balancer - Apache HTTP サーバ mod_proxy - Apache HTTP サーバ まず、mod_proxy_balancer では、２種類のアルゴリズムを選択できる。リクエスト回数ベースの Request Counting と、トラフィック量ベースの Weighted Traffic Counting の２種類。設定は、lbmethod で行う。 Request Counting Request Counting は、lbmethod=byrequests とすると有効になる。このスケジューリングアルゴリズムを左右するパラメータは、lbfactor と lbstatus の２つ。 設定パラメータ lbfactor は、ワーカーに割り当てる仕事量を意味する(クオータ)。lb
書評: 集合知プログラミング(Programming Collective Intelligence) | 秋元@サイボウズラボ・プログラマー・ブログ
献本いただいたもの。 翻訳が出ると聞いてからずっと気になっていた本なので、いただけたのはとてもラッキーだった。 集合知プログラミング 著者／訳者：Toby Segaran 出版社：オライリージャパン( 2008-07-25 ) 定価：￥ 3,570 原題(Building Smart Web 2.0 Application)にあるとおり、集合知プログラミングは、ウェブサイトの背後でいろいろと賢いことをするために使えるいろいろな技法を広く紹介した技術書だ。 大勢の過去の行動データから推薦を行なう 集団をグループに分ける 検索エンジンとランクづけ 最適解を低コストで見つける スパム判定 条件判定のルールを生成する 価格モデルを作っての価格予測 カーネルメソッドやサポートベクトルマシン 遺伝的プログラミング といったトピックが、Pythonのサンプルコードとあわせて解説されている。 内容は、読む
「馬券の配当160億円」をどうやって実現したのか - 朝日新聞の補足記事 - アフター・パンデミック
ちまたの競馬予想会社のうさん臭さは、「そんなに儲かるならなぜ自分で買わない」という言葉で表されるが、ほんとに儲かる人間はやはり自分で馬券を買っていることを証明した事件だと言える。 asahi.com（朝日新聞）が競馬の配当１６０億円隠す 英国人社長のデータ分析会社という記事を報じているが、新聞紙面ではその隣に関連記事も掲載されているので、これを引用する。 「なぜそんなに稼げた - 3連単を分散買い」（2009年10月9日付朝日新聞より） ユープロ関係者らによると、同社は、天候や出走馬の血統、騎手などの各データを入力、解析する競馬必勝プログラムを使い、高確率で配当金を得ていたという。だが、億単位の資金を使い、ほとんどの組み合わせの馬券を買うという、一般の競馬ファンにはまねできないやり方だった。 05年設立の同社が目をつけたのは、「3連単」という馬券。1着から3着までを順番通り当てるもので、配
How Not To Sort By Average Rating
By Evan Miller February 6, 2009 (Changes) Translations: Dutch Estonian German Russian Ukrainian PROBLEM: You are a web programmer. You have users. Your users rate stuff on your site. You want to put the highest-rated stuff at the top and lowest-rated at the bottom. You need some sort of “score” to sort by. WRONG SOLUTION #1: Score = (Positive ratings) − (Negative ratings) Why it is wrong: Supp
The Danger of Naïveté
07 Dec 2007 The Danger of Naïveté In my previous post on shuffling, I glossed over something very important. The very first thing that came to mind for a shuffle algorithm is this: for (int i = 0; i < cards.Length; i++) { int n = rand.Next(cards.Length); Swap(ref cards[i], ref cards[n]); } It's a nice, simple solution to the shuffling problem: Loop through each card in the deck. Swap the current c
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ゼロ平均正規化相互相関 - PukiWiki
Quasi-random sequences
ウォール・ストリート、暴走するアルゴリズム(1/5)
http://www.sci.kagoshima-u.ac.jp/~ebqc/miyatake01/
はてなブログ | 無料ブログを作成しよう
Erlang: 組合せをやってみる | | プログラマ2.0日報 | あすなろBLOG
HatenarMaps - はてな村勢力地図