Average Number

Weighted Average

兩數,依照比例(權重),各取一部分,加總,得到「加權平均值」。

加權平均值介於兩數之間。調整權重,可以得到兩數之間的每一種數字。

x = w x₁ + (1-w) x₂   (0 ≤ w ≤ 1)

推廣到多數。加權平均值介於最大值和最小值之間。

x = w₁x₁ + w₂x₂ + ... + wₙxₙ   (w₁ + ... + wₙ = 1)

推廣到高維度。加權平均值介於凸包之間。

[x]      [x₁]      [x₂]            [xₙ]
[y] = w₁ [y₁] + w₂ [y₂] + ... + wₙ [yₙ]   (w₁ + ... + wₙ = 1)
[z]      [z₁]      [z₂]            [zₙ]

其實只是每個維度分開處理
x = w₁ x₁ + w₂ x₂ + ... + wₙ xₙ
y = w₁ y₁ + w₂ y₂ + ... + wₙ yₙ
z = w₁ z₁ + w₂ z₂ + ... + wₙ zₙ

權重推廣成任意數。每個權重另外除以權重總和。

     (w₁)       (w₂)         (w₃)
      a          b            c        ax₁ + bx₂ + cx₃
x = ————— x₁ + —————  x₂ +  ————— x₃ = ———————————————
    a+b+c      a+b+c        a+b+c         a + b + c   
          a₁                       aₙ
x = ————————————— x₁ + ... + ————————————— xₙ
    a₁ + ... + aₙ            a₁ + ... + aₙ

    a₁ x₁ + ... + aₙ xₙ
  = ———————————————————
       a₁ + ... + aₙ   

數字推廣成任意事物。加權平均值無所不在。

主角    加權平均值
--------  ----------
質點    重心
溶液    混和濃度
機率    期望值
座標點   凸包範圍
函數點   線性內插
線性代數  線性組合
三原色   人類眼中的彩色

加權平均值的精髓:多數化作一數。

Floating Number

Random Variable與Distribution

現實世界的數值,通常是浮動數值,不是精準數值。數值具有多種可能性,有時高一點,有時低一點。

工程師活用了區間的概念,描述浮動數值。例如食品包裝經常見到的500±20,表示數值可能是區間[480,520]的其中一個。

工程師命名為「誤差範圍」。好用,但是太過陽春。

數學家活用了比例、函數兩個概念,描述浮動數值。我們可以自由控制要出現那些數值,個別的數值(離散)、一段範圍的數值(連續)。我們甚至可以個別調整每一種數值的出現程度高低。

數學家命名為「隨機變數」。這個名稱經常造成誤解,事實上這根本不隨機。理想的名稱應是「浮動數字」。

兩個隨機變數可以加減乘除,但是計算過程非常複雜:試誤法,針對一個答案,窮舉各種得到此答案的方式,累加機率。

     add: X+Y  (convolution)
subtract: X-Y  (convolution)
multiply: XY   (Dirichlet convolution)
  divide: X/Y

數學家定義了一些簡易指標,可以迅速獲知隨機變數的重點。

一個隨機變數的
平均值 mean        : E[X]
均方值 mean square : E[X^2]
變異數 variance    : E[(X-E[X])^2]

兩個隨機變數的
共相關數   correlation             : E[XY]
共變異數   covariance              : E[(X-E[X])(Y-E[Y])]
共相關係數 correlation coefficient : CoVar[X,Y] / sqrt(Var[X]) / sqrt(Var[Y])

由於隨機變數的四則運算非常複雜,數學家鮮少討論隨機變數的四則運算,轉而討論隨機變數的指標的四則運算。出乎意料地優雅。

E[X+Y] = E[X] + E[Y]
E[X⋅Y] = E[X] ⋅ E[Y]   if X and Y are independnet
E[X+k] = E[X] + k
E[X⋅k] = E[X] ⋅ k
Var[X+Y] = Var[X] + Var[Y] + CoVar[X,Y]
Var[X-Y] = Var[X] + Var[Y] - CoVar[X,Y]
CoVar[X,Y] = 0   if X and Y are independnet
Var[X+k] = Var[X]
Var[X⋅k] = Var[X] ⋅ k²

至於「每一種數值的出現程度高低」的函數,數學家命名為「分布」。數學家創造了許多經典的分布,數學性質極強。例如兩個常態分布隨機變數,相加減還是常態分布。相乘除就不是。

uniform distribution
Gaussian distribution (normal distribution)
binomial distribution
Poisson distribution

大學的機率課程已經談過這些東西,此處只做重點歸納。

Mixture Distribution(Mixture Model)

數個隨機變數,浮動出現其中一個隨機變數。兩層隨機變數。

其實就是數個分布函數的加權平均值,因而稱作「混合分布」。想一想為什麼。

混合分布是計算學家的最愛。用幾個經典的分布,調整平均數、變異數,以及權重,組合出具有曼妙曲線的分布。

經典的混合分布,像是數個常態分布的加權平均值,稱做「高斯混合模型Gaussian Mixture Model」。

Weighted Average of Random Variables

真實世界當中,數字通常不精準,數字通常有誤差。引入機率分布,讓每個數字擁有浮動範圍,是個不錯的辦法。例如讓每個數字套用常態分布。

浮動數字的加權平均值,我不清楚是否有人研究。如果只有兩個數字,而且權重都是0.5,加權平均值就是摺積。值得一提的是,兩個常態分布的摺積仍是常態分布,平均數、變異數很好推算:

http://www.tina-vision.net/docs/memos/2003-003.pdf

Random Number

Random Number

「隨機數」、「亂數」。我們習慣一口氣取大量隨機數。

1694 19262 3252 4541 20 28590 6191 814 30047 9007 29380 1639 23559

什麼樣子叫做Random呢?目前沒有定論!

大家習慣把Random解讀為「沒有規律」、「不可預測」、「亂」,但是沒有人能明確描述詳細內容。

大致能想到的有:

一、數字的分布:每個數字都可能出現。
二、數字的排版:數字沒有特殊造型。
三、數字的擾動:數字歪了,多了點、少了點。
四、次序的更動:下個數字不知道是哪一個。

相關的數學概念有:

一、Inversion 逆序對
二、Entropy 熵
三、Discrepancy
四、Normal Number 正規數
五、Point Process 點程序

Pseudorandom Number

計算機只能接受明確指令,人類只好使用明確數學公式、明確演算法來製造隨機數。隨機數具有規律、可以預測,於是早期文獻稱做「偽隨機數」、「偽亂數」。

儘管隨機數具有規律、可以預測,我們還是可以努力讓隨機數「看起來似乎很亂」,讓人一時無法預測。但由於缺乏「亂」的明確定義,所以無法精準評比優劣。一切都是靠感覺,很不科學。

C的內建函式庫,提供了隨機數。可惜不是均勻分布uniform distribution,時常為人詬病。

C++的內建函式庫,提供了健全的隨機數。

演算法(Linear Congruential Generator)

先備知識是「餘數」。

以數學式子xnext = (((x ⋅ a) + b) % n);不斷製造隨機數。

當n是質數,則0到n-1恰好各出現一次,呈均勻分布。不過當n不是質數,就很難說了,必須小心設定a b n才行。

缺點:每n個數字循環出現,可以預測。實務上會讓n很大,以避開缺點。

C語言的rand()即是此演算法。

演算法(Xorshift)

先備知識是「有限域」。

餘數系統,將整數推廣成餘數多項式。二進位數字視作餘數多項式,餘數多項式加法、乘法化作xor、shift。細節請自行查詢。

演算法(Mersenne Twister)

我沒有研究。細節請自行查詢。

2D Random Number

二維隨機數,更加講究排版,衍生許多演算法。

       regular:排列整齊。缺點是太過整齊,具有明顯紋路。
       uniform:均勻分布。缺點是不夠整齊,偶有空白小格。
      jittered:regular + uniform,每小格任取一點。
                宏觀整齊適中,微觀仍不夠整齊,常常靠太近。
        n-rook:n個城堡不互相攻擊。奇爛無比。
multi-jittered:每小格實施n-rook。稍微改善小處不夠整齊的問題。
  Poisson disk:每一點到其他點的最短距離為定值d。整齊。慢。
best candidate:每一點到先前點的最短距離盡量長。不太整齊。快。
    Hammersley:(i, i的二進位鏡射)。整齊適中。超快!
        Halton:(i的a進位鏡射, i的b進位鏡射),a與b互質。超快!
         Sobol:我沒有研究。

演算法(Poisson Disk Sampling)

每回合在圓形聯集的邊界上隨機生一點。自訂圓半徑。

演算法(Best Candidate Sampling)

每回合隨機生k個候選點,留下最遠的那一點。

演算法(Hammersley Sequence)

(i, i的二進位鏡射)。

i | i₍₂₎ |Φ(i)₍₂₎| Φ(i)
--|------|-------|------
1 |    1 | .1    | .5
2 |   10 | .01   | .25
3 |   11 | .11   | .75
4 |  100 | .001  | .125
5 |  101 | .101  | .635
6 |  110 | .011  | .325
7 |  111 | .111  | .875
8 | 1000 | .0001 | .0625

Φ(i): radical inverse of integer i

演算法(Halton Sequence)

(i的a進位鏡射, i的b進位鏡射),a與b互質。

演算法(Sobol Sequence)

http://web.maths.unsw.edu.au/~fkuo/sobol/joe-kuo-notes.pdf

演算法(Recursive Wang Tile)

整數隨機數調整範圍

一種隨機數,放大、位移,調整範圍。

random(0, 2) + 3 = random(3, 5)
random(0, 2) - 3 = random(-3, -1)
random(0, 2) × 3 = random(0, 6)

多種隨機數,分別做為每個位數,仍是均勻分布!需要調整成十進位,很麻煩。

random(0, 2) * 10 + random(0, 9) ---> random(0, 29)

浮點數隨機數調整範圍

一種隨機數,縮放、位移,調整範圍。

uniform(0, 2) + 3 = uniform(3, 5)
uniform(0, 2) - 3 = uniform(-3, -1)
uniform(0, 2) × 3 = uniform(0, 6)
uniform(0, 2) ÷ 3 = uniform(0, 2/3)

多種隨機數,相加、相乘,不再是均勻分布!別亂用。

uniform(0, 2) + uniform(0, 3) ≠ uniform(0, 5)
uniform(0, 2) × uniform(0, 3) ≠ uniform(0, 6)

一維隨機數,位於線段。可以變成圓形、半圓形。

二維隨機數,位於正方形。可以變成矩形、三角形、四邊形、多邊形、圓盤、球面、半球面。

Graphics3D[{PointSize[Large], Point[RandomPoint[Ball[], 200]]}, Boxed->False] Graphics3D[{PointSize[Large], Point[SpherePoints[200]]}, Boxed->False] u1 := RandomReal[{0,1}]; u2 := RandomReal[{0,1}]; f[{u1_, u2_}] := {Sqrt[u1]*Cos[2*Pi*u2], Sqrt[u1]*Sin[2*Pi*u2], Sqrt[1-u1]}; pts = f /@ Table[{u1, u2}, {200}]; Graphics3D[{PointSize[Large], Point /@ pts}, Boxed->False]

變換時必須注意面積變化、密度變化,以確保均勻。例如正方形變圓盤:長變成幅角、寬變成半徑平方。若忘了開根號,則內密外疏。

順帶一提,後面章節Sampling的演算法,似乎也都可以用於調整形狀。不過我還沒想清楚。

Sampling

Sampling

「取樣」。創造大量數字,符合給定分布。

使用均勻分布的隨機數,製作其他分布的隨機數。

UVa 12109

演算法(Inversion Sampling)

均勻分布的隨機數,代入「分布的積分的倒函數」,就得到該分布的隨機數。

若隨機數起初不是均勻分布,則先變成均勻分布,再變成目標分布。應該用不上。

演算法(Rejection Sampling)

二維隨機數(x,p),在分布曲線下就保留,在分布曲線上就捨棄,x即為所求。相當直覺的方法。

缺點:一、很多隨機數沒有用處,白算了。二、下一個輸出,延遲時間不穩定。有時一下就得到,有時一直得不到。

減少空白處,增加使用率。想辦法建立一個上界函數upper(x),略大於等於分布,做為p的上界。

每個位置x的上界都不同,導致p有密有疏、有多有少;為了讓p均勻等量,x必須符合上界函數的分布。(上界函數除以曲線下方面積,面積調成1,就變成了分布。)

然而上界函數往往難想。這招往往難用。

演算法(Metropolis-Hasting Sampling)

原理源自Markov Chain:

https://zhuanlan.zhihu.com/p/21112618

http://www.jianshu.com/p/27829d842fbc

直接講結論:隨機挑起點,隨機挑下一步。以分布高低比例,決定去或留。需要多少隨機數,就做多少回合。

步伐大小:可以採用任意分布,但是必須左右對稱。

去留判斷:一、下一步分布更高時:既然此處已取樣,分布更高的地方,也應該取樣,以符合分布高低。二、下一步分布更小時:依照比例高低來取樣,抽中原處的機會較高,抽中下一步的機會較低。

此演算法改善了先前缺點。遺珠之憾是隨機數有地緣關係。

演算法(Gibbs Sampling)

推廣到高維度。每次只沿一個維度走或停,每個維度隨機輪流一遍,再重新隨機輪流一遍,不斷下去。

演算法(Box-Muller Transform)

均勻分布變常態分布。因為常態分布的數學式子太長、計算時間太久,所以發明了快而不準的演算法。欲速則不達。

演算法(Central Limit Thorem)

任意分布變常態分布。中央極限定理:任意一個分布,取樣取多了,樣本們的平均值是一個浮動數字,呈現常態分布。

速度更快,準度更低。

Hash Function

Hash Function

「雜湊函數」。輸入輸出都是數字的函數,但是有著形形色色的變種:限寬、均勻、保距、量化、混亂、單向、編碼。大家視情況需要,混用多個變種。

各種變種仍在發展中,以下只簡介。

1. hash function

限寬。限制輸出範圍。簡易方式是mod運算。

用途是縮減數字範圍。

2. uniform hash function

均勻。輸出數字使用機率均等。簡易方式是mod最大公因數。

用途是均勻分散儲存。知名應用是hash table。

3. isometric mapping / locality-sensitive hashing

保距。所有數對,變換前的差異,大致等於變換後的差異。簡易方式是線性變換。

同樣道理,還可以發明保長、保角、保秩、保序等變種。

用途是以雜湊值估計相似度。

4. quantization / projection

量化。刪除數字的細節,降低精確度。簡易方式是floor運算。

用途是簡化數字。知名演算法是PCA、KNN。

5. random hash function

混亂。輸出是固定的隨機數。簡易方式是以輸入數字生成隨機數、隨機排列。

6. cryptographic hash function

單向。難以從輸出推算輸入。簡易方式是餘數連乘、三角函數。

用途是密碼、摘要、簽章,讓外人難以偽造變換前的原始資料。知名演算法如SHA、MD5。

請見本站文件「Encryption」。

7. coding

編碼。輸入不是數字,而是其他元件,例如字串。簡易方式是先化作多項式、再化作數字。

用途是建立索引表,知名演算法如murmur。

請見本站文件「String」。