そんな大層なものではないジャンルのやつです。
N列の数字列（初期はすべて0）を用意して、どんどん伝播させていきます。
伝播させるごとにそれぞれの数値にゆらぎが生じて・・・
等確率で+1,0,-1の変化をします。
さて、n回伝播したとき、どれくらいデータはぐちゃぐちゃになっているでしょーか？
つまり、そのデータの分散値（Σx^2)はどんくらいでしょーか？
まあ、基本的にはランダムウォークなので、もにょもにょと計算すれば一発です。
データ列が∞、すなわちN→∞ のときは、そのデータ内でランダムウォークすべての状態が網羅されていると考えてよいので、
分散： σ^2 = 2/3 n となります。
問題はNが有限のときです。このときは、標本分散、s^2がサンプリングごとにゆらぐ、つまるところ確率変数とみなしてよいことになるので、
s^2をたくさんサンプリングしてその平均をとれば、中心極限定理より"真な"s^2（μ(s^2))が求まる気がします。
というわけで、ざくざくと最近勉強中のHaskellでデータを集めて計算してみると、
μ(s^2) = 2/3 *(1-1/N) * n
となりますた。当たり前ですけど、データ列が小さいほうが情報の崩壊が少ないっつーわけですね。
2013年9月17日火曜日
2012年10月12日金曜日
情報の誤伝達５
今回は次のための準備みたいなものです。
伝えたい情報は｛0 0 0 0 0 0 0 ..... 0｝とします。
そして、今まではどれだけズレても±1か0かどう動くかは等確率1/3でした。
今回は、確率が「復元力」を持つと仮定しましょう。
この仮定は、
「ズレが大きくなく情報にある程度の常識があり、そこから伝達を類推できる。」
という状況を以ていい近似になりうります。
そして、復元力、確率は各々の情報要素で独立に振る舞うとします。
（次に話したいものはこの復元力によって隣の情報要素と相互作用させようというもの）
その復元力をどうするかですが、単純にズレの距離に比例にしてしまうと、
負の確率がでてきてしまうので、少し改変します。
おいおい話しますが、流れを切らないために、式を先に示します。
ここで、dはどういう値かというと、いわゆる「バネの伸びの限界」で、
「xがdになると、P(-1)とP(1)の比がほぼ１０倍になる」としています。
つまりdが大きければ大きいほど、復元力は弱いということになります。
参考までに、d=1でのプロットを乗せておきます。青がP(-1),赤がP(+1)です。
これを用いて、Javaでシミュレーションしてみたいと思います。
この前のやつのr部分だけいじりたいと思います。
import java.util.*;
class InfoDest2 {
static double pneg (int x,double d){
return Math.exp(x/d)/3/Math.cosh(x/d);
}
static double ppos (int x,double d){
return Math.exp(-x/d)/3/Math.cosh(x/d);
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
int k = sc.nextInt(); //情報数(配列の長さ)
int n = sc.nextInt(); //試行回数
double d = sc.nextDouble(); //バネ限界伸び
while(data>0){ calc(k,n,d); data--;}
}
static void calc(int k,int n,double d) {
int[] a = new int[10];
//最初の値は全部0なのでこのままでいきます。
for(int i=0; i<n; i++){
for(int j=0; j<k; j++){
double rd = Math.random();
int r;
if(rd<=pneg(a[j],d)) r=-1;
else if(rd>=ppos(a[j],d)) r=1;
else r=0;
a[j] = a[j] + r;
}
}
double avr=0; double var=0;
for(int i=0; i<k; i++){
System.out.print(a[i]+", ");
avr += Math.abs(a[i]);
var += a[i]*a[i];
}
System.out.printf("誤り距離平均: %.2f, 誤り分散: %.2f %n",avr/k,Math.sqrt(var));
}
}
ことさら変わったところもないので、ちっちゃくしときます。
入力にバネ限界伸びが追加されました。
5 5 100 1 で出力してみる。
2, 1, 3, 2, 2, 誤り距離平均: 2.00, 誤り分散: 4.69
3, 3, 2, 0, 0, 誤り距離平均: 1.60, 誤り分散: 4.69
-1, 3, -1, 0, 0, 誤り距離平均: 1.00, 誤り分散: 3.32
0, 0, 2, -1, 1, 誤り距離平均: 0.80, 誤り分散: 2.45
2, 6, 3, 1, 0, 誤り距離平均: 2.40, 誤り分散: 7.07
ちなみに、復元力なしの場合（5 5 100)
10, 2, 0, 2, 7, 誤り距離平均: 4.20, 誤り分散: 12.53
-5, -6, -16, 20, 6, 誤り距離平均: 10.60, 誤り分散: 27.44
0, -5, -13, 8, 1, 誤り距離平均: 5.40, 誤り分散: 16.09
2, 11, 15, 2, 12, 誤り距離平均: 8.40, 誤り分散: 22.32
2, -8, -13, -1, 1, 誤り距離平均: 5.00, 誤り分散: 15.46
たしかにdが大きくなるほど、誤り距離平均は大きくなっています。
---------------------------------------------
最後に書き残していたP(-1)とP(+1)の求め方について説明しておきます。
まず、非負をとる関数で扱いが容易であるものとして
exp(kx)とexp(-kx)を考えます。
もちろん、
P(-1) ∝ exp(kx)
P(+1) ∝ exp(-kx)
となるだろうと思うわけですが、今回は確率を考えたいので、この両者の割合、
とします。ここでλは定数です。
λを決める。確率は1なのだから、
P(0) + P(+1) + P(-1) = 1
P(+1) + P(-1) = 2/3
で、計算すると、λ = 2/3となります。（まあそりゃそうだ）
最後に、ハイパボリックコサインの定義式：
を代入すれば、上の式に近い値が得られます。
最終的にkをバネ限界伸びdで表すのですが、これは簡単で、
P(+1)/P(-1) = exp(-2) ～ 0.1 として計算すればよいです。
なぜexp(-2)にするかですが、これは式が綺麗になるから以外に理由はないかな…。
ですがまあ大体10倍比であれば、ほぼそれ以上伸びないと思っていいだろう。
「指数関数でいいのか」と思うかもしれないですが、
dを大きくすれば、非常になめらかになるので、
一次関数の近似として十分扱えるんじゃないでしょうか。
伝えたい情報は｛0 0 0 0 0 0 0 ..... 0｝とします。
そして、今まではどれだけズレても±1か0かどう動くかは等確率1/3でした。
今回は、確率が「復元力」を持つと仮定しましょう。
この仮定は、
「ズレが大きくなく情報にある程度の常識があり、そこから伝達を類推できる。」
という状況を以ていい近似になりうります。
そして、復元力、確率は各々の情報要素で独立に振る舞うとします。
（次に話したいものはこの復元力によって隣の情報要素と相互作用させようというもの）
その復元力をどうするかですが、単純にズレの距離に比例にしてしまうと、
負の確率がでてきてしまうので、少し改変します。
おいおい話しますが、流れを切らないために、式を先に示します。
ここで、dはどういう値かというと、いわゆる「バネの伸びの限界」で、
「xがdになると、P(-1)とP(1)の比がほぼ１０倍になる」としています。
つまりdが大きければ大きいほど、復元力は弱いということになります。
参考までに、d=1でのプロットを乗せておきます。青がP(-1),赤がP(+1)です。
これを用いて、Javaでシミュレーションしてみたいと思います。
この前のやつのr部分だけいじりたいと思います。
import java.util.*;
class InfoDest2 {
static double pneg (int x,double d){
return Math.exp(x/d)/3/Math.cosh(x/d);
}
static double ppos (int x,double d){
return Math.exp(-x/d)/3/Math.cosh(x/d);
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
int k = sc.nextInt(); //情報数(配列の長さ)
int n = sc.nextInt(); //試行回数
double d = sc.nextDouble(); //バネ限界伸び
while(data>0){ calc(k,n,d); data--;}
}
static void calc(int k,int n,double d) {
int[] a = new int[10];
//最初の値は全部0なのでこのままでいきます。
for(int i=0; i<n; i++){
for(int j=0; j<k; j++){
double rd = Math.random();
int r;
if(rd<=pneg(a[j],d)) r=-1;
else if(rd>=ppos(a[j],d)) r=1;
else r=0;
a[j] = a[j] + r;
}
}
double avr=0; double var=0;
for(int i=0; i<k; i++){
System.out.print(a[i]+", ");
avr += Math.abs(a[i]);
var += a[i]*a[i];
}
System.out.printf("誤り距離平均: %.2f, 誤り分散: %.2f %n",avr/k,Math.sqrt(var));
}
}
ことさら変わったところもないので、ちっちゃくしときます。
入力にバネ限界伸びが追加されました。
5 5 100 1 で出力してみる。
2, 1, 3, 2, 2, 誤り距離平均: 2.00, 誤り分散: 4.69
3, 3, 2, 0, 0, 誤り距離平均: 1.60, 誤り分散: 4.69
-1, 3, -1, 0, 0, 誤り距離平均: 1.00, 誤り分散: 3.32
0, 0, 2, -1, 1, 誤り距離平均: 0.80, 誤り分散: 2.45
2, 6, 3, 1, 0, 誤り距離平均: 2.40, 誤り分散: 7.07
ちなみに、復元力なしの場合（5 5 100)
10, 2, 0, 2, 7, 誤り距離平均: 4.20, 誤り分散: 12.53
-5, -6, -16, 20, 6, 誤り距離平均: 10.60, 誤り分散: 27.44
0, -5, -13, 8, 1, 誤り距離平均: 5.40, 誤り分散: 16.09
2, 11, 15, 2, 12, 誤り距離平均: 8.40, 誤り分散: 22.32
2, -8, -13, -1, 1, 誤り距離平均: 5.00, 誤り分散: 15.46
となり、明らかに情報が上手く伝わっていますね。
5 5 1000 1としてみると効果が歴然で、
1, 1, 0, -1, -2, 誤り距離平均: 1.00, 誤り分散: 2.65
-2, 3, 3, 1, -2, 誤り距離平均: 2.20, 誤り分散: 5.20
0, 1, -2, 0, 2, 誤り距離平均: 1.00, 誤り分散: 3.00
0, 0, 0, 0, 2, 誤り距離平均: 0.40, 誤り分散: 2.00
0, 3, 2, 8, 0, 誤り距離平均: 2.60, 誤り分散: 8.77
４つ目にいたってはほぼ正確に伝わってます。
-------------------------------------------
気になることとしては、バネ限界伸びにどのように依存するか、ですね。
そこで、1 10 100 d として、dを1～10まで出力してみます。
たしかにdが大きくなるほど、誤り距離平均は大きくなっています。
---------------------------------------------
最後に書き残していたP(-1)とP(+1)の求め方について説明しておきます。
まず、非負をとる関数で扱いが容易であるものとして
exp(kx)とexp(-kx)を考えます。
もちろん、
P(-1) ∝ exp(kx)
P(+1) ∝ exp(-kx)
となるだろうと思うわけですが、今回は確率を考えたいので、この両者の割合、
とします。ここでλは定数です。
λを決める。確率は1なのだから、
P(0) + P(+1) + P(-1) = 1
P(+1) + P(-1) = 2/3
で、計算すると、λ = 2/3となります。（まあそりゃそうだ）
最後に、ハイパボリックコサインの定義式：
を代入すれば、上の式に近い値が得られます。
最終的にkをバネ限界伸びdで表すのですが、これは簡単で、
P(+1)/P(-1) = exp(-2) ～ 0.1 として計算すればよいです。
なぜexp(-2)にするかですが、これは式が綺麗になるから以外に理由はないかな…。
ですがまあ大体10倍比であれば、ほぼそれ以上伸びないと思っていいだろう。
「指数関数でいいのか」と思うかもしれないですが、
dを大きくすれば、非常になめらかになるので、
一次関数の近似として十分扱えるんじゃないでしょうか。
2012年10月11日木曜日
情報の誤伝達４
結局確率過程はマルコフ過程の手前まで頑張りましたが、そこで停滞中です…。
そこで、今ある知識でちょっとでもがんばろうと思いまして、
まず情報列のうちのひとつだけに着目したいと思います。
情報各列は独立に伝達されると仮定するわけです。
もちろん『わたしは』とかの情報列は独立ではないので、仮定から外れます。
「n回伝達された際、そこの情報がxだけずれている確率(x ≧ 0 の整数)」
を考えたいと思います。
明らかに確率は原点で対称になるはずですからxは非負の整数にします。
x≧0ですから、-1より1の方がx回多く出たということです。
動く量が0である回数をn-k回数とする。
そうした場合、k回の中で、1が-1よりx回多く出ればよい。
-1の出る回数をmとおけば、1の出る回数はm+xであるから
m + m + x = k
これを解いて、 m = (k-x)/2 となる。
まず、mは整数でないといけないので、k ≡ x (mod 2)が条件。
そうして、1の出る回数はm+x = (k+x)/2であるから、
xずれる確率は、
となります。あとはほろほろと計算をすればいい。
簡単のため、伝達回数n = 5とします。
そうすると、xは0～5になるので、頑張って計算できそう…。
無論プログラミング組めよ！と思いますが、この記事ではペンを動かします。
P(0)=51/243 ～ 0.21
P(1)=45/243 ～ 0.19
P(2)=30/243 ～ 0.12
P(3)=15/243 ～ 0.06
P(4)=5 /243 ～ 0.02
P(5)=1 /243 ～ 0.0004
となりました。あら？ちゃんと減ってる・・・
実際は対称性があるので、グラフとしてはこうなります。
あら？綺麗なもんですね…
この確率分布の「距離」の期待値を考えると、
E ～ 1.44 となりました。なるほど、必ず間違えてしまうのか。
実際、この前のプログラミングでやってみます。
10 1 5で出力してみると、
-1, 2,1, -2, 1, -2, 0, 0, 1, 0, とデータが得られたので、
平均してみるとちょうど1になりますね、まあたしかに1.44ってのは妥当か
問題は、この前定義した「誤り平均」です。
それぞれが1.44でズレるはずなので、誤り平均もこれに相当したものになるはず。
それぞれが独立に振舞うので当たり前ですが・・・
10 5 5で出力してみます。
2, 1, 0, -4, 0, 誤り距離平均: 1.40, 誤り分散: 4.58
-1, 1, 2, 0, 1, 誤り距離平均: 1.00, 誤り分散: 2.65
2, 1, -1, 2, 2, 誤り距離平均: 1.60, 誤り分散: 3.74
-1, -1, -1, -1, 1, 誤り距離平均: 1.00, 誤り分散: 2.24
-1, 3, 2, -1, 3, 誤り距離平均: 2.00, 誤り分散: 4.90
-1, -3, -1, -2, -3, 誤り距離平均: 2.00, 誤り分散: 4.90
0, 1, 1, 2, 2, 誤り距離平均: 1.20, 誤り分散: 3.16
3, 2, -2, 1, 0, 誤り距離平均: 1.60, 誤り分散: 4.24
2, 0, -2, 1, -1, 誤り距離平均: 1.20, 誤り分散: 3.16
0, -1, 0, 2, -2, 誤り距離平均: 1.00, 誤り分散: 3.00
ほうほう、ということは擬似乱数はおかしくなかったということか…！
次の記事で、プログラミングで伝達回数に対する誤り平均のデータを集めて、
グラフ化してみたいと思います。
とりあえずのまとめとしては、
「期待値としては絶対に情報は隣半くらいまでズレる」ということです。
そこで、今ある知識でちょっとでもがんばろうと思いまして、
まず情報列のうちのひとつだけに着目したいと思います。
情報各列は独立に伝達されると仮定するわけです。
もちろん『わたしは』とかの情報列は独立ではないので、仮定から外れます。
「n回伝達された際、そこの情報がxだけずれている確率(x ≧ 0 の整数)」
を考えたいと思います。
明らかに確率は原点で対称になるはずですからxは非負の整数にします。
x≧0ですから、-1より1の方がx回多く出たということです。
動く量が0である回数をn-k回数とする。
そうした場合、k回の中で、1が-1よりx回多く出ればよい。
-1の出る回数をmとおけば、1の出る回数はm+xであるから
m + m + x = k
これを解いて、 m = (k-x)/2 となる。
まず、mは整数でないといけないので、k ≡ x (mod 2)が条件。
そうして、1の出る回数はm+x = (k+x)/2であるから、
xずれる確率は、
となります。あとはほろほろと計算をすればいい。
簡単のため、伝達回数n = 5とします。
そうすると、xは0～5になるので、頑張って計算できそう…。
無論プログラミング組めよ！と思いますが、この記事ではペンを動かします。
P(0)=51/243 ～ 0.21
P(1)=45/243 ～ 0.19
P(2)=30/243 ～ 0.12
P(3)=15/243 ～ 0.06
P(4)=5 /243 ～ 0.02
P(5)=1 /243 ～ 0.0004
となりました。あら？ちゃんと減ってる・・・
実際は対称性があるので、グラフとしてはこうなります。
あら？綺麗なもんですね…
この確率分布の「距離」の期待値を考えると、
E ～ 1.44 となりました。なるほど、必ず間違えてしまうのか。
実際、この前のプログラミングでやってみます。
10 1 5で出力してみると、
-1, 2,1, -2, 1, -2, 0, 0, 1, 0, とデータが得られたので、
平均してみるとちょうど1になりますね、まあたしかに1.44ってのは妥当か
問題は、この前定義した「誤り平均」です。
それぞれが1.44でズレるはずなので、誤り平均もこれに相当したものになるはず。
それぞれが独立に振舞うので当たり前ですが・・・
10 5 5で出力してみます。
2, 1, 0, -4, 0, 誤り距離平均: 1.40, 誤り分散: 4.58
-1, 1, 2, 0, 1, 誤り距離平均: 1.00, 誤り分散: 2.65
2, 1, -1, 2, 2, 誤り距離平均: 1.60, 誤り分散: 3.74
-1, -1, -1, -1, 1, 誤り距離平均: 1.00, 誤り分散: 2.24
-1, 3, 2, -1, 3, 誤り距離平均: 2.00, 誤り分散: 4.90
-1, -3, -1, -2, -3, 誤り距離平均: 2.00, 誤り分散: 4.90
0, 1, 1, 2, 2, 誤り距離平均: 1.20, 誤り分散: 3.16
3, 2, -2, 1, 0, 誤り距離平均: 1.60, 誤り分散: 4.24
2, 0, -2, 1, -1, 誤り距離平均: 1.20, 誤り分散: 3.16
0, -1, 0, 2, -2, 誤り距離平均: 1.00, 誤り分散: 3.00
ほうほう、ということは擬似乱数はおかしくなかったということか…！
次の記事で、プログラミングで伝達回数に対する誤り平均のデータを集めて、
グラフ化してみたいと思います。
とりあえずのまとめとしては、
「期待値としては絶対に情報は隣半くらいまでズレる」ということです。
2012年10月4日木曜日
情報の誤伝達2
import java.util.*;
class InfoDest {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int data = sc.nextInt();
int k = sc.nextInt(); //情報数(配列の長さ)
int n = sc.nextInt(); //試行回数
while(data>0){ calc(k,n); data--;}
}
static void calc(int k,int n) {
Random rand = new Random();
int[] a = new int[10];
//最初の値は全部0なのでこのままでいきます。
for(int i=0; i<n; i++){
for(int j=0; j<k; j++){
int r = rand.nextInt(3)-1;
a[j] = a[j] + r;
}
}
double avr=0; double var=0;
for(int i=0; i<k; i++){
System.out.print(a[i]+", ");
avr += Math.abs(a[i]);
var += a[i]*a[i];
}
System.out.printf("誤り距離平均: %.2f, 誤り分散: %.2f %n",avr/k,Math.sqrt(var));
}
}
入力としては、3つあって、
データ数 情報数（配列の長さ） 伝達回数 です。
試しに、
データ数を5, 情報数を5, 伝達回数を100とすると
5 5 100とすると、
23, 1, 0, 5, 14, 誤り距離平均: 8.60, 誤り分散: 27.40
7, 16, 5, 6, -8, 誤り距離平均: 8.40, 誤り分散: 20.74
-2, 12, 11, 6, 5, 誤り距離平均: 7.20, 誤り分散: 18.17
4, 7, 6, 3, -3, 誤り距離平均: 4.60, 誤り分散: 10.91
ということは、伝達回数が多くなれば、『上手い具合に』元に戻りそうな気がします。
実際は戻ってないですね。
5 5 1000をしてみます。
-45, -4, 27, 10, 38, 誤り距離平均: 24.80, 誤り分散: 65.68
14, 5, -4, 18, 14, 誤り距離平均: 11.00, 誤り分散: 27.51
-21, -16, 41, -4, 50, 誤り距離平均: 26.40, 誤り分散: 69.96
-7, 47, 43, -6, -5, 誤り距離平均: 21.60, 誤り分散: 64.56
25, -19, -14, 18, 0, 誤り距離平均: 15.20, 誤り分散: 38.81
むう、やはり戻らないな。
5 5 10000だと、
-18, -9, 51, -64, -84, 誤り距離平均: 45.20, 誤り分散: 118.99
42, 30, -59, 240, -126, 誤り距離平均: 99.40, 誤り分散: 282.17
24, -22, -5, 25, 22, 誤り距離平均: 19.60, 誤り分散: 46.84
-28, -27, 8, 104, -101, 誤り距離平均: 53.60, 誤り分散: 150.31
-29, 125, -38, 90, 112, 誤り距離平均: 78.80, 誤り分散: 196.35
情報の誤伝達1
情報はどれだけ間違えて伝わるかについて考えようみたいな。
あるk列の数列があるとする。（この際の数字は整数であればどんなものでも構わない)
たとえば、５列の数列であれば、
1 2 3 4 5でも、1200 20 54 -87 132でもよいとする。
仮定は、こういったものにしたい：
伝達の際、その数字列の±1もしくは0だけ不安定になる。
たとえば、50を伝える際に、49,50,51に揺らいでしまう。
それをすべての数字について彼は行い、そして伝達する。
最も簡単なものとして、1列の数字を与える。a0=10としよう。
次に伝わった情報をa1と置けば、
a1=9,10,11のどれかになる。そしてa2=8,9,10,11,12のいずれかになる。
結局、漸化式としては、
a(n) = a(n-1) + r
ただし、r = 0, -1 , +1 (各々の確率は1/3)とする。
どれだけ間違えたかについては、二種類の量がありますね。
と
nはn回伝達後の情報。
Vは考えている列の集合。要は最初の文字、次の文字…と足していく。
n(V)は集合Vの要素の個数。情報の長さです。
前者については、いわゆる平均です。
「それぞれについて、基準との”距離”を測り、その平均をみる」ということです。
後者については、いわゆる分散です。
「蓄積された情報の誤り具合」といえばいいかな。
で、これは多分確率過程の話なんだろうｗ
しかしまだ確率過程は勉強してませんので、javaさんに頼みます。
初期値、つまり、伝えたい情報は0 0 0 0 0 0 0......0にします。
すると評価も簡単になりますから。
というわけで、ここで一旦終わります。つまり、続きものです。
あるk列の数列があるとする。（この際の数字は整数であればどんなものでも構わない)
たとえば、５列の数列であれば、
1 2 3 4 5でも、1200 20 54 -87 132でもよいとする。
仮定は、こういったものにしたい：
伝達の際、その数字列の±1もしくは0だけ不安定になる。
たとえば、50を伝える際に、49,50,51に揺らいでしまう。
それをすべての数字について彼は行い、そして伝達する。
最も簡単なものとして、1列の数字を与える。a0=10としよう。
次に伝わった情報をa1と置けば、
a1=9,10,11のどれかになる。そしてa2=8,9,10,11,12のいずれかになる。
結局、漸化式としては、
a(n) = a(n-1) + r
ただし、r = 0, -1 , +1 (各々の確率は1/3)とする。
どれだけ間違えたかについては、二種類の量がありますね。
と
nはn回伝達後の情報。
Vは考えている列の集合。要は最初の文字、次の文字…と足していく。
n(V)は集合Vの要素の個数。情報の長さです。
前者については、いわゆる平均です。
「それぞれについて、基準との”距離”を測り、その平均をみる」ということです。
後者については、いわゆる分散です。
「蓄積された情報の誤り具合」といえばいいかな。
で、これは多分確率過程の話なんだろうｗ
しかしまだ確率過程は勉強してませんので、javaさんに頼みます。
初期値、つまり、伝えたい情報は0 0 0 0 0 0 0......0にします。
すると評価も簡単になりますから。
というわけで、ここで一旦終わります。つまり、続きものです。
登録:
投稿 (Atom)