HOME CHANGES INDEX

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
notes:soliton [2016/08/27] – gomidanotes:soliton [2022/11/17] (current) – removed gomida
Line 1: Line 1:
-====== 솔리톤 분포 ====== 
-===== Soliton Distribution ===== 
-<sq> 
-==== Ideal Soliton Distribution ==== 
-=== Definition === 
-| $\rho(1) = 1/k$ || 
-| $\rho(i)=1/i(i − 1),$ | $(i = 2,...,k)$ | 
-\\ 
-위 정의에 의해 $k\geq 1,\thinspace i\in\mathbb{N}$ 일 때, Probability Distribution의 ​조건 ​$\sum_i\rho(i)=1$ 을 만족한다. 따라서 별도의 normalization은 필요 없지만, 코드로 구현해보면 자료형의 정밀도 한계에 의해 누적합이 1의 근사치로 나타나기도 한다. 
-\\ 
-\\ 
-=== Graph === 
-<HTML><div style="max-width:552px;margin:0 auto;text-align:center;"></HTML> 
-{{:notes:soliton_distribution_k10.png?nolink}} 
-$$k = 10$$ 
-\\ 
-{{:notes:soliton_distribution.png?nolink}} 
-$$k = 10000$$ 
-<HTML></div></HTML> 
-\\ 
-=== Reference === 
-[[https://docs.switzernet.com/people/emin-gabrielyan/060708-thesis-ref/papers/Luby02.pdf|M. Luby "LT-codes," in Proc. 43rd Annu. IEEE Symp. Foundations of Computer Science (FOCS), Vancouver, BC, Canada, Nov. 2002, pp. 271–280.]] 
-</sq> 
-<sq> 
-==== Math Symbols ==== 
-| $P$ | $\rho$ | rho | 
-| $T$ | $\tau$ | tau | 
-| $M$ | $\mu$ | mu | 
-| $D$ | $\delta$ | delta | 
-</sq> 
-<sq> 
-==== Robust Soliton Distribution ==== 
-=== Definition === 
-| $\mu(i)=(\rho(i)+\tau(i)) / (\sum\rho(i)+\tau(i))$ | 
-Robust Soliton Distribution $\mu(i)$는 Ideal Soliton Distribution $\rho(i)$에 $\tau(i)$를 더하고 누적합이 1이 되도록 normalization을 수행한 것이다. 
-\\ 
-\\ 
-| $\tau(i)= 1/im,$ | $(i=1,2,\dots,m-1)$ | 
-| $\tau(i)= ln((k/m)/\delta)/m,$ | $(i=m)$ | 
-| $\tau(i)= 0,$ | $(i=m+1,\dots,k)$ | 
- 
-$\tau(i)$의 정의는 논문보다는 $k/R$을 m으로 표기하는 위키피디아의 표기방법이 더 직관적인 것으로 생각되어 이를 따랐다. 논문에서 정의하는 $R$은 상수 $c$와 $\delta$에 의해 그 값이 결정되는데, 최종적으로는 자연수 m으로 표현되기 때문이다. 
-\\ 
-\\ 
-=== Graph === 
-<HTML><div style="max-width:552px;margin:0 auto;text-align:center;"></HTML> 
-{{:notes:robust_soliton_distribution.png?nolink}} 
-$$k = 10000, c = 0.2, \delta = 0.05 ( S = 244, M = 41, Z = 1.31 )$$ 
-<HTML></div></HTML> 
-\\ 
-</sq> 
-<sq> 
-==== CDF ==== 
-[[notes/gofountain]]하다 보면 솔리톤분포 생성함수를 CDF(Cumulative Distribution Function, 누적분포함수)라고 지칭하고 있는데 PDF와의 차이점을 공부하다가 정리해본다. 우선 용어에서 혼란이 있었는데 정리하자면 하기와 같다. 
-| Probability Distribution Function | Probability Mass Function | Discrete variable | 
-| ::: | Probability Density Function | Continuous variable | 
-| ::: | Cumulative Distribution Function | PMF의 누적합 또는 PDF의 적분 | 
- 
-먼저 CDF의 정의를 찾아보자. A real-valued random variable X 대한 함수의 정의는, 
-$$F(x) = P(X\leq x)$$ 
-이 때, P는 임의의 실수 X가 x보다 작거나 같을 확률이다. 
-Continuous random variables 에서는 PDF(Probability Density Function)에 대한 적분이고, 
-$$F(x)=\int_{-\infty}^x f(t)dt$$ 
-Discrete random variables 에서는 PMF(Probability Mass Function)에 대한 누적합이다. 
-$$F(x)=\sum\limits_{t \leq x} f(t)$$ 
-</sq> 
-<sq> 
-==== Go implementation ==== 
-=== Ideal Soliton Distribution === 
-Reference 
-  * https://github.com/google/gofountain/blob/master/util.go#L34 
- 
-하기 CDF는 [[notes/gofountain|gofountain]]에서 발췌하였다. 한 개의 파라메터 n 을 가지는데, 관련 논문에서는 통상 소스심볼의 수 k로 표기하며 여기서는 위키피디아의 표기 N을 참조한 것으로 생각된다. 이 값은 최대 degree로도 해석할 수 있으며, 따라서 소스심볼의 수 k를 넘을 수 없다. 
-<code go> 
-package main 
- 
-import(  
- "fmt" 
-) 
- 
-func SolitonDistribution(n int) []float64 { 
- cdf := make([]float64, n+1) 
- cdf[1] = 1 / float64(n) 
- for i := 2; i < len(cdf); i++ { 
- cdf[i] = cdf[i-1] + (1 / (float64(i) * float64(i-1))) 
- } 
- return cdf 
-} 
- 
-func main() { 
- for i:=1;i<20;i++{ 
- fmt.Println(SolitonDistribution(i)) 
- } 
-} 
-</code> 
-<code> 
-MacBook-Pro-Retina:gofountain-LT-experiment gomida$ go run soliton.go  
-[0 1] 
-[0 0.5 1] 
-[0 0.3333333333333333 0.8333333333333333 0.9999999999999999] 
-[0 0.25 0.75 0.9166666666666666 1] 
-[0 0.2 0.7 0.8666666666666666 0.95 1] 
-[0 0.16666666666666666 0.6666666666666666 0.8333333333333333 0.9166666666666666 0.9666666666666667 1] 
-[0 0.14285714285714285 0.6428571428571428 0.8095238095238094 0.8928571428571428 0.9428571428571428 0.9761904761904762 1] 
-[0 0.125 0.625 0.7916666666666666 0.875 0.925 0.9583333333333334 0.9821428571428572 1] 
-[0 0.1111111111111111 0.6111111111111112 0.7777777777777778 0.8611111111111112 0.9111111111111112 0.9444444444444445 0.9682539682539684 0.9861111111111113 1.0000000000000002] 
-[0 0.1 0.6 0.7666666666666666 0.85 0.9 0.9333333333333333 0.9571428571428572 0.9750000000000001 0.9888888888888889 1] 
-[0 0.09090909090909091 0.5909090909090909 0.7575757575757576 0.8409090909090909 0.890909090909091 0.9242424242424243 0.9480519480519481 0.965909090909091 0.9797979797979799 0.990909090909091 1] 
-[0 0.08333333333333333 0.5833333333333334 0.75 0.8333333333333334 0.8833333333333334 0.9166666666666667 0.9404761904761906 0.9583333333333335 0.9722222222222223 0.9833333333333334 0.9924242424242424 1] 
-[0 0.07692307692307693 0.5769230769230769 0.7435897435897435 0.8269230769230769 0.8769230769230769 0.9102564102564102 0.9340659340659341 0.951923076923077 0.9658119658119658 0.9769230769230769 0.9860139860139859 0.9935897435897435 0.9999999999999999] 
-[0 0.07142857142857142 0.5714285714285714 0.738095238095238 0.8214285714285714 0.8714285714285714 0.9047619047619048 0.9285714285714286 0.9464285714285715 0.9603174603174603 0.9714285714285714 0.9805194805194805 0.988095238095238 0.9945054945054944 0.9999999999999999] 
-[0 0.06666666666666667 0.5666666666666667 0.7333333333333333 0.8166666666666667 0.8666666666666667 0.9 0.9238095238095239 0.9416666666666668 0.9555555555555556 0.9666666666666667 0.9757575757575757 0.9833333333333333 0.9897435897435897 0.9952380952380951 0.9999999999999999] 
-[0 0.0625 0.5625 0.7291666666666666 0.8125 0.8625 0.8958333333333334 0.9196428571428572 0.9375000000000001 0.951388888888889 0.9625 0.9715909090909091 0.9791666666666666 0.985576923076923 0.9910714285714285 0.9958333333333332 0.9999999999999999] 
-[0 0.058823529411764705 0.5588235294117647 0.7254901960784313 0.8088235294117647 0.8588235294117648 0.8921568627450981 0.9159663865546219 0.9338235294117648 0.9477124183006537 0.9588235294117647 0.9679144385026738 0.9754901960784313 0.9819004524886877 0.9873949579831932 0.992156862745098 0.9963235294117646 0.9999999999999999] 
-[0 0.05555555555555555 0.5555555555555556 0.7222222222222222 0.8055555555555556 0.8555555555555556 0.888888888888889 0.9126984126984128 0.9305555555555557 0.9444444444444445 0.9555555555555556 0.9646464646464646 0.9722222222222222 0.9786324786324786 0.9841269841269841 0.9888888888888888 0.9930555555555555 0.9967320261437908 0.9999999999999999] 
-[0 0.05263157894736842 0.5526315789473684 0.719298245614035 0.8026315789473684 0.8526315789473684 0.8859649122807017 0.9097744360902256 0.9276315789473685 0.9415204678362573 0.9526315789473684 0.9617224880382774 0.969298245614035 0.9757085020242914 0.9812030075187969 0.9859649122807016 0.9901315789473683 0.9938080495356035 0.9970760233918127 0.9999999999999998] 
-MacBook-Pro-Retina:gofountain-LT-experiment gomida$ 
-</code> 
-각 라인의 마지막 값을 살펴보면 누적 합이 1이 아닌 경우들을 관찰 할 수 있다. 이는 분수를 float 자료형으로 풀어 계산 후 합산했기 때문으로 수학적으로는 1이 되어야 한다. 
-</sq> 
-<sq> 
-==== Go implementation ==== 
-=== Robust Soliton Distribution === 
-Reference 
-  * https://github.com/google/gofountain/blob/master/util.go#L54 
-하기 CDF 역시 gofountain에서 발췌하였다. 세 개의 파라메터 n, m, delta를 가지는데, 원본 논문의 수식에 대입하면 각각 $k, k/R, \delta$에 해당한다. 
-<code go> 
-package main 
- 
-import(  
- "fmt" 
- "math" 
-) 
- 
-func robustSolitonDistribution(n int, m int, delta float64) []float64 { 
- pdf := make([]float64, n+1) 
- 
- pdf[1] = 1/float64(n) + 1/float64(m) 
- total := pdf[1] 
- for i := 2; i < len(pdf); i++ { 
- pdf[i] = (1 / (float64(i) * float64(i-1))) 
- if i < m { 
- pdf[i] = 1 / (float64(i) * float64(m)) 
- } 
- if i == m { 
- pdf[i] += math.Log(float64(n)/(float64(m)*delta)) / float64(m) 
- } 
- total += pdf[i] 
- } 
- 
- cdf := make([]float64, n+1) 
- for i := 1; i < len(pdf); i++ { 
- pdf[i] /= total 
- cdf[i] = cdf[i-1] + pdf[i] 
- } 
- return cdf 
-} 
- 
-func main() { 
- for i:=1;i<20;i++{ 
- fmt.Println(robustSolitonDistribution(10, i, 0.01)) 
- } 
-} 
-</code> 
-<code> 
-[0 0.55 0.8 0.8833333333333334 0.925 0.9500000000000001 0.9666666666666668 0.9785714285714286 0.9875 0.9944444444444445 1] 
-[0 0.1302280017970026 0.9131813321353315 0.9493557770789434 0.9674429995507493 0.9782953330338329 0.9855302220225552 0.9906979998716426 0.9945738332584582 0.9975883703370925 0.9999999999999999] 
-[0 0.14757394691281517 0.20433315726389792 0.9205371055084842 0.9489167106840256 0.9659444737893504 0.977296315859567 0.9854047744811503 0.9914861184473377 0.9962160526432613 1.0000000000000002] 
-[0 0.16113943843239625 0.21868923787253777 0.2570557708326321 0.9309402406718303 0.953960160447887 0.9693067736319247 0.9802686401919517 0.988490040111972 0.9948844622719877 1.0000000000000002] 
-[0 0.1737790432159883 0.23170539095465106 0.27032295611375956 0.29928612998309095 0.9420736522613373 0.9613824348408916 0.975174422397716 0.9855184130653344 0.9935637391401486 1] 
-[0 0.18606102561920923 0.2442050961252121 0.2829678097958807 0.31203984504888216 0.33529747325128334 0.9534847435951979 0.9700973351683415 0.9825567788481993 0.9922474572658664 1] 
-[0 0.198169570702819 0.2564547385565893 0.2953115171257695 0.3244541010526546 0.34776816819416273 0.36719655747875285 0.965028899287738 0.9796001912511806 0.9909334183338582 1.0000000000000002] 
-[0 0.21018147011690527 0.26856521181604565 0.30748770628213923 0.33667957713170943 0.36003307381136557 0.37949432104441233 0.3961753901013096 0.976646503320344 0.9896206681423751 1] 
-[0 0.22213420396002018 0.2805905734231834 0.3195614863986255 0.34878967113020715 0.3721722189154724 0.39165767540319346 0.4083594952498115 0.42297358761560233 0.9883087261073674 1] 
-[0 0.23404816770391026 0.2925602096298878 0.33156823758053955 0.36082425854352834 0.38422907531391937 0.40373308928924523 0.42045081555381025 0.4350788260353046 0.4480815020188552 1] 
-[0 0.5212252536196198 0.645326504481434 0.7280606717226435 0.7901112971535507 0.8397517974982763 0.881118881118881 0.9165763813651137 0.9476016940805673 0.9751797498276371 1] 
-[0 0.5328207592503604 0.6539163863527151 0.7346468044209515 0.7951946179721289 0.8436328688130708 0.883998077847189 0.9185968284478617 0.9488707352234503 0.9757808745795291 1] 
-[0 0.5438678802664915 0.6621000281505114 0.7409214600731913 0.8000375340152012 0.8473303931688091 0.886741109130149 0.9205217228112975 0.9500797597823025 0.9763535704231958 0.9999999999999998] 
-[0 0.5544046200385004 0.6699055825465213 0.7469062242185353 0.8046567054725458 0.8508570904757541 0.889357411311761 0.9223576863140528 0.951232926941058 0.976899807498396 1.0000000000000002] 
-[0 0.5644655496819281 0.6773586596183137 0.7526207329092374 0.8090672878774302 0.8542245318519844 0.8918555684974463 0.9241107427649851 0.9523340202490814 0.9774213780127227 0.9999999999999998] 
-[0 0.5740821869797599 0.6844826075527907 0.7580828879348112 0.8132830982213265 0.8574432664505388 0.894243406641549 0.9257863839481292 0.9533864890913869 0.9779199158853937 0.9999999999999999] 
-[0 0.5832833261894558 0.6912987569652809 0.7633090441491643 0.8173167595370769 0.860522931847407 0.8965280754393488 0.9273896270895845 0.9543934847835408 0.9783969138448353 1.0000000000000002] 
-[0 0.592095326004867 0.6978266342200219 0.7683141730301251 0.8211798271377024 0.8634723504237644 0.8987161198288159 0.9289250650331459 0.9553578920869346 0.978853738356969 1] 
-[0 0.6005423617388447 0.704084148245542 0.7731120059166736 0.8248828991700223 0.8662996137727013 0.9008135426082671 0.9303969101816092 0.9562823568082836 0.9792916426986608 1.0000000000000002] 
-</code> 
-</sq> 
-<sq> 
-==== Python implementation ==== 
-=== Soliton Distribution === 
-Reference 
-  * http://stats.stackexchange.com/questions/37581/how-do-i-generate-numbers-according-to-a-soliton-distribution/37583#37583 
-<code python> 
-from __future__ import print_function, division 
-import random 
-from math import ceil 
- 
-def soliton(N, seed): 
-  prng = random.Random() 
-  prng.seed(seed) 
-  while 1: 
-    x = random.random() # Uniform values in [0, 1) 
-    i = int(ceil(1/x))       # Modified soliton distribution 
-    yield i if i <= N else 1 # Correct extreme values to 1 
- 
-if __name__ == '__main__': 
-  N = 10 
-  T = 10 ** 5 # Number of trials 
-  s = soliton(N, random.randint(0, 2 ** 32 - 1)) 
-  f = [0]*N 
-  for j in range(T): 
-    i = next(s) 
-    f[i-1] += 1 
- 
-  print("k\tFreq.\tExpected Prob\tObserved Prob\n"); 
- 
-  print("{:d}\t{:d}\t{:f}\t{:f}".format(1, f[0], 1/N, f[0]/T)) 
-  for k in range(2, N+1): 
-    print("{:d}\t{:d}\t{:f}\t{:f}".format(k, f[k-1], 1/(k*(k-1)), f[k-1]/T)) 
-</code> 
- 
-<code> 
-MacBook-Pro-Retina:work gomida$ python soliton.py  
-k Freq. Expected Prob Observed Prob 
- 
-1 10148 0.100000 0.101480 
-2 49794 0.500000 0.497940 
-3 16661 0.166667 0.166610 
-4 8335 0.083333 0.083350 
-5 5031 0.050000 0.050310 
-6 3306 0.033333 0.033060 
-7 2469 0.023810 0.024690 
-8 1771 0.017857 0.017710 
-9 1419 0.013889 0.014190 
-10 1066 0.011111 0.010660 
-MacBook-Pro-Retina:work gomida$  
-</code> 
-</sq> 
  
TypeError: Cannot access offset of type string on string

TypeError: Cannot access offset of type string on string

An unforeseen error has occured. This is most likely a bug somewhere.

More info has been written to the DokuWiki error log.