鸡兔同笼问题的程序解法

定义

“鸡兔同笼问题”是我国古算书《孙子算经》中著名的数学问题,其内容是:

今有雉(鸡)兔同笼,上有三十五头,下有九十四足。问雉兔各几何。

数学描述

设鸡有 x 只,兔有 y 只,则:

1
2
x + y = 35
2x + 4y = 94

解这个方程组得 x = 23, y = 12

用矩阵表示:

1
2
[1, 1]  *  [x]  =  [35]
[2, 4] [y] [94]

Python 代码

1
2
3
4
5
6
>>> import numpy as np
>>> a = np.mat([[1, 1], [2, 4]])
>>> b = np.mat([[35], [94]])
>>> a.I * b
matrix([[23.],
[12.]])

再来一题三元版本:

有蜘蛛,蜻蜓,蝉三种动物共 18 只,共有腿 118 条,翅膀 20 对,三种动物各几只?

蜘蛛 8 条腿;蜻蜓 6 条腿, 2 对翅膀;蝉 6 条腿,1 对翅膀。

1
2
3
[1, 1, 1]     [x]     [18]
[8, 6, 6] * [y] = [118]
[0, 2, 1] [z] [20]

代码:

1
2
3
4
5
6
7
>>> import numpy as np
>>> a = np.mat([[1, 1, 1], [8, 6, 6], [0, 2, 1]])
>>> b = np.mat([[18], [118], [20]])
>>> a.I * b
matrix([[5.],
[7.],
[6.]])

股神诞生记——概率和似然

问题

概率(probability)和似然(likelihood)的区别?

  • 概率是给定某一参数值,求某一结果的可能性。
  • 似然是给定某一结果,求某一参数值的可能性。

故事

小明称自己炒股一直赚钱,从没亏过。

但是大家都不信!于是他提出一系列证据:

  • 长周期观测和技术分析;
  • 如果被套,不管天荒地老,坚决等到涨上去再卖;
  • 开户后至今每次卖出都是赚钱的。

然而,大家依然不信,认为这是短期结果、幸存者偏差、取样太少……

做个通俗的比喻:小明抛了 10 次硬币,每次都是正面,于是他宣称自己抛出正面的概率是 100%。嗯?鬼信啊……正常人都知道这概率应该是 50% 才合理,只抛 10 次,这取样太少。

后来,小明依然雷打不动如此操作,直到去世,他终于用行动宣告自己股神的事实无法动摇,盈利的概率真的是 100%。

概括

故事中,小明生前炒股盈利的概率本是未知的,只有他去世后才能确定。

用数学语言来描述:

  • 已知:小明生前炒股每次都盈利
  • 求:他炒股盈利的概率是多少?

很明显,小明没死前,这是求不出准确值的!只能说:在已知条件下,小明盈利的概率——最可能是 100%。

概率可能是多少,就是似然;概率最可能是多少,就是极大似然。一切都有可能,但可能性不同,总有一个是最像的。

感谢股神小明用理智而伟大的一生演绎了史诗般的数学教材。

人工神经网络究竟是什么鬼?

难解释的问题,就举个简单的例子说明。PS:稣才入门,也不懂不简单的例子……

题目

有一个未知的函数 f(x1, x2),其中 x1、x2 取值和结果符合下表:

x1 x2 f(x1, x2)
0 0 0
0 1 1
1 0 1
1 1 0

求 f(x1, x2) 的表达式。

求解

人脑抢答

知道异或运算的人可以马上抢答:f(x1, x2) = x1 ^ x2,其中 ^ 是 C 语言里表示 XOR 的运算符。

很明显,这答案是准确无误的,人脑的速度还可以……

放开那个函数,让 AI 来!

人工神经网络(Artificial Neural Network,简称 ANN)解决问题的思路相对而言不太精确,大概就是——通过几个函数算出一个近似值,接近 0 就说是 0,接近 1 就说是 1。

首先,引入一个激活函数:

1
sigmoid(x) = 1.0 / (1 + exp(-x))

举个例子:sigmoid(1.777) = 1.0 / (1 + exp(-1.777)) ≈ 0.855326

类似的激活函数还有 tanh,但其实用 ReLU 更好,既简单又接近生物上的神经元。参考:在神经网络中,激活函数sigmoid和tanh除了阈值取值外有什么不同吗?请问人工神经网络中的activation function的作用具体是什么?为什么ReLu要好过于tanh和sigmoid function?。但是 sigmoid 比较古老,很多教材拿它举例,稣也沿用它。

我们要求的函数是这样的:

1
f(x1, x2) = sigmoid(w1 * g(x1, x2) + w2 * h(x1, x2) + w3)

其中:

1
2
g(x1, x2) = sigmoid(wg1 * x1 + wg2 * x2 + wg3)
h(x1, x2) = sigmoid(wh1 * x1 + wh2 * x2 + wh3)

最终要求的是这三对系数:

1
2
3
wg1 wg2 wg3
wh1 wh2 wh3
w1 w2 w3

通俗说法叫求 w,其中序号为 3 的系数,又叫 bias 或者 b。

函数 f、g、h 其实就是一个神经元(neuron),结构如下:

神经元结构图

神经元结构图 DOT 源文件

训练出来的一个解是:

1
2
3
-5.734 -6.029 1.777
-3.261 -3.172 4.460
-6.581 5.826 -2.444

下面我们来验证一下,举例 x1 = x2 = 0 比较容易算:

1
2
3
4
g(0, 0) = sigmoid(1.777)0.855326
h(0, 0) = sigmoid(4.460)0.988570
f(0.855326, 0.988569) = sigmoid(-6.581 * 0.855326 + 5.826 * 0.988570 + -2.444)
= sigmoid(-2.313491586)0.0900120

结论

ANN 就是数学的运用,训练就是在随机的 w 组合通过参考已知解逐渐纠正误差,逼出正解 w 组合。

打个比方,练习投篮的过程:肉眼观测,无数次调高低角度、出手力度、左右偏差,最终找到一套合适的参数,这个叫培养了球感……

机器学习也差不多是这样的过程,只是它比人快很多。

留一法交叉验证

题目

假设有如下一组输入并输出一个实数的数据,则线性回归(Y = bX + c)的留一法交叉验证均方差为?

X Y
0 2
2 2
3 1

A. 10/27
B. 20/27
C. 50/27
D. 49/27

学习

交叉验证(Cross Validation)

也称作循环估计(Rotation Estimation),是一种统计学上将数据样本切割成较小子集的实用方法。

在模式识别(Pattern Recognition)和机器学习(Machine Learning)的相关研究中,经常会将整个数据集合分成两个部分,分别是训练集合和测试集合。在一个 n 个元素的集合,选择 r 个元素做训练集(非空集,r > 0),剩下的 n - r 个做测试集,这可以用“组合”计算有多少种可能。把每种组合都做过一遍就是交叉验证。

组合(Combination)

nCr 表示由 n 个不同元素中,每次取出 r 个不重复之元素的组合,用符号 C n(下标)r(上标)表示。

留一法交叉验证(Leave-one-out Cross Validation)

只留一个元素做测试集,即:r = n - 1。

均方差

标准差(Standard Deviation),别名:标准偏差、实验标准差、均方差,是离均差平方的算术平均数的平方根,用 σ 表示。标准差是方差的算术平方根。标准差能反映一个数据集的离散程度。平均数相同的两组数据,标准差未必相同。

解题

三个元素的集合留一,一共有 3C1 = 3 种组合,画 3 个点:

  • A = (0, 2)
  • B = (2, 2)
  • C = (3, 1)
  1. 连接 A 和 B,得到直线 Y = 2,C 点的偏差 = 2 - 1 = 1
  2. 连接 A 和 C,得到直线 Y = (6 - X) / 3,B 点的偏差 = 4/3 - 2 = -2/3
  3. 连接 B 和 C,得到直线 Y = 4 - X,A 点的偏差 = 4 - 2 = 2

所以方差为:(1^2 + (2/3)^2 + 2^2) / 3 = (9 + 4 + 4 * 9) / 27 = 49/27

题目说的是“均方差”,根据百度百科标准差词条的说法,“均方差”==标准差,要开平方……所以题目中的答案没有一个是对的。出题者想让我们选 D,稣偏要选 F,你懂的 ck……