十五:多层感知机与布尔函数

今天没有别的话,好好学习,多多转发!

本期内容是

【多层感知机与布尔函数】

场景描述

神经网络概念的诞生很大程度上受到了神经科学的启发。生物学研究表明,大脑皮层的感知与计算功能是通过分多层实现的,例如视觉图像,首先光信号进入大脑皮层的V1区,即初级视皮层,之后依次通过V2层,V4层,即纹外皮层,进入下颞叶参与物体识别。深度神经网络,除了其模拟人脑功能的多层结构,最大的优势在于能够以紧凑简洁的方式来表达比浅层网络更复杂的函数集合(这里的“简洁”可定义为隐层单元的数目与输入单元的数目呈多项式关系)我们的问题将从一个简单的例子引出,已知神经网络中每个节点都可以进行“逻辑与/或/非”的运算,如何构造一个多层感知机 (Multi-Layer Perceptron, MLP) 网络实现n个输入比特的奇偶校验码(任意布尔函数)?

问题描述

如何用多层感知机实现一个异或逻辑(仅考虑二元输入)?

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

上面的问题中,由单隐层变为多隐层,需要多少节点?

合理配置后所需的最少网络层数是多少?

背景知识:数理逻辑、深度学习

解答与分析

1. 如何用多层感知机实现一个异或逻辑(仅考虑二元输入)?

如下图所示(可有其他解法):

2. 如果只使用一个隐层,需要多少隐节点能够实现包含n元输入的任意布尔函数?

包含n元输入的任意布尔函数可以唯一表示为“析取范式 (Disjunctive Normal Form, DNF)”(由有限个简单合取式构成的析取式)的形式。先看一个简单的例子:

由于每个隐节点可以表示析取范式中的一个简单合取式,所以该函数可由包含六个隐节点的三层感知机实现,如下图:

我们可以使用卡诺图表示析取式,即用网格表示真值表,当输入的合取式值为1时,则填充相应的网格。卡诺图中相邻的填色区域可以进行规约,以达到化简布尔函数的目的,如下图所示,七个填色网格最终可规约为三个合取式,故该函数可由包含三个隐节点的三层感知机实现:

于是我们的问题可转化为,寻找“最大不可规约的”n元析取范式DNF,也等价于最大不可规约的卡诺图,直观上,我们只需间隔填充网格即可实现,其表示的布尔函数恰为n元输入的异或操作,如图:

因此,n元布尔函数的析取范式最多包含2(n-1)个合取式,对于单隐层的MLP,需要2(n-1)个隐节点可以实现。

3. 上面的问题中,由单隐层变为多隐层,构造一个n元异或函数需要多少节点?

考虑二元输入的情况,需要三个节点可完成一次异或操作;对于四元输入,包含三次异或操作,需要3×3=9个节点即可完成;而对于六元输入,包含五次异或操作,需要3×5=15个节点…依此类推,n元异或函数需要3(n-1)个节点(包括最终输出节点)。网络的构造方式可参考下图:

我们可以发现,多隐层结构可以将隐节点的数目从指数级O(2(n-1))直接减少至线性级O(3(n﹣1))!

4. 合理配置后所需的最少网络层数是多少?

根据二分思想,每层节点两两分组进行异或运算,需要两个隐层操作完成,故合理配置后需要的网络层数为2㏒2(N)。

本文来自企鹅号 - Hulu媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏转载gongluck的CSDN博客

bmp图像大小biSizeImage算法公式由来

LPBITMAPINFOHEADER lpbmiHeader; // ... 计算BMP方法 法一:lpbmiHeader->biSizeImage = (cx...

4825
来自专栏人工智能LeadAI

决策树会有哪些特性?

决策树(Decision Tree)是机器学习中最常见的算法, 因为决策树的结果简单,容易理解, 因此应用超级广泛, 但是机器学习的专家们在设计决策树的时候会考...

3527
来自专栏余林丰

12.高斯消去法(1)——矩阵编程基础

对于一阶线性方程的求解有多种方式,这里将介绍利用高斯消去法解一阶线性方程组。在介绍高斯消去法前需要对《线性代数》做一下温习,同时在代码中对于矩阵的存储做一个简...

2437
来自专栏数据结构与算法

快速傅里叶变换(FFT)详解

本文只讨论FFT在信息学奥赛中的应用 文中内容均为个人理解,如有错误请指出,不胜感激 前言 先解释几个比较容易混淆的缩写吧 DFT:离散傅里叶变换—> 计算多...

4577
来自专栏小樱的经验随笔

算法--枚举策略

枚举法的基本思想 枚举法的基本思想是根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。 枚举结构:循环...

5129
来自专栏CreateAMind

keras doc 9 预处理等

用以生成一个batch的图像数据,支持实时数据提升。训练时该函数会无限生成数据,直到达到规定的epoch次数为止。

2282
来自专栏数据结构与算法

学大伟业 国庆Day2

期望得分:30+100+0=130 实际得分:30+100+20=150 忍者钩爪 (ninja.pas/c/cpp) 【问题描述】 小Q是一名酷爱钩爪的忍者,...

4914
来自专栏闪电gogogo的专栏

压缩感知重构算法之正则化正交匹配追踪(ROMP)

  在看代码之前,先拜读了ROMP的经典文章:Needell D,VershyninR.Signal recovery from incompleteand i...

3546
来自专栏Leetcode名企之路

【Leetcode】64. 最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

1921
来自专栏null的专栏

机器学习算法实现解析——libFM之libFM的训练过程概述

本节主要介绍的是libFM源码分析的第四部分——libFM的训练。 FM模型的训练是FM模型的核心的部分。 4.1、libFM中训练过程的实现 在FM模型的训练...

48711

扫码关注云+社区

领取腾讯云代金券