【Novikoff 定理】

设训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_N,y_N)\}$ 是是线性可分的，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $n$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})\in \mathbb{R}^n$，输出 $y_i\in\mathcal{Y}=\{+1,-1\}$，则：

1. 存在满足条件 $||W_{opt}||_2=1$ 的超平面 $S:W_{opt}X=\boldsymbol{\omega}_{opt}\cdot\mathbf{x}+\theta_{opt}=0$ 将训练集完全正确分开，且存在 $\gamma>0$，对所有的 $i=1,2,…,N$，有：

【原始形式与对偶形式】

对于感知机模型 $f(\mathbf{x})=\text{sign}(\boldsymbol{\omega}\cdot \mathbf{x}+\theta)$，其损失函数为：

这时感知机学习问题就转换为求解损失函数的最优化问题，即：

【概述】

感知机（Perceptron）是神经网络和支持向量机的起源算法，从结构上来讲，其分为单层感知机（Single Layer Perceptron）和多层感知机（Multi-Layer Perceptron）

单层感知机就是 MP 神经元，其一般用于处理线性可分问题，多层感知机是多个 MP 神经元的累叠，通过增加层数来处理线性不可分问题

【线性可分与分离超平面】

在二维空间上，两类点被一条直线完全分开称为线性可分

【概述】

MP 神经元是由 McCulloch 与 Pitts 于 1943 年发表的神经元模型，其是按照生物神经元的结构与工作原理所构造的一个抽象与简单的模型，简单模拟了神经元的反应流程

在目前的神经网络中，最基本的单元就是神经元（Neuron），即 MP 神经元

【概述】

剪枝（Pruning）是决策树处理过拟合的主要手段，即通过主动去掉一些分支来降低过拟合的风险

决策树剪枝的基本策略有预剪枝（Pre-Pruning）、后剪枝（Post-Pruning）两种，在实际应用中，往往使用后剪枝策略更多一些

Reference

• 回归树（Regression Tree）
• Regression Tree 回归树
• 决策树(分类树、回归树）
• 【机器学习】决策树（上）——ID3、C4.5、CART（非常详细）
• 决策树—ID3、C4.5、CART

【概述】

对于 ID3 和 C4.5 来说，它们只能用来解决分类为问题，因此都是分类决策树

Reference

• 【机器学习】决策树（上）——ID3、C4.5、CART
• 决策树—ID3、C4.5、CART

【ID3 算法】

概述

【概率分布的基尼指数】

基尼指数表示在样本集合中一个随机选中的样本被分错的概率，与信息熵相似，基尼指数越大，样本集合 $D$ 的不确定性也就越大

假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$，则概率分布的基尼指数定义为：

【信息增益与互信息】

在决策树中，信息增益（Information Gain）表示在知道了特征 $X$ 的信息后，使得使类 $Y$ 的信息的不确定性减少了的程度

信息增益是针对特征而言的，因此，特征 $A$ 对于训练集 $D$ 的信息增益 $g(D,A)$，被定义为：训练集 $D$ 的经验信息熵 $H(D)$ 与给定条件下特征 $A$ 与训练集 $D$ 的经验条件熵 $H(D|A)$ 的差，即：