確率的プログラミング | POSTD
この数年で、プログラミング言語（PL）や機械学習のコミュニティは 確率的プログラミング（PP） を用いて、それぞれに共通する研究の関心事を明らかにしてきました。その概念は、抽象化のような強力なPLのコンセプトを”エクスポート”し、現状では複雑で困難な作業である統計的モデリングに再利用することができるかもしれない、というところにあります。 （講義ノートの 最新版 を閲覧したい方は、リンクをクリックしてください。ソースは GitHub に投稿してあります。誤りを発見した場合は、Pull Requestを送信してください。） 1. 何、そしてなぜ 1.1. 確率的プログラミングは○○○ではない 直観に反して、確率的プログラミングとは確率的に振る舞うソフトウェアを書くことでは ありません。 例えば、暗号のキー・ジェネレータやOSカーネルでの ASLR の実装、または回路設計のための 焼きなまし法
グラフ代数 | POSTD
数学や計算幾科学の分野において、 グラフ理論 は私のお気に入りのテーマです。この記事では、私が長年研究している グラフ代数 についてご紹介します。代数学は私にとって、グラフを扱う上で欠かせないツールになっています。皆さんにも、その便利さが伝われば幸いです。 私がグラフ代数の研究を始めたきっかけは、CONCUR 09という学会向けに提出した論文です。その論文は不採録でしたが、私はその後も特定用途向けのいくつかの論文を発表し、代数学の知識を深めていきました。その全容が記載された論文は、 ACM TECS でご確認いただけます（査読前の原稿は こちら です）。では早速、最もシンプルなグラフ代数の概要と、Haskellでの実装方法を紹介します。 グラフの作成 ここでは、固定領域に存在する頂点を持つ一式のグラフをGと表記します。例として、正整数の頂点を持つグラフについて考えてみましょう。グラフg ∈
データの次元削減に関する資料集 - めも
次元削減とは データの次元削減(Dimensionality reduction) + データの可視化(Data Visualization) PCA Principal Component Analysis(PCA) randomized PCA Online Robust Principal Component Analysis(OR-PCA) 多様体学習 t-Distributed Stochastic Neighbor Embedding(t-SNE) Multidimensional Scaling(MDS) Isomap Locally Linear Embedding (LLE) Laplacian Eigenmaps(LE) Semidefinite Embedding (SDE) Latent Dirichlet Allocation(LDA) Labeled LDA P
効率の良いパリティ計算方法 - Qiita
通信系のプログラムを書いていると、誤り検出のためにパリティビットを使用することがあります。 この記事ではuint32_t型の数値が与えられたときに、そのパリティを計算する関数を効率化することを紹介します。 関数の仕様 関数の仕様を以下のように決めます。 入力 uint32_t型の整数 出力 入力された整数を2進数で表現したときに、ビット1の数が偶数ならば0、奇数ならば1 とりあえず愚直に実装 とりあえずは、仕様を愚直に実装してみます。 32回のループを回して、1の数を数え上げています。 int parity(uint32_t val) { int count = 0; for(int i = 0; i < 32; i++) { if(val & 0x00000001) count++; val <<= 1; } return count & 0x00000001; }
Java で最速の乱数生成器を目指す: (3) ガンマ分布に従う乱数
TL;DR: ガンマ分布に従う乱数生成器を Java で実装し、Commons Math の実装と比較して 最大で約 16 倍 (任意の形状パラメータの乱数を生成する場合) の速度効率を達成しましたよ、というお話です。 (Header image: Mundhenk at en.wikipedia) ガンマ分布に従う乱数生成の実装方法Permalink これまで 正規分布に従う乱数生成、指数分布に従う乱数生成 をそれぞれ Java で実装してきましたが、今回はガンマ分布に従う乱数生成を Java で実装してみます。 ガンマ分布 は、形状パラメータ k>0 と スケールパラメータ θ>0 (もしくは形状パラメータ α=k と比率パラメータ β=1/θ) の 2 つのパラメータを持ち、その確率密度関数は次の式で表されます。 f(x)=xk−1e−x/θΓ(k)θk ガンマ分布の形状パラメータ
カルマンフィルタってなに？ - Qiita
はじめに この記事について そもそもカルマンフィルタってなに？なんのためにあるの？ 何を受け取って，何を出力しているの？ どういう原理で動いているの？ 最適カルマンゲインってなに？ というところを解説していきます． わかりやすさの向上のため，わかりにくいところや気づいたことがあれば気軽にコメントしてください． 書かれていないこと この記事ではカルマンフィルタの考え方を知っていただきたいので，最適カルマンゲインの導出方法やその先のことは書かれていません． \newcommand{\Xtrue}{\mathbf{x}^{true}} \newcommand{\Xest}{\mathbf{x}^{est}} \newcommand{\Xodo}{\mathbf{x}^{odo}} \newcommand{\Xobs}{\mathbf{x}^{obs}} \newcommand{\xtrue}{x
量子アニーリングで組合せ最適化 - Qiita
これはNextremer Advent Calendarの23日目の記事です。 現在、株式会社Nextremerでは早稲田大学の田中宗様と量子アニーリングに関する共同研究を行っております。 はじめに 量子アニーリングは組合せ最適化問題を解くための有効なアルゴリズムと言われています。 本記事では、量子モンテカルロ法による量子アニーリングを用いて、代表的な組合せ最適化問題であるTSP(巡回セールスマン問題)に対して解を求めたいと思います。 量子論の基礎 TSPの議論に入る前に、少しだけ量子論の基礎的なことに触れておきます。 物理量(エネルギーや運動量など)は、量子の世界では演算子というものに対応します。例えば、エネルギーという物理量に対応するものはハミルトニアン($\hat{H}$と表します)という演算子です。 このハミルトニアン $\hat{H}$ という演算子は、ある量子状態 $\psi$
外部メモリー付きのニューラルネット"Differentiable Neural Computing (DNC)"について解説するよ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事について DeepMind が Nature に投稿した論文 Hybrid computing using a neural network with dynamic external memory で使用されている "Differentiable Neural Computing (DNC)" について解説します。ロジックの説明がメインですが、Python - Chainer による実装例も紹介します。 Differentiable Neural Computing (DNC)とは sequential data を Neur
アルゴリズムとデータ構造 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 教科書を借りたので、主にそれに沿って。（講義？知らんがな） データ構造 列 配列 アクセス $O(1)$ アドレスが計算可能 挿入、削除 $O(n)$ 当該データ以降をずらす リスト アクセス $O(n)$ めぐるめぐるよ 挿入、削除 $O(1)$ つなぎ替えるだけ スタック アクセス可能な位置を限定したので$O(1)$。 LIFO。 待ち行列 $O(1)$。 FIFO。 木 ノードと葉からなる。 子供の数が任意である場合、子供の持ち方（順序が大事なら列、そうでなければ集合の持ち方の中から）考えなければならない。 集合 優先度付き待ち行
suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog;
文字列アルゴリズムを学んでいると、suffix array(接尾辞配列)という配列が出てくる。これは文字列の接尾辞の集合を辞書順にソートし、その順でそれぞれの接尾辞の文字列中の開始位置のindexを格納した配列のことである。以下が参考になる。 接尾辞配列 - Wikipedia サービス終了のお知らせ 例えばbananaの場合、接尾辞は - banana (position=0) - anana (position=1) - nana (position=2) - ana (position=3) - na (position=4) - a (position=5)となり、これを辞書順にソートしたものは - a (position=5) - ana (position=3) - anana (position=1) - banana (position=0) - na (position=
Suffix Trieを使って文字列マッチングする - $shibayu36->blog;
文字列マッチングを行うためのアルゴリズムとして、Suffix Trieを使った探索というものがある。これはテキストからSuffix Trieという構造を作り、パターンをつかってそれを辿ることで、パターンの長さmに対して、O(m)の計算量で探索できるものである。 今回はJavaでSuffix Trieを使った探索をしてみた。 トライ木とパトリシア 先にトライ木とパトリシアについて紹介。 今回Suffix Trieという構造を調べていると、同じような構造としてSuffix Treeというものが出てきて混乱した。よく調べてみると、Suffixの集合をトライ木という構造で実装したものがSuffix Trieで、パトリシアという構造で実装したものがSuffix Treeらしい。 トライ木はnodeを連結していって、その枝に1文字を割り当てて辿れるようにした構造。トライ木は枝に1文字しか割り当てない構
（ 事例調査 ）トポロジー・ 微分幾何学・ 情報幾何学 の 高み から、（深層）ニューラル・ネットワークモデル の 情報処理過程 を 可視化し、学習速度 を 早める 視座 の 有効性 を 考える - Qiita
（ 事例調査 ）トポロジー・ 微分幾何学・ 情報幾何学 の 高み から、（深層）ニューラル・ネットワークモデル の 情報処理過程 を 可視化し、学習速度 を 早める 視座 の 有効性 を 考える人工知能深層学習DeepLearning情報幾何学InformationGeometry （深層）ニューラル・ネットワークモデル を 改良して、 局所最適解への陥落 を 防ぎ、 なるべく短い学習回数で、全体最適解 に 到達する より良い (Deep) neural networkモデル を 見い出す 上 で、 【 情報幾何学（微分幾何学）の 見地 】 （１）誤差逆伝播（BP）法 の パラメータ更新式 を Riemann空間で組成し、 （２）フィッシャー行列 で 表現される Riemann計量 を 用いる 方法 及び 【 位相幾何学 の 見地 】 （１）(Deep) neural network モデ
複素数演算による幾何ライブラリの実装 - ヘクトのメモ
この記事はMCC Advent Calendar 2016 15日目の記事です．ICPC向けの複素数演算による幾何ライブラリの実装について話します． MCC Advent Calendar 2016 - Adventar 遅れてすいません... 背景 ICPCでは幾何の問題が出てきます． ただし，ICPCでは電子的な事前準備の禁止と標準ライブラリしか使えない制約があります． このため，標準ライブラリ縛りで幾何に必要な関数を一から実装する必要があります． しかし，事前準備なしで幾何に必要な関数を実装するのは大変なことであり，多くのチームは紙媒体でライブラリを用意していると思います． 幾何に必要な関数を一から実装するとコード量も膨大になりがちです． そこで，複素数演算を活用することで実装量を減らすことができます． (ただし，2D限定です．あと，事実だけを淡々と書いていきます．) ベクトル 2次
Suffix ArrayをRustで実装した - Islands in the byte stream
suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog; を読んで、ちょうど自分も何らかの形で全文検索を一部実装してみようと思っていたのでRustで真似してみました。 Rustを選んだ理由は、以下の理由からです。 実際に全文検索を実装するのに耐えうるパフォーマンスであること パッケージマネージャなどのエコシステムが完備されていること Rustについてはそれほど詳しくはないのですが、GCや例外がないとのこと。であればパフォーマンスチューニングがC言語並にやりやすい可能性がありますし、一度真面目に勉強してみたいと思っていました。Goと異なり、ジェネリクスがあるのも魅力的です。 というわけでコードこんな感じになりました: pub fn make_suffix_array(s: &str) -> Vec<i64> { use
木の直径を求めるアルゴリズム - ペケンペイのブログ
注意：議論が洗練されておらず、真面目に読むべき記事ではありません。信頼できそうなグラフ理論の書籍を読んだほうが良いと思います。ウェブ上で閲覧できる資料としては以下があり、そこの References を辿ると良いでしょう。 http://mathworld.wolfram.com/GraphCenter.html 中心が高々 2 個であることと、2 個あるならばそれらは隣接していることは F. Harary の ''Graph Theory'' に証明があります。p. 35 の Theorem 4.2 Every tree has a center consisting of either one point or two adjacent points. がそれです。頻繁に参照される記事ではありませんので、この記事を改訂する予定は今の所ありませんが、幾らか思うところがあるので希望があれば
力づく法・分割統治法・動的計画法 - アルゴリズム学習(その5) - $shibayu36->blog;
アルゴリズムの設計手法として、力ずく法・分割統治法・動的計画法というような考え方があった。新しいアルゴリズムを学ぶ時、どの設計手法でやっているのだろうかと意識しておくと、頭に入りやすい気がした。そこで、自分の頭を整理するためにメモを書いておく。自分用メモなので、情報の正確さについては保証がない。 力づく法 全探索する方法 アルゴリズムの考え方としては単純なことが多いが、かなり遅いものになることが多い 例えば、Nクイーンなら、N個の置き方を全通り作って、それぞれが条件をみたすか確認し、条件を満たしたら返すようなもの。Nの二乗のなかから、N個の組み合わせを作って試すので、計算が膨大になる 例えば文字列マッチなら、1文字ずつずらしながら、マッチさせたいパターンとテキストの文字を比較していくようなもの 分割統治法 Wikipediaによると、そのままでは解決できない大きな問題を小さな問題に分割し、
オセロの着手可能位置生成 【ビット演算テクニック Advent Calendar 2016 23日目】 - prime's diary
はじめに この記事はビット演算テクニック Advent Calendar 2016の23日目の記事です。 www.adventar.org オセロとビット演算 オセロは盤面サイズが8x8=64マスなので、64bit変数を2つ用意し、1つめを自分の石（あるいは黒石）の位置を、2つめを相手の石（あるいは白石）を表すために使うと合計128ビットで自然に表現できます。*1 自然に表現できるだけでなく、盤面の回転や反転などもDelta swapとその応用 【ビット演算テクニック Advent Calendar 2016 3日目】 - prime's diaryで紹介したような方法で効率的に行なえます。 着手可能位置の生成はタテ・ヨコ・ナナメの一直線上をpextなどで取ってきて表引きをすることにより、ある程度の速度で可能ですが、(38=6561なのでL1キャッシュに乗る程度の大きさとはいえ)メモリアク
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
How GPS navigation works using Breadth-First Search (BFS) | HackerEarth Blog
再帰的なアルゴリズムの実例集 - Qiita
ビット演算テクニック Advent Calendar 2016 - Adventar
