1次元ランダムウォーク - ei1333の日記
初心者向け 1 次元ランダムウォーク 数直線があって、原点 に点 がある。 時刻が 進むごとに、点 の位置が確率 で 、確率 で 動く。 この確率モデルを (対称な) 次元ランダムウォークと呼ぶ。 パスの個数 横軸を時間軸、縦軸を点 の位置を表すこととすると、以下のような折れ線グラフで表すことができる。 を、原点から点 までのパスの個数（言い換えると、時刻 に位置 に至る経路数）とする。 と から、ランダムウォークで した回数 と した回数 をそれぞれ計算できる。 より、 となる。("45度回転"に相当する) したがって と の偶奇が一致しているとき と二項係数を用いて表せる。 auto L = [&](int t, int x) -> modint { if(t % 2 != abs(x) % 2) { return 0; } else { return beet.C(t, (t + x
C言語による乱数生成
本文章はC言語を用いて様々な確率分布に従う乱数を生成する方法やコードをまとめたものである。rand関数やメルセンヌ・ツイスタの使い方から始まり, 正規分布・指数分布等の様々な確率分布に従う乱数の生成方法について解説する。このページは近江崇宏によって作られました。コードはご自由にお使いになってかまいませんが、バグ等によって生じた損失に対する責任は負いません。 道しるべ: ・Ｃ言語でお手軽に整数の乱数を発生させたい人 ==> C言語のrand関数の使い方 ・メルセンヌ・ツイスタの使い方を知りたい人 ==> メルセンヌ・ツイスタの使い方 ・一様乱数の生成方法を知りたい人 ==> 一様乱数 ・様々な確率分布に従う乱数生成法を知りたい人 ==> 各種の確率分布に従う乱数の生成法 入門編 C言語のrand関数の使い方 メルセンヌ・ツイスタの使い方 乱数生成の基礎 一様乱数 (Uniform Rando
SQL実行時のブルームフィルタ(Bloom Filter)アルゴリズム | フューチャー技術ブログ
1. 初めにDBにおける処理はSQLによって記述しますが、データの取得するために具体的にどのような内部処理を行うかという点までは記述しません。 ここでいう内部処理とは「SQLの書き換え」「インデックスの使用」「結合アルゴリズムの選択」などがDBMSのオプティマイザによって選択されて実施されることを指します。 SQLのパフォーマンスを見るにあたっては上記の内部処理について正しく理解する必要があります。 本Blogでは、重要なアルゴリズムであるにもかかわらず、まとまった情報が少ないSQL実行時におけるブルームフィルタ(Bloom Filter)についてOracleをもとに紹介を行います。 Bloom Filterは結合処理を効率化するために、結合の前段階で利用される技術になります。 公式なドキュメントとしては以下になります。 Oracle Database SQLチューニング・ガイド 12cリ
確率的データ構造の比較：カッコウフィルタ対ブルームフィルタ | POSTD
確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
5_特集_3校_0724.indd
MEDICAL IMAGING TECHNOLOGY Vol. 32 No. 3 May 2014 155 確率的画像処理の手引き −マルコフ確率場モデルと確率伝搬法− 安田 宗樹＊1 本稿では確率的画像処理の枠組みの基礎を成しているマルコフ確率場とその計算アルゴリズムとし ての確率伝搬法 サムプロダクト確率伝搬法とマックスプロダクト確率伝搬法 について議論する これらの概念は最新の確率的画像処理分野においても重要な位置を占めている確率的画像処理の基礎 数理を説明しノイズ除去フィルタへの応用を通して確率的画像処理への導入を手引きする 確率的画像処理マルコフ確率場ベイズの定理確率伝搬法画像修復 Med Imag Tech 32 3 : 155︲163, 2014 1. 確率モデルを基礎とした画像処理システムに 関する研究が 最近の画像認識処理を含めた画 像処理分野 コンピュータビジョン co
機械学習ナイーブベイズ分類器のアルゴリズムを理解したのでメモ。そしてPythonで書いてみた。 - Qiita
概要 ナイーブベイズ分類器(ベイジアンフィルター)のアルゴリズムを具体的な数値を使って説明します。また、Pythonで実装してみました。自分の勉強メモのつもりで書いたのですが、他の方の役にも立てたら嬉しいです。 ナイーブベイズ分類器って？ あるデータ(文章)をどのカテゴリーに属するのかを判定させる、機械学習の教師あり学習の手法の一つです。 スパムメールフィルターやWEBニュース記事のカテゴライズによく使われています。 難易度 ベイズの定理を利用した単純な手法で、難易度は低です。 なるべく数式を使わないで説明してみました。 ナイーブベイズ分類器の計算 対象文章がどのカテゴリーに分類されるかを決めるための計算ロジックを、具体的な数値を使って説明します。 学習データが以下である場合、対象文章がどのカテゴリーに分類されるか計算します。 学習データ サッカー [ ボール | スポーツ | ワールド
ナイーブベイズについて勉強したのでざっくりまとめ | DevelopersIO
概要 こんにちは、データインテグレーション部のyoshimです。この記事は機械学習アドベントカレンダー6日目のものとなります。 今回は「ナイーブベイズ」という手法を説明してみようと思います。 ナイーブベイズは「学習が高速、かつ実装が容易」といった実用性の観点から利用されることの多いアルゴリズムです。 (より精度が高いアルゴリズムやナイーブベイズを元にした発展系も存在します) なお、今回のエントリーではナイーブベイズの「理論」の部分だけで、実際にやってみた例については後日公開しようと思います。 目次 文書を単語単位に分割する ベイズの定理とは ナイーブベイズとは まとめ 文書を単語単位に分割する 早速、「ナイーブベイズ」について説明していきたいのですが、その前に「自然言語を機械学習で扱う際によくやる前処理」について説明します。 今回の記事では、ナイーブベイズを使って「文書分類」をする例で説明
テストの実行 - C# を使用した Thompson Sampling
注意 このページにアクセスするには、承認が必要です。 サインインまたはディレクトリの変更を試すことができます。 このページにアクセスするには、承認が必要です。 ディレクトリの変更を試すことができます。 February 2018 Volume 33 Number 2 テストの実行 - C# を使用した Thompson Sampling James McCaffrey Thompson Sampling は、多腕バンディット問題の解を求めるために使用できるアルゴリズムです。用語「多腕バンディット」は、ギャンブルに使われるスロットマシンの俗称が「one-armed bandit (片腕バンディット)」だったことに由来します。 ここに 3 台のスロットマシンがあるとします。3 台のうちの 1 台のハンドルを引くと、誰も知らない何らかの確率分布に従って、掛け金を失うか、1 ドルが払い戻されます。
確率DPを極めよう - 確率と期待値の問題解説
DP tsutaj (@_TTJR_) Hokkaido University B4 February 20, 2018 tsutaj (Hokkaido Univ.) DP February 20, 2018 1 / 54 1 2 ( ) ( ) HSI 3 4 RareItems (Hard) 5 tsutaj (Hokkaido Univ.) DP February 20, 2018 2 / 54 (Dynamic Programming) tsutaj (Hokkaido Univ.) DP February 20, 2018 3 / 54 DP DP DP tsutaj (Hokkaido Univ.) DP February 20, 2018 4 / 54 A P(A) = A : 6 1 5 P(x ≥ 5) = 1+1 6 = 1 3 A P(Ā) = 1 − P(A)
EMアルゴリズム徹底解説 - Qiita
ステップ2 $r_{nk}$を固定して$J$を$\mu_k$で偏微分して最小化します。 式変形をすると、 クラスタ$k$の最適なCentroidは上記のように、クラスター$k$に所属しているデータの平均であることがわかりました。 上記より最初のデモンストレーションで行っていたアルゴリズムは損失関数$J$の最適化によって導出されたものを適用していたことがわかります。 2−3. 実装 上記で示した２ステップを計算して、イテレーションを回すだけのシンプルなプログラムです。最後に更新前のmuと更新後のmuの差を取り、それがある程度小さくなったら収束したと判断し、イテレーションを止めるようにしています。 下記はアルゴリズム部分の抜粋です。プログラムの全文はコチラにあります。 for _iter in range(100): # Step 1 =============================
Bloom Filters by Example
A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. The price paid for this efficiency is that a Bloom filter is a probabilistic data structure: it tells us that the element either definitely is not in the set or may be in the set. The base data structure of a Bloom filter is a Bit Vector. Here's a small one we'll use to
Bloomフィルターについて調べた
Eric Redmond & Jim R. Wilson 著の”Seven Databases in Seven Weeks” を読んでいたところ、Ch.8 Redis の Day2 で書籍名の重複チェックに Bloom Filter という確率的データ構造(アルゴリズム?)が利用されていた。本ではさらっとしか触れられていなかったので調査。 処理の流れ 材料 ビット配列(m ビット) ハッシュ関数(k個。整数1からm のどれかをかえす) 作り方 下ごしらえ ビット配列の各ビットは予め0で初期化しておく。 各初期データをk個のハッシュ関数に食わせ、ハッシュ関数のかえすビットを立てる。 重複チェック 重複チェックしたい入力値をk個のハッシュ関数に食わせる ハッシュ関数のかえすビットがビット配列で立っているかチェック すべてのビットが立っていれば、重複と判定。 一つでも立っていないビットがあれば
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
Algorithms for calculating variance - Wikipedia
Algorithms for calculating variance play a major role in computational statistics. A key difficulty in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead to numerical instability as well as to arithmetic overflow when dealing with large values. A formula for calculating the variance of an entire population of size N is: Usin
Web広告配信における多腕バンディット問題、Mortal Multi-Armed Bandits Problemとアルゴリズム - CARTA TECH BLOG
こんにちは@hagino3000です。Zucks Ad Networkという広告配信サービスの開発をしています。最近はアドネットワークの広告配信最適化に利用できるアルゴリズムの調査もしています。 本稿では調査で読んだ論文の一つ、オンライン広告配信を想定した多腕バンディット問題である、Mortal Multi-Armed Banditsを紹介します。多腕バンディット問題になじみがある読者を想定しています。 papers.nips.cc オンライン広告と多腕バンディット問題 ここでは簡単のために、クリック課金型のディスプレイ広告を前提に説明します。オンライン広告配信システムにおける問題として「最初はどの広告がどれだけクリックされるかわからないが、なるべくクリックされる広告を多く配信したい。」という物があります。これは多腕バンディット問題として知られており、探索はCTRが推定できるまで配信する事
じゃんけんが終わるまでの平均回数を求める - 唯物是真 @Scaled_Wurm
じゃんけんをするときに人数が多いとあいこが増えて、なかなか終わらなかった経験があると思います \(n\)人でじゃんけんした時に、ただ1人の勝者が決まるまでの回数の期待値(平均回数)を計算してみました また大人数でもすぐに勝負がつくゲーマーじゃんけんも取り上げています この記事ではある人がグー・チョキ・パーを出す確率はそれぞれ等しいとします じゃんけん まず結果が知りたい人のために最初にグラフを載せておきます 横軸が人数、縦軸がただ一人の勝者が決まるまでのじゃんけんの平均回数です \(10\)人で約\(24\)回、\(15\)人で約\(159\)回と、人数が増えると回数の期待値が急激に増えていくのがわかると思います 人数 回数の期待値 1 0 2 1.5 3 2.25 4 3.21428571429 5 4.48571428571 6 6.2198156682 7 8.64673579109
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The art of solving problems with Monte Carlo simulations | Gabriel Carvalho
機械学習初心者がナイーブベイズに手を出してみる (1) - 理論編 - Qiita
乱択アルゴリズム紹介(行列乗算の検査&多項式等価性の検査) - Preferred Networks Research & Development
https://www.astr.tohoku.ac.jp/~chinone/Markov_Chain_Monte_Carlo/Markov_Chain_Monte_Carlo.pdf