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のチームは
CHAGEの裏側: ブルームフィルタとISONの逆引き高速化 | IIJ Engineers Blog
セキュリティ本部 セキュリティ情報統括室に所属 システム開発者。2000年問題で「2038年問題は定年で対応しなくていい！」とフラグを...。 CHAGE開発者のヒラマツです。 前回（CHAGEの裏側: D3.jsの紹介）同様、CHAGEの紹介と並行して、CHAGEの中が気になる人に、CHAGEで使われている技術をちょっと濃い目に解説するという企画です。 今回は、本編（CHAGE の動き）がISONネタなので、こちらもISONに関係ある話として、ブルームフィルタについて書きます。 ブルームフィルタをざっくり解説してから、ブルームフィルタの具体的な使用例としてISONでの逆引き高速化の方法を紹介していきたいと思います。 目指すのは、ちゃんとした理解ではなく、「ブルームフィルタの雰囲気を知って、利用価値をなんとなく判断できる」ところです。 今回は、以下の知識を前提にしているので、そこはご了承く
テストの実行 - 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)
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が推定できるまで配信する事
モンテカルロ木探索 と TOTAL WAR: ROME II｜miyayou
TOTAL WAR : ROME II のAIでモンテカルロ木探索法（MCTS）が採用された。 モンテカルロ木探索は、９０年代から囲碁AIに応用されて来た方法であるが、２００６年頃に改良され（勝敗だけを取る）、囲碁AIに革命的進歩をもたらした。 その後、理論的基盤やさらなる（プレイアウトにおける）改良が加えられたが、基本的にはとてもシンプルな方法で、選んだ手の評価を、それ以降をランダムにシミュレーションして、良さそうならさらにシミュレーション回数を増やすという方法である。 ゲーム産業も長い間、注目して来て、ウィーンのゲームAI会議や、GDCで、解説講演が何度も開催されて来たが、実用例はなかった。 今回は、プレイヤーの対戦相手として、RTSのプレイをするAIに、MCTSが採用された。ゲームの局面局面で、その時に実行可能なタスクを生成する（task generation）。囲碁の手の代わりに、
OpenBSD、予測不可能なrand関数を実装（ただしPOSIX違反） | スラド デベロッパー
乱数が欲しいとき、言語の標準関数にrandやrandomという名前の関数があればそれを使うのは自然であろう。しかし、Cのrandはランダムではない。むしろ規定されているのはランダムネスではなく、その逆、srandによる予測可能性である。それにも関わらず余りにも多くのコードが定数やpidや現在時刻をシードにして安心しきっている。OpenBSDはPOSIXを破って、そのそうなアホなコードでもランダムになるよう変更を行った。 今後しばらくOpenBSDでsrandによる再現可能性を必要とする場合にはsrand_deterministicを呼ぶ必要がある (srandのユースケースをすべて調査したあとで元に戻す可能性はあるが）。このような乱暴な手法でセキュリティを実現しようとする独善的態度には批判もありそうだ。
多腕バンディットによる表示コンテンツの最適化 - クックパッド開発者ブログ
こんにちは。技術部検索グループの原島です。 上の画像は、スマートフォン（ブラウザ版）で見たクックパッドの検索結果ページです。レシピだけでなく、ニュースも表示されていますね。献立や掲示板のスレッドなどが表示されることもあります。 クックパッドでは、検索結果ページに表示するコンテンツをクエリなどに応じて最適化しています。最適化は、膨大なログデータと最新の機械学習を用いることで、実現しています。このエントリでは、クックパッドにおけるコンテンツ最適化の裏側を紹介します。 最適化の背景 スマートフォンの普及に伴って、ユーザが利用するプラットフォームは PC からモバイルにシフトしつつあります。クックパッドにおけるモバイル利用者の割合も、ここ 2 年で 10% 以上増加しました。最近では、60% 以上のユーザがモバイルからアクセスしています。 ユーザの利用形態が変化すれば、検索結果ページもその変化に対
How to Write a Spelling Corrector
One week in 2007, two friends (Dean and Bill) independently told me they were amazed at Google's spelling correction. Type in a search like [speling] and Google instantly comes back with Showing results for: spelling. I thought Dean and Bill, being highly accomplished engineers and mathematicians, would have good intuitions about how this process works. But they didn't, and come to think of it, wh
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
yowa on Twitter: "0.25*(popcount(rand64bit()) - 32) を正規乱数だと言い張るスタイル"
講談社サイエンティフィク on Twitter: "＼50周年！／『データサイエンス入門シリーズ』新刊2冊を抽選で3名に同時プレゼント。応募締切4/21(火) 23:59 『モンテカルロ統計計算』 https://t.co/gpURfqNqME 『データサイエンスのためのデータベ… https://t.co/NGXLQeSRT0"
乱択アルゴリズム紹介(行列乗算の検査&多項式等価性の検査) - Preferred Networks Research & Development
Bloom filter
