本节目标：

• 了解什么是二元分类
• 了解如何使用逻辑函数进行分类
• 要能够将 k 近邻算法应用于分类问题

回顾
监督学习（Supervised Learning）的流程：

监督学习的两个子类别：回归（Regression）和分类（Classification）。

回归问题中，标记数据 $y_i$ 取连续值，$y_i\in \mathbb{R}$（$\mathbb{R}$ 表示实数集）；而分类问题中，标记数据 $y_i$ 取离散值， y i ∈ { 1 , 2 , … , l } y_i \in \{1,2,\ldots,l\} yi​∈{1,2,…,l} ，即标签属于一个有限的离散集合。

分类问题的示例:

当只有两种类型的标签时(最后一列是否有心脏病），我们将其称为二元分类问题。

标签可以是 {-1, 1} 、{0, 1} 、{1, 2} 、{A, B} 等等。唯一重要的是标签仅取两个离散值，给这些标签取什么名字并不重要。

为什么我们不将回归技术用于分类？

例子如下

假设我们给定一个数据集，目标是训练一个模型来预测旅行者的交通方式。
数据集包含四列：行程时间（Journey time）、费用（Cost）、换乘次数（Changes）和使用的交通工具（Transport used），并给出了四组数据示例。

为解决问题，给每种交通工具分配一个数字标签：飞机（Aeroplane）为 $y=-1$ ，火车（Train）为 $y=0$ ，公共汽车（Bus）为 $y=+1$ 。可以使用类似回归的技术找到一个最适合数据的模型 $y=f(x)$ 。

到此为止，问题就出现了，如果真按照上面那样找这个模型，那么问题如下：

• 问题 1：给标签任意赋值可能会在数据集上强加一些实际上不存在的顺序或结构。例如，当前标签暗示飞机和公共汽车之间的 “距离” 是 $|-1+1|=2$ ，是火车和公共汽车之间距离的两倍，但原始数据并未提及飞机、公共汽车和火车之间的相似性。
• 问题 2：训练的模型 $y=f(x)$ 不太可能只输出离散值（例如，多项式映射到 $(-\infty ,\infty )$ ，而不是 { − 1 , 0 , 1 } \{-1, 0, 1\} {−1,0,1} ）。如何将预测值 $f(x_0)=0.5$ 判定为火车还是公共汽车是一个任意决定，对于 $f(x_0)=100$ 该给出什么预测也不明确。
• 问题 3：真实模型 $y=f_{true}(x)$ 不是连续的（除非它是常数），因为它取离散值。因此，从理论上讲，不能证明这个函数可以被通用逼近器（斯通 - 魏尔斯特拉斯定理）逼近。

贝叶斯分类器（The Bayes Classifier）

贝叶斯推断（Bayesian inference），它是一种数据建模方法，基于数据估计事件发生的概率。与构建模型不同，贝叶斯推断构建的是概率分布。

与回归方法的对比
在处理标签为连续值的回归问题时，我们试图找到一个函数或模型 $f(x_i)\approx y_i$ 。但在贝叶斯推断里，我们试图找到一个函数，该函数近似表示 $f_l(x)\approx \mathbb{P}(y=l|x)$ 。这里，$f_l(x)$ 是一个取值范围在 $[0,1]$ 之间的函数，用于估计数据样本 $x$ 被标记为 $y=l$ 的概率。

当然，在实际应用贝叶斯分类器的过程中，$f_l(x)\in [0,1]$ 这个条件很难被严格满足。(因为现实有噪声、误差，并且特征之前可能不是完全独立等。）

逻辑回归（Logistic Regression）

假设给定数据 $D=\{(x_i,y_i){\}}_{i=1}^N$ ，其中 y i ∈ { − 1 , 1 } y_i \in \{-1, 1\} yi​∈{−1,1} ，属于二分类（binary classification）问题。
目标函数
我们试图找到一个函数，近似表示 $f(x)\approx \mathbb{P}(y=1|x)$ 。$f(x)$ 的取值范围在 $[0,1]$ ，用于估计数据样本 $x$ 被标记为 $y=1$ 的概率。由于只有两个标签，所以只需要找到一个 “$f$” 函数。
多项式不是 $f(x)$ 的理想选择，因为其输出值会超出 $[0,1]$ 范围。一个常用的函数是逻辑函数（Logistic function）。
逻辑函数的表达式为 $f(x)=\frac{e^{a_0+a_1^{\top }x}}{1+e^{a_0+a_1^{\top }x}}$ 。在神经网络文献中，它也被称为 sigmoid 函数。
下图展示了 sigmoid 函数 $y=\frac{e^x}{1+e^x}$ 的图像，该函数的形状为一条 S 形曲线。此外，图中还提到当前标签取值 ({-1, 1}) 是任意选择的，后续为了数学计算方便，会选择 ({0, 1}) 。

对逻辑回归的更多直观理解

寻找逻辑回归函数的动机：
我们需要找到一个函数 $f(x)\approx \mathbb{P}(y=1|x)$ 来近似表示在给定 $x$ 的条件下 $y=1$ 的概率。
由于概率值在 $[0,1]$ 之间，很多函数类难以对其进行近似，所以需要一种将 $[0,1]$ 映射到 $(-\infty ,\infty )$ 的变换。

几率（Odds）的概念
给定一个结果发生的概率为 $P\in [0,1]$，其几率 $O$ 定义为 $O=\frac{P}{1-P}\in [0,\infty )$，它是结果发生的事件数与不发生的事件数之比。
若几率 $O\in [0,\infty )$，那么对数几率 $\log O\in (-\infty ,\infty )$，这是一个有用的变换。

逻辑函数的推导过程：
尝试用最简单的线性函数来拟合对数几率，即 $\log \left(\frac{p(x;\theta )}{1-p(x;\theta )}\right)={\theta }_0+{\theta }_1^{T}x$。
通过对上述等式进行整理，就可以得到逻辑函数 $p(x;\theta )=\frac{e^{{\theta }_0+{\theta }_1^{T}x}}{1+e^{{\theta }_0+{\theta }_1^{T}x}}$。

逻辑 /sigmoid 函数的导数

在继续学习之前，需要计算逻辑 /sigmoid 函数的导数，并且该导数在训练逻辑函数和神经网络时都很有用。

函数表达式
展示了 sigmoid 函数的两种等价形式：$\sigma (x)=\frac{e^x}{1+e^x}=\frac{1}{1+e^{-x}}$ ，以及逻辑函数 $f(x)=\frac{1}{1+e^{-{\theta }_0-{\theta }_1^{\top }x}}=\sigma ({\theta }_0+{\theta }_1^{\top }x)$ 。

求导过程
对 $\sigma (x)$ 求导，根据求导公式和法则，先得到 ${\sigma }^{\prime }(x)=-(1+e^{-x}{)}^{-2}(e^{-x})(-1)$ ，然后逐步化简为 ${\sigma }^{\prime }(x)=\left(\frac{e^{-x}}{1+e^{-x}}\right)\left(\frac{1}{1+e^{-x}}\right)=\sigma (x)\left(1-\frac{e^{-x}}{1+e^{-x}}\right)=\sigma (x)(1-\sigma (x))$ 。
进一步求 $\frac{\partial f(x)}{\partial {\theta }_k}$ ，结果为 ${\sigma }^{\prime }({\theta }_0+{\theta }_1^{\top }x)x_k=f(x)(1-f(x))x_k$ 。

我们如何确定参数

数据设定
假设给定数据集 $D=\{(x_i,y_i){\}}_{i=1}^N$，其中 y i ∈ { 0 , 1 } y_i \in \{0, 1\} yi​∈{0,1}，这是一个二分类问题

条件概率假设
假设对于某些参数 $a_0^{\ast },a_1^{\ast }\in \mathbb{R}$，有 $p(x;a_0^{\ast },a_1^{\ast })=\mathbb{P}(y=1|x)$，其中 $p(x;a_0,a_1)=\frac{e^{a_0+a_1^{\top }x}}{1+e^{a_0+a_1^{\top }x}}$，这是一个逻辑函数形式的概率表达式。

我们的数据集 D 没有告诉我们标签出现的概率，所以在拟合贝叶斯概率模型时，不能最小化平方误差和。

参数求解思路
为了根据给定数据找到合适的 $a_0^{\ast },a_1^{\ast }\in \mathbb{R}$，我们需要最大化似然函数 $$l(a_0,a_1)$$
$l(a_0,a_1)$ 定义为在给定特征数据 $x_i$ 的情况下观察到标签 $y_i$ 的概率，即 max ⁡ a 0 , a 1 l ( a 0 , a 1 ) : = P ( Observing labels  y i  given feature data  x i  for  i ∈ { 1 , … , N } ) \max_{a_0, a_1} l(a_0, a_1) := \mathbb{P}(\text{Observing labels } y_i \text{ given feature data } x_i \text{ for } i \in \{1, \ldots, N\}) a0​,a1​max​l(a0​,a1​):=P(Observing labels yi​ given feature data xi​ for i∈{1,…,N})
通过一系列推导
1.首先等价于 P ( y = y i  for  i ∈ { 1 , … , N } ∣ x 1 , … x n ) \mathbb{P}(y = y_i \text{ for } i \in \{1, \ldots, N\} | x_1, \ldots x_n) P(y=yi​ for i∈{1,…,N}∣x1​,…xn​) 。
2.基于 N 个观测值之间相互独立的假设，进一步推导为 $$\prod _{i:y_i=+1}p(x_i;a_0,a_1)\prod _{j:y_j=0}(1-p(x_j;a_0,a_1))$$ 。
3. 最后，由于对 $y$ 标签的巧妙选择，化简为 $$\prod _{i=1}^{N}p(x_i;a_0,a_1{)}^{y_i}(1-p(x_i;a_0,a_1){)}^{1-y_i}$$
4. 这个式子就是在二分类问题中用于求解参数 a0 和 a1 的最终形式（通过最大化这个式子）。

更通俗易懂的理解（可以跳过）

在二分类问题里，我们要找的就是能够最准确描述数据特征与分类标签之间关系的参数 a0 和 a1。如何确定a0a1就靠上面这个式子。

逻辑回归中的似然函数

似然函数 $l(a_0,a_1)$ 的表达式：
$$l(a_0,a_1):=\prod _{i=1}^{N}p(x_i;a_0,a_1{)}^{y_i}(1-p(x_i;a_0,a_1){)}^{1-y_i}$$
其中 $p(x;a_0,a_1)=\frac{e^{a_0+a_1^{\top }x}}{1+e^{a_0+a_1^{\top }x}}$ 。

似然函数的性质
如果我们很好地选择参数 $a_0$ 和 $a_1$，使得 $p(x;a_0,a_1)\approx \mathbb{P}(y=1|x)$，那么:
当 $y_i=+1$ 时，$p(x_i;a_0,a_1)\approx 1$ ；
当 $y_j=0$ 时，$p(x_j;a_0,a_1)\approx 0$ 。

因此，最优参数会使 $l(a_0,a_1)\approx 1$ ，次优参数会使 $l(a_0,a_1)\approx 0$ 。（代入进上面那个式子试一下就知道了。别忘了有yi和1-yi次方）

决策变量 $a_0$ 和 $a_1$ 与似然函数 $l(a_0,a_1)$ 的输出之间存在复杂的关系。
这使得求解优化问题 max ⁡ a 0 , a 1 { l ( a 0 , a 1 ) } \max_{a_0, a_1} \{l(a_0, a_1)\} maxa0​,a1​​{l(a0​,a1​)} 变得困难。

最大化似然函数

原始优化问题
求解以下优化问题较为困难：${\max }_{a_0,a_1}l(a_0,a_1):={\prod }_{i=1}^{N}p(x_i;a_0,a_1{)}^{y_i}(1-p(x_i;a_0,a_1){)}^{1-y_i}$ ，这是一个关于参数 $a_0$ 和 $a_1$ 的似然函数最大化问题。

为了简化问题，采用求解等价优化问题的思路，将原问题转换为对似然函数取对数后的最大化问题，即从${\max }_{a_0,a_1}l(a_0,a_1)$ 转换为 max ⁡ a 0 , a 1 { log ⁡ l ( a 0 , a 1 ) } \max_{a_0, a_1} \{\log l(a_0, a_1)\} maxa0​,a1​​{logl(a0​,a1​)} 。

对数似然函数展开
利用对数的性质 $\log (ab)=\log (a)+\log (b)$ 和 $\log (a^b)=b\log (a)$ ，对 $\log l(a_0,a_1)$ 进行展开：
max ⁡ a 0 , a 1 { log ⁡ l ( a 0 , a 1 ) } = max ⁡ a 0 , a 1 { ∑ i = 1 N y i log ⁡ ( p ( x i ; a 0 , a 1 ) ) + ( 1 − y i ) log ⁡ ( 1 − p ( x i ; a 0 , a 1 ) ) } \max_{a_0, a_1} \{\log l(a_0, a_1)\} = \max_{a_0, a_1} \left\{\sum_{i = 1}^{N} y_i \log(p(x_i; a_0, a_1)) + (1 - y_i) \log(1 - p(x_i; a_0, a_1))\right\} a0​,a1​max​{logl(a0​,a1​)}=a0​,a1​max​{i=1∑N​yi​log(p(xi​;a0​,a1​))+(1−yi​)log(1−p(xi​;a0​,a1​))}

如何寻找对数似然函数的驻点

回顾解决普通最小二乘法（OLS）问题时，是通过求导并令导数为零来求解的，这里也采用同样的方法。

将参数符号简化，令 $\theta =\left[\begin{array}{c}{a}_0\\ a_1\end{array}\right]$，同时 $p(x;\theta )=\frac{e^{{\theta }_0+{\theta }_1^{\top }x}}{1+e^{{\theta }_0+{\theta }_1^{\top }x}}=\frac{1}{1+e^{-{\theta }_0-{\theta }_1^{\top }x}}$

对数似然函数整理
在对对数似然函数求导之前先进行整理，对数似然函数 $L(\theta ):=\log l(\theta )$ ，经过一系列变换：
$$\begin{array}{rl}L(\theta )& =\sum _{i=1}^N{y}_i\log (p(x_i;\theta ))+(1-y_i)\log (1-p(x_i;\theta ))\\ & =\sum _{i=1}^N{y}_i\log \left(\frac{p(x_i;\theta )}{1-p(x_i;\theta )}\right)+\log (1-p(x_i;\theta ))\\ & =\sum _{i=1}^N{y}_i({\theta }_0+{\theta }_1^{\top }{x}_i)-\log (1+e^{{\theta }_0+{\theta }_1^{\top }{x}_i})\end{array}$$
求导与目标
对 $L(\theta )$ 关于 ${\theta }_k$ 求导：
$$\frac{\partial }{\partial {\theta }_k}L(\theta )=\sum _{i=1}^N{y}_i{x}_{i,k}-\frac{e^{{\theta }_0+{\theta }_1^{\top }{x}_i}}{1+e^{{\theta }_0+{\theta }_1^{\top }{x}_i}}{x}_{i,k}=\sum _{i=1}^N(y_i-p(x_i;\theta ))x_{i,k}$$

为了方便，引入符号 $x_{i,0}=1$

需要找到 $\theta$ 使得 $$\sum _{i=1}^N(y_i-p(x_i;\theta ))x_{i,k}=0$$

其中 $p(x;\theta )=\frac{e^{{\theta }_0+{\theta }_1^{\top }x}}{1+e^{{\theta }_0+{\theta }_1^{\top }x}}$ ,这一问题涉及到求解超越方程。

不幸的是，求解逻辑回归问题涉及到求解超越方程。一般来说，超越方程没有解析解，只有近似的求根方法，如牛顿法（Newton’s method） 。

超越方程

定义
超越方程是一类需要找到一个数（实数、复数或多维等）来满足包含非多项式项恒等式的问题。一般来说，超越方程包含了指数函数、三角函数、对数函数等非多项式项。

进一步的理解
从数学原理上看，解析解是指可以用有限次的常见运算（加、减、乘、除、乘方、开方等）和基本函数（幂函数、指数函数、对数函数、三角函数、反三角函数等）来表示的解。

超越方程由于其函数的复杂性和非线性，很难甚至无法通过有限次的代数运算和基本函数组合来精确表示其解。例如 $e^x+x^2-1=0$ ， $e^x$ 的存在使得方程不能像一元二次方程 $a{x}^2+bx+c=0$（可以用求根公式 $x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$ 这样的解析形式求解 ）那样，用有限次常见运算和基本函数组合给出精确的解。

所以，对于超越方程，通常只能采用近似的求根方法，如牛顿法，它是通过迭代的方式不断逼近方程的根。
超越方程由于其函数的复杂性和非线性，很难甚至无法通过有限次的代数运算和基本函数组合来精确表示其解。

牛顿法（Newton’s Method）求根。

求解$f(x)=0$时牛顿法:

1. 首先找到一个点xi，这个点可以随机，当然选择离x轴交点近的地方更好。
2. 下一步找到斜率为 $f^{\prime }(x_i)$ 的直线：直线的一般方程为 $y=mx+c$，其中斜率 $m=f^{\prime }(x_i)$，且直线过点 $(x_i,f(x_i))$，由此可得截距 $c=f(x_i)-f^{\prime }(x_i)x_i$。
3. 找到直线与 $x$ 轴的交点：令 $y=0$，即 $0=m{x}_{i+1}+c$，从而推导出 $x_{i+1}=x_i-\frac{f(x_i)}{f^{\prime }(x_i)}$。
4. 将$x_{i+1}$视作新的xi，重复上面的步骤，直到$f(x_i)$趋近于0.

但是结合上述问题，求解最大化似然函数市不是要$f(x)=0$，而是要需求驻点，即求解 $f^{\prime }(x)=0$.

求解 $f^{\prime }(x)=0$ 可能比较困难，所以与上面类似，应用牛顿法，其迭代公式为 $x_{i+1}=x_i-\frac{f^{\prime }(x_i)}{f^{\prime \prime }(x_i)}$，其中 $f^{\prime }(x_i)$ 是函数 $f(x)$ 在 $x_i$ 处的一阶导数，$f^{\prime \prime }(x_i)$ 是函数 $f(x)$ 在 $x_i$ 处的二阶导数。

高维空间中的牛顿 - 拉夫森方法

刚刚的牛顿法求根是比较容易理解的，不过我们还需要扩展一下，从实数空间扩展到n维实数空间。

为求解无约束优化问题 ${\min }_{x\in {\mathbb{R}}^n}f(x)$（即在 n 维实数空间中求函数 $f(x)$ 的最小值），应用的迭代公式为 $x_{i+1}=x_i-(Hf(x_i){)}^{-1}\nabla f(x_i)$。这里 $x\in {\mathbb{R}}^n$，当 (n = 1) 时，就退化为上面的一维的结果。

我们期望 $x^{\ast }={\lim }_{i\to \infty }{x}_i$ 满足 $f(x^{\ast })={\min }_{x\in {\mathbb{R}}^n}f(x)$，即迭代的极限点 $x^{\ast }$ 是函数 $f(x)$ 在 $n$ 维空间中的最小值点。

补充两个概念：

1. $\nabla f(x)$ 表示梯度向量，其形式为 $\left[\begin{array}{c}\frac{\partial }{\partial x_1}f(x)\\ ⋮\\ \frac{\partial }{\partial x_n}f(x)\end{array}\right]$，它是由函数 $f(x)$ 对各个变量 $x_1,x_2,\cdots ,x_n$ 的一阶偏导数组成的向量。(简单理解：可以当作一次导数）
2. $Hf(x)$ 表示海森矩阵，形式为 $\left[\begin{array}{ccc}\frac{{\partial }^2}{\partial x_1^2}f(x)& \cdots & \frac{{\partial }^2}{\partial x_1\partial x_n}f(x)\\ ⋮& \ddots & ⋮\\ \frac{{\partial }^2}{\partial x_n\partial x_1}f(x)& \cdots & \frac{{\partial }^2}{\partial x_n^2}f(x)\end{array}\right]$，它是由函数 (f(x)) 对各个变量的二阶偏导数组成的 $n\times n$ 矩阵。 （简单理解：二次导数）

应用牛顿 - 拉夫森方法求解逻辑回归

核心迭代公式为 ${\theta }_{i+1}={\theta }_i-(HL({\theta }_i){)}^{-1}\nabla L({\theta }_i)$。这里应用牛顿 - 拉夫森方法时，用 $-L(\theta )$（负对数似然函数）替代了常规函数 $f(x)$，原因是我们要最大化对数似然函数 $L(\theta )$。

对数似然函数 $L(\theta )$

回忆对数似然函数的表达式为 $L(\theta ):={\sum }_{i=1}^N{y}_i({\theta }_0+{\theta }_1^{\top }x)-\log (1+e^{{\theta }_0+{\theta }_1^{\top }x})$，其中 $y_i$ 是样本标签，${\theta }_0$ 是截距项，${\theta }_1$ 是参数向量，$x$ 是特征向量。

梯度向量 $\nabla L({\theta }_i)$ 和海森矩阵 $HL({\theta }_i)$

接下来要找到 $HL({\theta }_i)$ 和 $\nabla L({\theta }_i)$ 的表达式：

• 梯度向量 $\nabla L(\theta )$ 的第 $k$ 个分量 $[\nabla L(\theta ){]}_k=\frac{\partial }{\partial {\theta }_k}L(\theta )={\sum }_{i=1}^N(y_i-p(x_i;\theta ))x_{i,k}$，其中 $p(x;\theta )=\frac{e^{{\theta }_0+{\theta }_1^{\top }x}}{1+e^{{\theta }_0+{\theta }_1^{\top }x}}$ 是逻辑回归的预测概率。
• 海森矩阵 $HL(\theta )$ 的第 $l,k$ 个元素 $[HL(\theta ){]}_{l,k}=\frac{{\partial }^2}{\partial {\theta }_l\partial {\theta }_k}L(\theta )=-{\sum }_{i=1}^N{x}_{i,k}{x}_{i,l}(1-p(x_i;\theta ))p(x_i;\theta )$ 。
• 补充说明：刚刚已经求得了关于 Sigmoid 函数的导数：$\frac{\partial p(x;\theta )}{\partial {\theta }_k}={\sigma }^{\prime }({\theta }_0+{\theta }_1^{\top }x)x_k=p(x;\theta )(x)(1-p(x;\theta )(x))x_k$，用于辅助理解上述两个式子的推导。

将牛顿 - 拉夫森方法用于逻辑回归的矩阵形式表达。

定义矩阵：

• $X:=\left[\begin{array}{cccc}1& x_{1,1}& \cdots & x_{m,1}\\ & ⋮& ⋮& \\ 1& x_{1,N}& \cdots & x_{m,N}\end{array}\right]\in {\mathbb{R}}^{N\times (m+1)}$，这是特征矩阵，每一行代表一个样本，每一列代表一个特征，第一列元素全为1，用于表示截距项。
• $Y:=\left[\begin{array}{c}{y}_1\\ ⋮\\ y_N\end{array}\right]\in {\mathbb{R}}^N$，是样本标签向量。
• $P(\theta ):=\left[\begin{array}{c}p(x_1;\theta )\\ ⋮\\ p(x_N;\theta )\end{array}\right]\in {\mathbb{R}}^N$，是模型预测的概率向量，其中 $p(x_i;\theta )$ 是样本 $x_i$ 属于正类的概率。
• $W(\theta ):=diag((1-p(x_1;\theta ))p(x_1;\theta ),\cdots ,(1-p(x_N;\theta ))p(x_N;\theta ))\in {\mathbb{R}}^{N\times N}$，是对角矩阵，对角元素由 $(1-p(x_i;\theta ))p(x_i;\theta )$ 构成。

推导梯度向量和海森矩阵的矩阵形式
已知 $[\nabla L(\theta ){]}_k={\sum }_{i=1}^N(y_i-p(x_i;\theta ))x_{i,k}$ 和 $[HL(\theta ){]}_{l,k}=-{\sum }_{i=1}^N{x}_{i,k}{x}_{i,l}(1-p(x_i;\theta ))p(x_i;\theta )$，推导出：

• 梯度向量 $\nabla L(\theta )=X^{\top }(Y-P(\theta ))$。
• 海森矩阵 $HL(\theta )=-X^{\top }W(\theta )X$。

将上述结果代入牛顿 - 拉夫森方法的迭代公式 ${\theta }_{i+1}={\theta }_i-(HL({\theta }_i){)}^{-1}\nabla L({\theta }_i)$，得到 $${\theta }_{i+1}={\theta }_i+(X^{\top }W({\theta }_i)X{)}^{-1}{X}^{\top }(Y-P({\theta }_i))$$

现在我们只需要初始化${\theta }_0$就好了：通常，我们随机初始化算法的参数 ${\theta }_0\in {\mathbb{R}}^m$，其中 $m$ 是特征的数量（不包括截距项对应的维度）。

例子

数据集：

$x$	-1	0
$y$	0	1

即当 $x=-1$ 时，对应的标签 $y=0$；当 $x=0$ 时，对应的标签 $y=1$。

逻辑回归模型的表达式：$f(x)=\frac{1}{1+e^{-{\theta }_0-{\theta }_{1}x}}$，该模型用于预测样本属于正类的概率。
考虑参数初始化 ${\theta }_{\text{initialisation}}=[1,1{]}^{\top }$，则初始模型为 $f_{\text{initialisation}}(x)=\frac{1}{1+e^{-1-x}}$。

• 当 $x=-1$ 时，$f_{\text{initialisation}}(-1)=\frac{1}{1+e^0}=0.5$，即模型预测 $x=-1$ 具有标签 $y=0$ 的概率为 $50\%$。
• 当 $x=0$ 时，$f_{\text{initialisation}}(0)=\frac{1}{1+e^{-1}}\approx 0.73$。

模型预测 $x=-1$ 有 $50/50$ 的概率标签为 $y=0$，这表明该模型当前表现不佳（Bad model）。使用牛顿法更新模型参数，以获得更好的模型。

使用牛顿法对逻辑回归模型进行参数更新

牛顿法用于逻辑回归参数更新的公式：${\theta }_{i+1}={\theta }_i+(X^{\top }W({\theta }_i)X{)}^{-1}{X}^{\top }(Y-P({\theta }_i))$。

矩阵计算过程

1. 特征矩阵 $X$、标签向量 $Y$ 和预测概率向量 $P(\theta )$：
   • $X=\left[\begin{array}{cc}1& -1\\ 1& 0\end{array}\right]$，$Y=\left[\begin{array}{c}0\\ 1\end{array}\right]$。
   • 当参数 $\theta =\left[\begin{array}{c}1\\ 1\end{array}\right]$ 时，$P(\left[\begin{array}{c}1\\ 1\end{array}\right])=\left[\begin{array}{c}\frac{1}{1+e^0}\\ \frac{1}{1+e^{-1}}\end{array}\right]=\left[\begin{array}{c}0.5\\ 0.7311\end{array}\right]$。
2. 权重矩阵 $W(\theta )$：
   • $W(\left[\begin{array}{c}1\\ 1\end{array}\right])=\left[\begin{array}{cc}(1-0.5)\times 0.5& 0\\ 0& (1-0.73)\times 0.73\end{array}\right]=\left[\begin{array}{cc}0.25& 0\\ 0& 0.2\end{array}\right]$。
3. 计算 $X^{\top }WX$： - $X^{\top }WX=\left[\begin{array}{cc}1& 1\\ -1& 0\end{array}\right]\left[\begin{array}{cc}0.25& 0\\ 0& 0.2\end{array}\right]\left[\begin{array}{cc}1& -1\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}0.45& -0.25\\ -0.25& 0.25\end{array}\right]$。
4. 计算 $(X^{\top }WX{)}^{-1}$： - 通过公式计算 $(X^{\top }WX{)}^{-1}=\frac{1}{0.45\times 0.25-0.25^2}\left[\begin{array}{cc}0.25& 0.25\\ 0.25& 0.45\end{array}\right]=\left[\begin{array}{cc}5& 5\\ 5& 9\end{array}\right]$。
5. 计算 $X^{\top }(Y-P)$： - $X^{\top }(Y-P)=\left[\begin{array}{cc}1& 1\\ -1& 0\end{array}\right](\left[\begin{array}{c}0\\ 1\end{array}\right]-\left[\begin{array}{c}0.5\\ 0.73\end{array}\right])=\left[\begin{array}{c}0.23\\ 0.5\end{array}\right]$。
6. 更新参数 $\theta$： - 最终得到更新后的参数 ${\theta }_{\text{update}}=\left[\begin{array}{c}1\\ 1\end{array}\right]+\left[\begin{array}{cc}5& 5\\ 5& 9\end{array}\right]\left[\begin{array}{c}0.23\\ 0.5\end{array}\right]=\left[\begin{array}{c}2.25\\ 4.35\end{array}\right]$。

根据之前计算得到更新后的参数 ${\theta }_{\text{update}}=\left[\begin{array}{c}2.25\\ 4.35\end{array}\right]$，更新后的逻辑回归模型为 $f_{\text{update}}(x)=\frac{1}{1+e^{-2.25-4.35x}}$。

模型预测结果 ：

• 当 $x=-1$ 时，$f_{\text{update}}(-1)=\frac{1}{1+e^{2.1}}=0.1$，即模型预测 $x=-1$ 具有标签 $y=1$ 的概率较低。
• 当 $x=0$ 时，$f_{\text{update}}(0)=\frac{1}{1+e^{-2.25}}=0.9$，即模型预测 $x=0$ 具有标签 $y=1$ 的概率较高。

更新后的模型能够正确地对样本进行预测，对于 $x=-1$ 预测为 $y=1$ 的概率较低，对于 $x=0$ 预测为 $y=1$ 的概率较高。更严格的模型性能分析还应包括准确率、特异性、ROC 表格、测试数据误差等指标。

分类问题中是否存在更简单的分类方法？

之前。我们尝试找到函数 $f(x)$ 来近似条件概率 $\mathbb{P}(y=1|x)$，这要求 $f(x)$ 的取值范围在 [0, 1] 之间。为解决此问题，我们任意选择了逻辑函数（logistic function）来作为 $f(x)$ 。

逻辑函数的局限性

尽管逻辑函数具有一些良好的性质，但是有的时候它实在是太复杂 。因此，我们考虑一种更简单的方法，即假设 $f(x)$ 没有特定的参数结构。

更简单的方法:k邻近

$f(x)$ 等于在 $x$ 的 $k$ 个最近邻训练数据点中 $y$ 的最常见值，这实际上就是 $k$ - 近邻（k - nearest neighbors，KNN）算法的基本思想。
在这种方法中，不对 $f$ 做任何参数化结构的假设。此方法的逻辑函数的表达式 $f(x)=\frac{e^{a_0+a_1^{\top }x}}{1+e^{a_0+a_1^{\top }x}}$。

k - 近邻分类器（K - Nearest Neighborhood Classifier）的原理和公式推导

数据集设定

假设给定一个数据集 $\mathcal{D}=\{(x_i,y_i){\}}_{1\le i\le N}$，其中 $x_i$ 是特征向量，$y_i$ 是对应的标签，N 是数据集中样本的数量。

近邻点索引集合

定义 $N_k(x_0)$ 为在数据集 { x i } i = 1 N \{x_i\}_{i = 1}^{N} {xi​}i=1N​ 中与 $x_0$ 最接近的 $k$ 个点的索引集合。

条件概率近似公式

对于给定的 $x=x_0$，类别 $y=l$ 的条件概率 $\mathbb{P}(y=l|x=x_0)$ 可以近似为：
P ( y = l ∣ x = x 0 ) ≈ 1 k ∑ i ∈ N k ( x 0 ) 1 { y i } ( l ) \mathbb{P}(y = l|x = x_0) \approx \frac{1}{k} \sum_{i\in N_k(x_0)} \mathbb{1}_{\{y_i\}}(l) P(y=l∣x=x0​)≈k1​i∈Nk​(x0​)∑​1{yi​}​(l)
其中，$1_A(x)$ 是指示函数，当 $x\in A$ 时取值为 $1$，否则为 $0$。这个公式的含义是，在 $x_0$ 的 $k$ 个近邻点中，标签为 $l$ 的点的数量占近邻点总数 $k$ 的比例，即近邻中标签为 $l$ 的点的频率。

分类器模型

选择模型 $f(x_0)$为：
f ( x 0 ) = max ⁡ l { 1 k ∑ i ∈ N k ( x 0 ) 1 { y i } ( l ) } f(x_0) = \max_{l} \left\{ \frac{1}{k} \sum_{i\in N_k(x_0)} \mathbb{1}_{\{y_i\}}(l) \right\} f(x0​)=lmax​⎩ ⎨ ⎧​k1​i∈Nk​(x0​)∑​1{yi​}​(l)⎭ ⎬ ⎫​
即 $f(x_0)$ 取使得上述条件概率近似值最大的类别 (l)。

总结

图片底部绿色区域总结了 (k) - 近邻分类器的核心思想：(f(x)) 等于在 (x) 的 (k) 个最近邻训练数据点中 (y) 的最常见值，也就是将未知样本 (x) 分类为其 (k) 个近邻中出现频率最高的类别。

K邻近例子