2018-07-10 21:00:23

人工神经网络训练方法——后向传播

《人工神经网络训练方法——随机查找》介绍的随机查找方法，有点盲人摸象，所以继续介绍主流的后向传播(BackPropagation)算法。

填坑

先给随机查找做个优化！上篇中的激活函数统一使用 ReLU，其实这是不好的，输出层可以改为 Sigmoid 或 Tanh：

inline double ActivationFunction_ReLU(double x) {
  return std::max(0.0, x);
}
inline double ActivationFunction_Sigmoid(double x) {
  return 1.0 / (1 + exp(-x));
}
inline double ActivationFunction_Tanh(double x) {
  return (tanh(x) + 1.0) / 2;
}

double AnnRun(const double x[2], double* w) {
  double f = ActivationFunction_ReLU(x[0] * w[0] + x[1] * w[1] - w[2]);
  double g = ActivationFunction_ReLU(x[0] * w[3] + x[1] * w[4] - w[5]);
  return ActivationFunction_Sigmoid(f * w[6] + g * w[7] - w[8]);
}

原因很简单，我们已经知道 Xor 的结果不是 0 就是 1，用 ReLU 是可能大于 1 的，而 Sigmoid 和 Tanh 不会大于 1。

后向传播

理论学习：《如何直观地解释 back propagation 算法？》

原理：求导

训练时，x 和 y 都是固定的，要求的是 a 和 b，所以问题是：当 y 偏离了 delta_y，求 a 和 b 应该修正多少？

分别对 a 和 b 求偏导，则:

1 2	dy/da = x dy/db = 1

所以

1 2	delta_a = delta_y / x delta_b = delta_y

代码不会骗人，来一个简化的例子：

// BackPropagation.cpp
//

#include <iostream>

void Train(double& a,
           double& b,
           double input,
           double expect_output,
           double learning_rate) {
  double delta_y = expect_output - (input * a + b);
  if (input != 0) {
    a += (delta_y / input) * learning_rate;
  }
  b += delta_y * learning_rate;
}

int main() {
  // 要求的函数是：y = 2 * x + 3
  const double input[4] = {0, 1, 2, 3};
  const double expect_output[4] = {3, 5, 7, 9};

  // 初始化状态是：y = 1 * x + 4
  double a = 1.0;
  double b = 4.0;

  std::cout << "Initial: y = " << a << " * x + " << b << "\n";

  // 两轮就搞定了
  for (int t = 0; t < 2; ++t) {
    for (int i = 0; i < 4; ++i) {
      Train(a, b, input[i], expect_output[i], 1);
    }
  }
  std::cout << "Trained: y = " << a << " * x + " << b << "\n";

  return 0;
}

2018-07-05 23:45:52

UMUTech

人工神经网络训练方法——随机查找

《人工神经网络究竟是什么鬼？》中没有讲到如何训练神经网络，本篇延续用 XOR 运算为例，介绍一种随机查找的训练方式，主要原理是：随机初始化 w，计算错误率，在循环中，保存错误率小的 w，直到错误率小于等于 0.01 为止。

代码不会骗人，简单的实现如下：

// TrainXor_RandomSearch.cpp
// UMUTech @ 2018-07-05 23:45:52
// Be aware that I'm only a novice to ANN. My apologies for any wrong info.
//
#include <algorithm>
#include <iostream>
#include <random>

std::default_random_engine random_engine;

void RandomizeW(double* w, size_t size) {
  std::uniform_real_distribution<double> r(0, 1);
  for (size_t i = 0; i < size; ++i) {
    w[i] = r(random_engine);
  }
}

void PrintW(double* w, size_t size) {
  for (size_t i = 0; i < size; ++i) {
    std::cout << i << "\t" << w[i] << "\n";
  }
}

double ActivationFunction(double x) {
  // ReLU
  return std::max(0.0, x);
}

double AnnRun(const double x[2], double* w) {
  // bias 乘了 -1，让结果更好地收敛到 [0, 1]
  double f = ActivationFunction(x[0] * w[0] + x[1] * w[1] - w[2]);
  double g = ActivationFunction(x[0] * w[3] + x[1] * w[4] - w[5]);
  return ActivationFunction(f * w[6] + g * w[7] - w[8]);
}

int main() {
  const double input[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
  const double expect_output[4] = {0, 1, 1, 0};

  double last_error = 1000;

  double w[3 * 3];
  double w_copy[3 * 3];

  std::random_device rd;
  random_engine.seed(rd());

  int train_count = 0;
  for (; last_error > 0.01; ++train_count) {
    if (train_count % 10000 == 0) {
      std::cout << "Randomize\n";
      RandomizeW(w, _countof(w));
    }

    memcpy(w_copy, w, sizeof(w));

    // 随机改变 w
    std::uniform_real_distribution<double> r(-0.5, 0.5);
    for (int i = 0; i < 3 * 3; ++i) {
      w[i] += r(random_engine);
    }

    double error = pow(AnnRun(input[0], w) - expect_output[0], 2.0);
    error += pow(AnnRun(input[1], w) - expect_output[1], 2.0);
    error += pow(AnnRun(input[2], w) - expect_output[2], 2.0);
    error += pow(AnnRun(input[3], w) - expect_output[3], 2.0);

    if (error < last_error) {
      // 错误率更小，保存
      last_error = error;
    } else {
      // 恢复 w
      memcpy(w, w_copy, sizeof(w));
    }
  }

  printf("Finished in %d loops.\n", train_count);

  PrintW(w, _countof(w));

  /* Run the network and see what it predicts. */
  printf("Output for [%1.f, %1.f] is %1.f.\n", input[0][0], input[0][1],
         AnnRun(input[0], w));
  printf("Output for [%1.f, %1.f] is %1.f.\n", input[1][0], input[1][1],
         AnnRun(input[1], w));
  printf("Output for [%1.f, %1.f] is %1.f.\n", input[2][0], input[2][1],
         AnnRun(input[2], w));
  printf("Output for [%1.f, %1.f] is %1.f.\n", input[3][0], input[3][1],
         AnnRun(input[3], w));

  return 0;
}

效果主要看人品，可能跑个不停，也可能几乎立刻完成。一次运行结果：

Randomize
Finished in 344 loops.
0       -1.18943
1       -1.60685
2       -0.848489
3       1.28751
4       1.21697
5       0.532657
6       -2.27322
7       -0.77646
8       -1.57966
Output for [0, 0] is 0.
Output for [0, 1] is 1.
Output for [1, 0] is 1.
Output for [1, 1] is 0.

另一次：

Randomize
Finished in 444 loops.
0       1.6138
1       1.4345
2       1.33925
3       1.50895
4       1.09461
5       -0.283878
6       -2.37528
7       1.08117
8       0.239626
Output for [0, 0] is 0.
Output for [0, 1] is 1.
Output for [1, 0] is 1.
Output for [1, 1] is 0.

2018-07-04 11:51:17

诗盗

诗盗·魖

《#诗盗#·魖》：五味俱毒，七情皆苦。人生百态，尽归虚无。

注解

平淡是真，平静是福。

2018-06-29 11:04:11

UMUTech

显卡名称包含汉字导致 DX11 程序无法正常工作

某游戏在 RemoteFX 远程桌面下无法正常运行。提示：

运行引擎需要DX11特征等级10.0

英文版提示：

DX11 feature level 10.0 is required to run the engine.

稣立刻调用 dxdiag 查看，结果 Feature Level 10.0 是支持的！

然后决定自己写个 DX11 程序测试一下，于是找到这里例子：Tutorial 3: Initializing DirectX 11，稍加修改后运行，得到一个错误提示：

MessageBox(hwnd, L"Could not initialize Direct3D.“, L"Error”, MB_OK);

接下来，仔细检查这个初始化过程，发现居然是因为 wcstombs_s 失败引起的：

1 2	// Convert the name of the video card to a character array and store it. error = wcstombs_s(&stringLength, m_videoCardDescription, 128, adapterDesc.Description, 128);

原来是因为 RemoteFX 显卡的名字里有汉字……

RemoteFX 3D 视频适配器

设备名称：

Microsoft RemoteFX 图形设备 - WDDM

通过注册表改显卡名字，测试代码的问题解决！但 wcstombs_s 这块代码其实并无与显卡功能相关，去掉这段代码也可以解决问题。

2018-06-23 21:54:47

UMUTech

RemoteFX 能否用于物理机的远程桌面服务？

用户故事

大学时期（2002-2006 年）经常在学校机房使用远程桌面（RDP）连自己宿舍的电脑，当时的校园网是 100Mpbs 的，但每次一开视频，还是卡成翔……

后来慢慢发现，远程桌面看视频已经不是事儿了，甚至可以玩游戏！

近几年，云游戏的概念越来越流行，曾经用远程桌面连到开启 RemoteFX 的虚拟机上玩过街霸，发现体验很好。于是有了一个疑问：稣有一台 PC，配了块 GeForce GTX 980 Ti 显卡，能不能开启 RemoteFX，然后在烂机器远程桌面上去愉快地玩耍？

调研结论

截止目前还不能在物理机上开启远程桌面的 RemoteFX 功能。其中原因是微软的商业策略，并不是技术问题。

参考链接

Windows 10 RDP with RemoteFX

2018-06-05 23:12:43

宇督观

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

难解释的问题，就举个简单的例子说明。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 比较容易算：

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.090012 ≈ 0

结论

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

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

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

2018-05-31 18:25:32

UMUTech

学习 MongoDB 选举机制

为了快速了解 MongoDB 选举机制，在网上找了一些文章来学习，后来发现里面提到的一些机制都过时了，尝试看代码了解，发现协议有 PV0 和 PV1 两种。

代码：https://github.com/mongodb/mongo/blob/r3.6.5/src/mongo/db/repl/topology_coordinator.cpp

一篇比较新的参考文章：https://blog.csdn.net/wentyoon/article/details/78986174

如果新选举出的主节点立马挂掉，至少需要 30s 重新选主，这个是由 leaseTime 常量决定的：

const Seconds TopologyCoordinator::VoteLease::leaseTime = Seconds(30);

PV0 时，一个反对会将最终票数减 10000，即在绝大多数情况下,只要有节点反对，请求的节点就不能成为主节点，由 prepareElectResponse 函数实现，里面有不少 vote = -10000;，PV1 版本取消了否决票。

2018-05-26 23:27:16

宇督观

留一法交叉验证

题目

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

X	Y
0	2
2	2
3	1

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

概念

1. 交叉验证（Cross Validation）

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

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

2. 组合（Combination）

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

3. 留一法交叉验证（Leave-one-out Cross Validation）

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

4. 均方差

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

解题

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

A = (0, 2)
B = (2, 2)
C = (3, 1)

连接 A 和 B，得到直线 Y = 2，C 点的偏差 = 2 - 1 = 1
连接 A 和 C，得到直线 Y = (6 - X) / 3，B 点的偏差 = 4/3 - 2 = -2/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……

2018-05-22 19:16:12

吓醒

特稣垃

“你留在我身体里的东西，我会用内力逼出来！”

“别装逼，稣戴套了……”

话虽如此，稣还是既吃惊又不解，刚才没有高空坠落啊！这到底是肿么肥事？稣瞄了一眼自己的 iPhone 7，红色的套依然崭新地散发金属般的光泽，显示的时间是凌晨 4 点多，但日期是 2019 年……这个女人，稣好像不认识，为什么会睡在特稣垃里？必须好好追忆一番！

稣买了一辆特稣垃摸抖歪，改造成一个可以写代码和睡觉的移动小房，每周都有一两天，吃完晚饭，上健身房锻炼，洗澡，然后把车停到 JFC 充电车位，开空调，写代码，睡觉。这一系列动作灰常自然，不太可能出八哥，但是这个女人……实在是个异常。稣从来不去酒吧，健身房也没认识这号人物。难道这是特稣垃的车灵？

以其乱猜，不如直接问她，“你是人是车？怎么会在这里？”

“车？你怎么不问是不是鬼？我是你过去妻啊！”

“小凰？你怎么变成这样的……样子都和上次不一样！”

“你忘记了？我们刚刚从 2024 年穿越回来的，这是我 2024 年的样子。”

“呃，这么一说，仔细看你，还有点像小老婆！”

“哈，是的，她因为不好好学习，已经被我取代，都消失好几年了。”

“握叉！？这事情稣会同意？”

“别装逼，你就喜欢知书达理的美女，这不就是我？”

“稣是这种人吗？咳，嗯！稣就是这种人……但为什么我们要穿越到过去？”

“因为在 2024 年，电动房车很流行，很多程序员下班，就找充电桩车位过夜，关系好的一些基友，还会相约停在一起，好交流。然后大量上班族都不买房，不生孩子了，房价大跌。你穿越的目的就是要告诉现在的自己，记得把房子卖了，而且不要买特斯拉，上班族专用的国产电动房车很快就要流行了。”

“这个理由不错，但穿越本身是什么鬼？太不科学了！”

“没错，我就是鬼！我带你来的。”

吓醒。

2018-05-19 21:23:40

宇督观

小本科对非欧几里得几何学脱敏的故事

高中时代

从小喜欢天文和数学，但高中时，有两个事件，促使后来读了挨踢专业。

穷。所有人都说读天文学很烧钱，穷人家是负担不起的，没学到家就出来又不好就业。

高一，有电脑课，但觉得电脑没人脑聪明，没什么兴趣。后来意外看到 Bill Gates 的事迹，明白了挨踢行业是很赚钱的，而且这个行业不怎么需要讲人情世故，也是自己可能擅长的领域。

被非欧几何打击了。和数学课代表交好，经常讨论数学，都喜欢自学超前的知识。其中讨论过的一个最大的未解之谜就是：

三角形内角和可以大于或小于 180 度。

当时只学到一些皮毛概念，仅知道“黎曼几何学是大于，罗巴切夫斯基几何学是小于”，但已经大受打击……

大学时代

大部分时间都用于实践编程技术，原来比较擅长的数学和英语都被牺牲，不怎么认真去学。

但有追究过非欧几何学到底怎么来的：公理体系中采用了不同的平行定理。

在平面内，从直线外一点，至少可以做两条直线和这条直线平行；
在平面内，从直线外一点，有且只有一条直线和这条直线平行；
在平面内，从直线外一点，不能做直线和已知直线平行。

当时没有去深入理解，看了一个例子说球体表面的两条直线都会相交，结果就对非欧几何过敏了……脑子里不断产生抵抗，球面不是平的，球面的直线特么是弯的，这让直男怎么接受？

然后就把非欧几何学当成是外星的哲学了，觉得不是个有用的理论，完全忽视了自以为能理解的广义相对论是和黎曼几何学有关的！

突然脱敏

最近补了点数学基础，顺便想把这个问题解决掉。纠正过程如下：

球面上的两点之间，直线最短，嗯，在球体上看，最短的直线是穿过球体内部的，那个才是直的。

不对，我们讨论的是二维的面，你怎么扯到三维的球体，还内部？

球面上的直线是指什么？用地球来比方，赤道线和纬度线是不是都算？

赤道线是，但其他的纬度线不是，其它纬度线上的两点之间最短的线，并不在纬度线上，纬度线绕的更远，最短的还是这两点加上球心切面上两点之间那段圆弧（劣弧）。

直线只是定义一样，但在两种不同体系的面上样子是不一样的？

是的，“两点之间，直线段最短”球面上的直线，在三维世界看确实是弯的，但在二维世界，它是直的……是直的……是直的。在四维空间看我们的世界，也许也是弯的，但反正我们在三维空间看，是直的！虽然我们能找到其实是弯的证据。

脱敏是很重要的能力

这其实不难理解，但长期自我抑制，不去解决它，再好的理解能力也没用武之地。

有些故事，要先相信，才有续集。

你是直的，还是弯的？