Question

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[XY] = 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^2

至于“每一种数值的出现程度高低”的函数，数学家命名为“分布”。数学家创造了许多经典的分布，数学性质极强。例如两个常态分布随机变数，相加减还是常态分布。相乘除就不是。

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

人类倾向考虑两个面向：无法预测（齐乱）、均匀分布（聚散）。前者令乱数无秩序，后者令乱数有秩序──乍听矛盾，却可并行不悖，此即成语“乱中有序”，好比混沌与碎形。

Pseudorandom Number

“伪随机数”、“伪乱数”。缺少了齐乱的要素。

计算机只能接受明确指令，人类只好使用明确数学公式、明确演算法来制造乱数。具备规律、可以预测，于是称做“伪乱数”。

C 的内建函式库，提供了伪乱数。可惜不是均匀分布 uniform distribution，时常为人诟病。

2D Random Number

2D Random Number

二维的情况下，更加讲究齐乱、聚散，衍生许多种演算法。因为缺乏“看起来似乎很乱”的数学概念，所以无法精准评比优劣。一切都是靠感觉。

       regular：排列整齐。缺点是太过整齐，具有明显纹路。
       uniform：均匀分布。缺点是不够整齐，偶有空白小格。
      jittered：regular + uniform，每小格任取一点。
                宏观整齐适中，微观仍不够整齐，常常靠太近。
        n-rook：n 个城堡不互相攻击。奇烂无比。
multi-jittered：每小格实施 n-rook。稍微改善小处不够整齐的问题。
  Poisson disk：每一点到其他点的最短距离为定值 d。整齐适中。极慢。
best candidate：每回合，随机取 k 点，挑出“与当前所有点的最短距离”最大的那一点。
                比 Poisson disk 略差，但是可以轻鬆增减取样点。稍慢。
    Hammersley：(i, i 的二进位镜射)。整齐适中。超快！
        Halton：(i 的 a 进位镜射, i 的 b 进位镜射)，a 与 b 互质。
                比 Hammersley 略差，但是可以轻鬆增减取样点。超快。
         Sobol：我没有研究。

二维的情况下，浮现了一个新要素：地序。地缘相近的数字，不准连续出现。然而目前的演算法，多半未考虑生成过程的地序，只考虑生成结果的齐乱与聚散。

演算法（Poisson Disk Sampling）

http://bl.ocks.org/mbostock/dbb02448b0f93e4c82c3

在圆形们的边界上随机取点。

演算法（Best Candidate Sampling）

http://bl.ocks.org/mbostock/6224050

演算法（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）

演算法（Sobol Sequence）

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

演算法（Recursive Wang Tile）

Shape Mapping【尚无专有名词】

二维乱数，即是正方形乱数。可以进一步变成其他形状，诸如矩形、三角形、圆盘、球面、半球面。

转换时必须注意面积变化。面积变化，导致密度变化，导致乱数不均匀。

举例来说，正方形变圆形，长变成幅角、宽变成半径平方。错误的方式是宽变半径，导致乱数不均匀，中央密、外围疏。

http://mathworld.wolfram.com/DiskPointPicking.html

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. pseudorandom hash function

混乱。输出数字是固定的随机数字。简易方式是以输入数字生成乱数、随机排列。

6. cryptographic hash function

单向。难以从输出推算输入。简易方式是馀数连乘、三角函数。

用途是密码、摘要、签章，让外人难以伪造变换前的原始资料。知名演算法如 SHA、MD5。

请参考本站文件“ Encryption ”。

7. coding

编码。输入不是数字，而是其他元件，例如字串。简易方式是多项式。

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

请参考本站文件“ String ”。