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

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

填坑

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

代码不会骗人,来一个简化的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 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;
}

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

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

代码不会骗人,简单的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

另一次:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

显卡名称包含汉字导致 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 这块代码其实并无与显卡功能相关,去掉这段代码也可以解决问题。

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

用户故事

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

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

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

调研结论

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

参考链接

Windows 10 RDP with RemoteFX

学习 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 版本取消了否决票。

批量导出 QQ 空间说说

创作故事

  2015-03-16 为了导出自己的说说,写了个半自动的程序,手动分析几个参数填到代码理,很快就刷刷地下载了 7 年的说说。第二天,就在知乎回答了两贴。

如何一次性导出QQ空间说说?

如何批量导出特定 QQ 号的所有说说?

  2015-09-07 发现导出程序失效了,参数有点变化,但很快又跟进。

  2015-11-27 又失效了,除了 json 字段有变化,还增加了对 Cookie 的验证,于是又加上了 Cookie 的模拟。

  2015-12-11 又又失效了,这次增加了对 UserAgent 的验证……继续跟进。

  由于知乎的热度,越来越多的人找 UMU 导出,但这个程序是半自动的,会占用宝贵的时间,所以后来干脆让全职带孩子的脑波来,收点人工费。需要的可以联系 QQ:372769132(验证消息:qzone)。

收费规则

1. 8.88 元起,每 1000 条 8.88 元人民币;

2. 未满 1000 条部分,采用进一法,即 10001 条,是收费 8.88 * 2 = 17.76 元;

3. 封顶 88.88 元,所以,如果您的说说很多也不用害怕会很贵。

4. 支持 QQ 红包、微信、支付宝。

FAQ

1. 要交出 QQ 密码吗?

答:不必须。如果您的说说都是公开的,则完全没有必要交出密码。如果您发过只有自己或者少数好友可见的说说,则需要用您的账号密码登陆才能抓全。

2. 我的 QQ 空间被封了,别人都无法访问,可以导出吗?

答:只要您自己能访问就可以,但要提供您的账号和密码。您可以事先改一个临时密码,事后再改掉。

3. 导出的格式是什么样的?

答:主体是一个 json 文件,里面有您全部说说,包括说说本身、别人的回复、图片链接(没有图片本身)。另外生成一份 txt 文件,只有发帖时间和说说本身,其它都没有。

备注

如果有时间会改进,比如说搞成图文并茂的格式,也导出博客。

MongoDB Shard ID hash 算法 std::hash 的跨平台性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <functional>
#include <iomanip>
#include <iostream>
#include <string>


int main()
{

std::string str = "Meet the new boss...";
std::size_t str_hash = std::hash<std::string>{}(str);
std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << std::endl;

str = "Meet the new boss..;";
str_hash = std::hash<std::string>{}(str);
std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << std::endl;

str = "Meet the new boss../";
str_hash = std::hash<std::string>{}(str);
std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << std::endl;

str = "Meet the new boss..,";
str_hash = std::hash<std::string>{}(str);
std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << std::endl;

return 0;
}

Windows, VS 2017 的结果:

hash(“Meet the new boss…”) = 5935324269489717502

hash(“Meet the new boss..;”) = 5935347359233909933

hash(“Meet the new boss../“) = 5935325369001345713

hash(“Meet the new boss..,”) = 5935322070466461080

Ubuntu 16.04, g++ 5.4.0 20160609 的结果:

hash(“Meet the new boss…”) = 10656026664466977650

hash(“Meet the new boss..;”) = 12509209616339026574

hash(“Meet the new boss../“) = 6552276210272946664

hash(“Meet the new boss..,”) = 15639609178671340058

还好我们不会在生产环境,使用 Windows 部署 MongoDB……

1
2
3
std::size_t ShardId::Hasher::operator()(const ShardId& shardId) const {
return std::hash<std::string>()(shardId._shardId);
}

详见:https://github.com/mongodb/mongo/blob/master/src/mongo/s/shard_id.cpp

这个 std::hash 在 x86 和 x64 下都不一样,所以,让我们看看 MongoDB 如何解决这个问题:

MongoDB 3.4 no longer supports 32-bit x86 platforms.

好样的!

求模版函数地址

最近用 WTL 写 Ribbon 界面,发现一个坑。

先看 WTL9.1 的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void (CharFormat::*Getk_[])(IPropertyStore*) = 
{
&CharFormat::Getk_Family,
&CharFormat::Getk_FontProperties_Size,
&CharFormat::Getk_MaskEffect<CFM_BOLD, CFE_BOLD, UI_PKEY_FontProperties_Bold>,
&CharFormat::Getk_MaskEffect<CFM_ITALIC, CFE_ITALIC, UI_PKEY_FontProperties_Italic>,
&CharFormat::Getk_MaskEffect<CFM_UNDERLINE, CFE_UNDERLINE, UI_PKEY_FontProperties_Underline>,
&CharFormat::Getk_MaskEffect<CFM_STRIKEOUT, CFE_STRIKEOUT, UI_PKEY_FontProperties_Strikethrough>,
&CharFormat::Getk_VerticalPositioning,
&CharFormat::Getk_Color<CFM_COLOR, UI_PKEY_FontProperties_ForegroundColor>,
&CharFormat::Getk_Color<CFM_BACKCOLOR, UI_PKEY_FontProperties_BackgroundColor>,
&CharFormat::Getk_ColorType<CFM_COLOR, CFE_AUTOCOLOR, UI_SWATCHCOLORTYPE_AUTOMATIC, UI_PKEY_FontProperties_ForegroundColorType>,
&CharFormat::Getk_ColorType<CFM_BACKCOLOR, CFE_AUTOBACKCOLOR, UI_SWATCHCOLORTYPE_NOCOLOR, UI_PKEY_FontProperties_BackgroundColorType>,
};

其中 Getk_MaskEffect 是个模版函数,实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <DWORD t_dwMask, DWORD t_dwEffects, REFPROPERTYKEY key>
void Getk_MaskEffect(IPropertyStore* pStore)
{
if (SUCCEEDED(pStore->GetValue(key, &propvar)))
{
UIPropertyToUInt32(key, propvar, &uValue);
if ((UI_FONTPROPERTIES)uValue != UI_FONTPROPERTIES_NOTAVAILABLE)
{
dwMask |= t_dwMask;
dwEffects |= ((UI_FONTPROPERTIES) uValue == UI_FONTPROPERTIES_SET) ? t_dwEffects : 0;
}
}
}

然后,在 VS2017 编译失败了……

1>X:\WTL91_5321_Final\Include\atlribbon.h(422): error C2440: ‘initializing’: cannot convert from ‘overloaded-function’ to ‘void (__thiscall WTL::RibbonUI::CharFormat:: )(IPropertyStore )’

1>X:\WTL91_5321_Final\Include\atlribbon.h(422): note: None of the functions with this name in scope match the target type

然后根据错误提示搜到:Cannot take address of template function,https://gcc.gnu.org/bugzilla/show_bug.cgi?id=39018,翻译一下:模版函数的地址转化,分两步走,第一步先转具化,第二步转目标类型,这样可以;直接转过去不可以!

再来看看 WTL10 怎么解决这个问题的!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void (CharFormat::*Getk_[])(IPropertyStore*) = 
{
&CharFormat::Getk_Family,
&CharFormat::Getk_FontProperties_Size,
&CharFormat::Getk_MaskEffectBold,
&CharFormat::Getk_MaskEffectItalic,
&CharFormat::Getk_MaskEffectUnderline,
&CharFormat::Getk_MaskEffectStrikeout,
&CharFormat::Getk_VerticalPositioning,
&CharFormat::Getk_Color,
&CharFormat::Getk_ColorBack,
&CharFormat::Getk_ColorType,
&CharFormat::Getk_ColorTypeBack,
};

原来的模版函数,已经替换成普通函数了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void Getk_MaskEffectBold(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_BOLD, CFE_BOLD, UI_PKEY_FontProperties_Bold);
}

void Getk_MaskEffectItalic(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_ITALIC, CFE_ITALIC, UI_PKEY_FontProperties_Italic);
}

void Getk_MaskEffectUnderline(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_UNDERLINE, CFE_UNDERLINE, UI_PKEY_FontProperties_Underline);
}

void Getk_MaskEffectStrikeout(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_STRIKEOUT, CFE_STRIKEOUT, UI_PKEY_FontProperties_Strikethrough);
}

void Getk_MaskEffectAll(IPropertyStore* pStore, DWORD _dwMask, DWORD _dwEffects, REFPROPERTYKEY key)
{
if (SUCCEEDED(pStore->GetValue(key, &propvar)))
{
UIPropertyToUInt32(key, propvar, &uValue);
if ((UI_FONTPROPERTIES)uValue != UI_FONTPROPERTIES_NOTAVAILABLE)
{
dwMask |= _dwMask;
dwEffects |= ((UI_FONTPROPERTIES)uValue == UI_FONTPROPERTIES_SET) ? _dwEffects : 0;
}
}
}

Mongo Shell 下批量更新集合

需求

延长 mongodb 某集合里的“过期时间”字段。

风险分析

update 一下是很简单,主要怕在 Shell 下操作可能改变数字类型。
先做了实验,发现 3.2 的版本下,并没有这个问题,之前看书,说数字可能被改为双精度,看来是旧版本的不足。

1
2
3
4
db.UMU.find().forEach(function (doc) {
doc.expireDate = NumberLong(doc.updateTime + 180*24*60*60*1000);
db.UMU.save(doc);
})

其中 NumberLong 是必要的,不然更新后,expireDate 的类型并不是和 updateTime 一样的 NumberLong。