AI模型深度学习

多层感知机与布尔函数

字数统计: 1.6k字   |   阅读时长: 6分
,

摘要: 《百面机器学习》Chap9 的一道题，构造 MLP 实现 n 元输入的布尔函数

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

大问题

如何构造一个 MLP 网络实现 n 元输入的布尔函数。

1
2
3
4
考察点:
- 数理逻辑
- 神经网络
- 深度学习

小问题1

二元输入的 MLP 表示异或逻辑最少需要几个隐藏层。

要点1: 零个隐藏层(LR)的情况

二元输入 $\boldsymbol{x} = (x_{1}, x_{2})$, $x_{1}, x_{2}$ 取值为 0, 1，$y$ 的真值为 $x_{1} \oplus x_{2}$

逻辑回归(详细参考 sklearn-逻辑回归)的模型如下:

sigmoid 是单调递增的:

  • 当 $\theta_{0} + \theta_{1}x_{1} + \theta_{2}x_{2}$ 变大的时候，$\hat{y}$ 也变大
  • 当 $\theta_{0} + \theta_{1}x_{1} + \theta_{2}x_{2}$ 变小的时候，$\hat{y}$ 也变小

仅考虑 $x_{1}$ 这一个特征:

  • 如果 $x_{2} = 1$，$x_{1}$ 取值从 0 到 1 使得真值 $y$ 的值从 1 到 0，标签 $y$ 与特征 $x_{1}$ 负相关，这需要 $\theta_{1}$ 取负数
  • 如果 $x_{2} = 0$，$x_{1}$ 取值从 0 到 1 使得真值 $y$ 的值从 0 到 1，标签 $y$ 与特征 $x_{1}$ 正相关，这需要 $\theta_{1}$ 取正数

$\theta_{1}$ 的取值产生矛盾，因此 LR 无法精确学出一个输出为异或的模型表示。

要点2: 一个隐藏层的情况

当有一个隐藏层的感知机设计如下，其中包含模型结构和参数两部分，这里不涉及参数的学习，而是手工设计出的参数。

多层感知机与布尔函数。

二元输入 $\boldsymbol{x} = (x_{1}, x_{2})$, $x_{1}, x_{2}$ 取值为 0, 1，$y$ 的真值为 $x_{1} \oplus x_{2}$。

有两个隐藏神经元，对于隐藏神经元 $z_{1}$:

  • $x_{1}$, $x_{2}$ 的权重均为 1，偏置为 -1: $h_{1} = x_{1} + x_{2} - 1$
  • 激活函数为 ReLU: $z_{1} = max(0, h_{1})$

对于隐藏神经元 $z_{2}$:

  • $x_{1}$, $x_{2}$ 的权重均为 -1，偏置为 1: $h_{2} = - x_{1} - x_{2} + 1$
  • 激活函数为 ReLU: $z_{2} = max(0, h_{2})$

可以发现: $z_{1}$ 在 $x_{1}$ 和 $x_{2}$ 同时为 1 时激活，输出 1, $z_{2}$ 在 $x_{1}$ 和 $x_{2}$ 同时为 0 时激活，输出 1。其余情况输出 0。

真值是 $x_{1}$ 和 $x_{2}$ 同时为 1 时输出 0，$x_{1}$ 和 $x_{2}$ 同时为 0 时输出 0，其余情况输出 1。

因此将 $z_{1}$ 和 $z_{2}$ 进行线性变换即可实现目标的操作: $\hat{y} = - z_{1} - z_{2} + 1$。

小问题2

n 元输入的 MLP，如果只用一个隐藏层，需要多少隐节点能够实现包含 n 元输入的任意布尔函数。

要点1: n 元输入的任意布尔函数

n 元输入的任意布尔哈数可以唯一表示为析取范式(有限个简单合取式构成的析取式)，这里涉及到数理逻辑中的一些概念:

  • 合取是5个基本命题联结词之一 ，用符号 $\land$ 表示。读作“且”，是自然语言中的联结词“并且”的抽象 。
  • 析取是5个基本命题联结词之一 ，用符号 $\lor$ 表示。读作“或”，是自然语言中的联结词“或”的抽象 。
  • 仅有有限个文字构成的析取式称作简单析取式。仅有有限个文字构成的合取式称作简单合取式。
  • 由有限个简单合取式构成的析取式称为析取范式。

要点2: 单个隐节点可以表示任意合取式

对于 n 元输入的其中一个变量 $x_{i}$。

  • 权重 $w_{i}$ 设置如下:
    • 若它在合取式中为正，则权重设为1
    • 若它在合取式中为非，则权重设为-1
    • 若它没有在合取式中出现，则权重为 0
  • 偏置为 - n + 1
  • 激活函数为 ReLU

该隐节点的输出为 $z = max(0, \sum\limits_{i=1}\limits^{n}w_{i}x_{i} - n + 1)$，当且仅当所有 $w_{i}x_{i}$ 均为正时，隐藏单元才被激活(输出1)，否则输出 0。符合合取的定义。

要点3: 输出层可以表示析取式

令所有隐藏元到输出层神经元的参数为 1，且输出神经元的偏置为 0, 这样输出层的公式为 $y = \sum z$，当且仅当所有隐藏元都未激活时，输出才为 0，否则将输出一个正数。符合析取的定义。

要点4: 卡诺图规约布尔函数

对于给定的布尔函数，可以听过卡诺图进行规约，最终规约为若干个析取范式，规约到多少个，就需要多少个隐藏元。

对于 n 元布尔函数的析取范式，最多包含 $2^(n-1)$ 个不可规约的合取范式。

小问题3

考虑多个隐藏层的情况，实现包含 n 元输入的异或最少需要多少个网络节点和网络层。

要点： 隐节点的组织

首先在小问题 1 中我们知道2元输入需要 3 个节点完成一次异或操作。

对于4元输入 $x_{1}, x_{2}, x_{3}, x_{4}$，包含三次异或操作，用 $3 \times 3 = 9$ 个节点可以完成。

以此类推，我们发现多隐层结果可以将隐节点数目从 $O(2^{n-1})$ 降为 $O(3(n-1))$。

以 4 元输入为例，3(n-1) 个节点的组织方式如下:

其中 n 元异或所需的 3(n-1) 个节点可以对应 2(n-1) 个层。这只是比较直观的组织方式。

实际上这个层数可以减少：在同一层计算 $z_{1} = x_{1} \oplus x_{2}$ 和 $z_{2} = x_{3} \oplus x_{4}$，然后再算 $y = z_{1} \oplus z_{2}$，这样可以将层数从 6 降为 4。

每层的节点都两两分组进行异或运算，需要的最少网络层数为 $\lceil 2log_{2}n\rceil$。

Share