# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # 感知器
#
# 感知机(Perceptron)是一种[二元](https://github.com/HAOzj/Classic-ML-Methods-Algo/blob/master/ipynbs/supervised/BasicNotions.ipynb)[线性分类器](https://github.com/HAOzj/Classic-ML-Methods-Algo/blob/master/ipynbs/supervised/BasicNotions.ipynb),是最简单的前向人工神经网络.1957由Rosenblatt在康奈尔航空研究室提出,受到心理学家McCulloch和数理逻辑学家<NAME>关于人工神经元数学模型的启发,开发出的模仿人类具有感知能力的试错,调整的机器学习方法.
#
# ## 算法
#
# 感知机有多种算法,比如最基本的感知机算法,感知机边界算法和多层感知机.我们这里介绍最基本的感知机算法.
#
# 以一组[线性可分的二元d维数据集](https://github.com/HAOzj/Classic-ML-Methods-Algo/blob/master/ipynbs/appendix/BasicNotions.ipynb)$ X =\{ (\vec{x_i}, y_t):y_t \in \{-1,1 \}, i \in [1,n]\}$为训练集,我们寻找一个[分隔超平面](https://github.com/HAOzj/Classic-ML-Methods-Algo/blob/master/ipynbs/appendix/BasicNotions.ipynb)$\vec{w^*} \cdot \vec{x} = 0$.
# 1. 初始化$\vec{w_0} = \vec{0}$,记$t=0$
# 2. 从$X$中拿出一个数据点$\vec{x_i}$,如果$\vec{w^*} \cdot \vec{x}> 0$,预测$\hat{y_i} = 1$,否则$\hat{y_i} = -1$
# 3. 如果$ y_i \neq \hat{y_i}$,更新一次 $\vec{w_t+1} = \vec{w_t} + y_i * \vec{x_i}, t=t+1  $
# 4. 重复2和3,直到遍历$X$
#
# ## 收敛性和复杂度
# 由[Novikoff定理](http://www.cs.columbia.edu/~mcollins/courses/6998-2012/notes/perc.converge.pdf)可知,最多经过$ \frac{R^2}{\gamma ^2}$步迭代就会收敛,其中$R,\gamma $分别为数据集中元素的长度的最大值和到[分割超平面](https://github.com/HAOzj/Classic-ML-Methods-Algo/blob/master/ipynbs/appendix/BasicNotions.ipynb)的最小[几何距离](https://github.com/HAOzj/Classic-ML-Methods-Algo/blob/master/ipynbs/appendix/BasicNotions.ipynb).
#
# 感知机算法复杂度是$O(n)$
#
# ## 优缺点
#
# 感知机最大的特点是简单,并且[错误边界](https://github.com/HAOzj/Classic-ML-Methods-Algo/blob/master/ipynbs/appendix/BasicNotions.ipynb)可控.但基本感知机算法无法处理非线性可分数据集和亦或(XOR)问题,因为基本感知机算法只是在平面画条线,无法把$\{ (-1,-1), (1,1)\}$和$\{ (1,-1), (1,-1)\}$区分开.
#
# ## 发展
#
# 模仿神经科学,我们可以把感知机刻画成一个只有输入层和输出层的神经网络. ![感知机](https://github.com/HAOzj/Classic-ML-Methods-Algo/blob/master/ipynbs/source/img/Perceptron.png?raw=true)
# Rosenblatt等人意识到引入隐藏层,也就是在输入层和输出层之间加入新的层并加入激活函数,![多层感知机](https://github.com/HAOzj/Classic-ML-Methods-Algo/blob/master/ipynbs/source/img/MLP.png?raw=true)可以解决线性不可分的问题.加上上世纪80年代,反向算法的提出,带动了神经网络,以至于现在如火如荼的深度学习的研究.
#



StarcoderdataJupyterScriptsDedupFiltered