Python

一、前言 本系列是我学习物理引擎相关知识的总结。虽说最初的目标是自己实现一个完整的物理引擎，但是随着学习的深入我认识到，为了让引擎更好地模拟实际，所需要的各种数学原理和处理技巧远远超出了“涉猎”的程度。因此我决定就此止步，但是还是留下了自己的实践成果和经验总结，就在这系列文章中。 本文是“2D物理引擎基础”的第一篇，将介绍物理引擎中物体所需的物理属性 二、物理引擎中的物体 在物理引擎中，模拟的物体对象被假定为刚体。刚体是如此致密坚硬的一种物体，以至于任何碰撞都无法改变其形状。同时物理引擎还常常假定对象的密度均匀，这样对象的质心将只由其几何形状决定。通过这样的假设，物理引擎将能够通过算法优化高效地进行计算模拟： 刚体说明物体不会改变形状，这样当物体受到力的作用时，力的作用效果就不会造成改变物体运动之外的其他影响，如质心改变。 密度均匀使得质心的求解更为方便，将质心位置和偏转角度作为物体属性，就可以完全表示物体上各点的位置信息 接下来所说的物理属性也是在如上约定的基础上的。 三、运动学属性 形状的表示 物理引擎中的形状用描述物体边界的属性表示。不同形状的物体通过不同的几何参数进行表示，如矩形可用长宽表示，圆可用半径长度表示，这些较为简单。更一般地我们考虑多边形，多边形可用顶点坐标表示，但是我们希望形状是位置无关的，那么多边形的顶点坐标也不能在坐标轴上随意选取。虽然 $(0, 0), (1, 0), (1, 1), (0, 1)$ 和 $(1, 1), (2, 1), (2, 2), (1, 2)$ 表示相同形状的多边形，但我们需要选择与位置无关的那一个。我们可以选择使多边形的质心在坐标原点的顶点集合，因为我们后续需要通过质心确定运动学属性。对于均质物体来说，这也就是多边形的几何中心在原点。 我们不能人为地在设置形状时就限制顶点围成的形状中心必须在原点，这对于复杂的形状来说十分困难。我们可以根据顶点集合先确定几何中心位置，再对每一顶点减去中心坐标以将物体平移到集合中心为原点的位置。 对于多边形，计算几何中心的公式为 $$ A = \frac{1}{2} \sum_{i=0}^{N-1}(x_iy_{i+1} - x_{i+1}y_i) $$ $$ c_x = \frac{1}{6A} \sum_{i=0}^{N-1}(x_i + x_{i+1})(x_iy_{i+1} - x_{i+1}y_i) $$ $$ c_y = \frac{1}{6A} \sum_{i=0}^{N-1}(y_i + y_{i+1})(x_iy_{i+1} - x_{i+1}y_i) $$ 其中 $A$ 为多边形面积， $(c_x, c_y)$ 即几何中心位置。需要注意的是，在这个公式中，顶点序列为逆时针，且第一个和最后一个应是同一个坐标，以暗示这是一个闭合图形并且方便公式表示。$N$ 是不重合的顶点个数/边数。 如下是求集合中心的 python 代码 def get_geometric_center(points): area = 0 c_x = c_y = 0 n = points....

一、前言——逻辑分类 机器学习研究的另一种问题为分类问题。给出一些信息，判断是或不是某种物体、属性。比如说给出病人的各项检测指标，判断其是否患病。 对于是、否的判断，这里用 1、0 表示。则训练样本就与之前的线性与多项式回归样本类似。 我们可以试着用一元线性回归来拟合分类问题的样本。 比如对于如下的样本数据 进行一元线性回归后得到 我们将数值大于 0.5 的部分看做预测为真，小于 0.5 的部分看做预测为假。可以看到，此时一元线性回归就已经可以使所有样本点符合判断结果了。 但如果我们在 x 值更大的区域增加更多的样本点，再进行回归 可以看到，有一部分应为 1 的点被分在了 y < 0.5 的部分，被预测为 0。这说明只凭线性回归无法解决分类问题。我们需要另一种回归方法。 二、逻辑回归 线性回归失效的原因在于，拟合的目标是对所有点的方差最小，在分类边界上的样本可能因为其他样本的影响而被分到另一类。而为什么会受到其他样本的影响呢？因为线性回归得到的表达式值域趋向于无穷；而样本的结果却只有 0、1。所以对于一个样本，只要它的特征数值足够大或足够小，就足以产生极大的损失。（为什么可能出现足够远的样本？因为分类问题需要划分出一个边界，在边界两侧可能存在足够大的范围。） 我们要对线性回归进行修改，需要将回归得到的表达式的值域缩小到 0 至 1 的范围。 这里引入 Sigmoid 函数 $$ S(z) = \frac{1}{1 + e^{-z}} $$ 它的图像如下 该函数定义域为 $(-\infty, +\infty)$，值域为 $(0, 1)$ 假设原本线性回归的函数为 $$ f_{\vec{w}, b}(\vec{x}) = \vec{w} \cdot \vec{x} + b $$ 则现在令 $$ f_{\vec{w}, b}(\vec{x}) = S(\vec{w} \cdot \vec{x} + b) $$ 即 $$ f_{\vec{w}, b}(\vec{x}) = \frac{1}{1 + e^{\vec{w} \cdot \vec{x} + b}} $$ 为新的函数。其中 $S(z)$ 即为 Sigmoid 函数。这样，表达式的值域就缩小为了 $(0, 1)$，从而消除了值域对损失的影响。...

一、引言——拟合多项式 考虑如图所示的样本数据： 如果我们用一元线性回归去拟合该数据，会发现直线与数据点拟合效果很差。 通过观察，我们很容易得知数据点满足二次函数，具体地，函数是 $\frac{1}{2}x^2 + 5$。既然用直线 $y = wx + b$ 不能拟合，那么换用二次函数 $y = w_1x^2 + w_2x + b$ 拟合的话效果会如何？ 二、多项式回归的步骤 对于一元多项式函数 $$ y = w_1x + w_2x^2 + \cdots + w_nx^n + b $$ 令 $x^i = y_i$，则原函数变为 $$ y = w_1y_1 + w_2y_2 + \cdots + w_ny_n + b $$ 对于自变量 $x$，只需将 $x^2, x^3, \cdots, x^n$ 看成与 $x$ 不同的特征。此时一个一元多项式函数的拟合问题就转变成了我们已知的多元线性拟合问题。同理，对于多元多项式函数，也可以将其转化为多元线性函数进行拟合。 三、代码实现 对于如下样本： x = np.array(range(-1, 10)) y = (x ** 2) / 2 + 5 将 $x^2$ 也作为一个特征...

一、引言——参数数值对权重的影响 考虑有两个特征的房价预测。其一为房子面积，其二为卧室数量。参数的范围为 $$ x_1 \in [300, 2000] \\ x_2 \in [0, 5] $$ 预测直线为 $$ y = w_1x_1 + w_2x_2 + b $$ 从感性上认知，如果 $w_1$ 的数值大于 $w_2$，那么由特征 $x_1$ 贡献的房价就会远大于特征 $x_2$。因为这样的话，对于同等数值的变化，特征 $x_1$ 的贡献变化大于 $x_2$，而 $x_1$ 的范围又更大，则其对贡献的变化也会更加得大。这是很不合常理的。因此从感性上讲，$w_1$ 的数值应该小于 $w_2$。 另外，根据损失函数的定义 $$ J(\vec{w}, b) = \frac{1}{2m}\sum_{i=1}^{m}(\vec{w}\cdot\vec{x}^{(i)} + b - y^{(i)})^2 $$ 当损失函数值固定时，改变权重 $w_1$, 则对应的权重 $w_2$ 的变化要大于 $w_1$。从图像来说，此时损失函数形成陡峭的“山谷”，它的等高线图类似于椭圆。这时进行梯度下降，在步长较大时可能出现在“崖壁”上来回跳跃的情况。 为了避免这种情况，我们需要找到一种优化的方法。 二、特征缩放 我们要做的是避免出现不同特征的范围差距较大的情况。那么对于极差较大的特征，我们需要将其数值所在的区间范围缩小。这就是特征放缩。 在进行过特征放缩后，损失函数从图像上看将会较原来更接近正圆形，这样的话，寻找通向最低点的路径将会更加容易。 特征缩放有许多不同的方法，如： 除数特征缩放 均值归一化（Mean normalization） Z-score标准化（Z-score normalization） 除数特征缩放指的是将该特征的所有值同除以某一个数，比如说最大值。 $$ x_{scaled} = \frac{x}{x_{max}} $$ 均值归一化是以均值为参照对所有数值进行缩放，公式： $$ x_{scaled} = \frac{x - x_{mean}}{x_{max} - x_{min}} $$ Z-score标准化将数值转换为正态分布。公式： $$ x_{scaled} = \frac{x - \mu}{\sigma} $$ 其中 $$ \mu = \frac{1}{m}\sum_{i = 1}^m x^{(i)} \\ \sigma^2 = \frac{1}{m}\sum_{i = 1}^m (x^{(i)} - \mu)^2 $$ 三、代码实现 利用 Z-score 标准化对特征进行缩放...

一、引言——多特征的房价预测 现实中，某一变量并不一定只与单一变量有关。还以房价来举例，除了位置以外，房价还可能与房子面积、卧室数量、层数、房龄等因素有关。 面积 卧室数 层数 房龄 房价 2104 5 1 45 460 1416 3 2 40 232 1534 3 2 30 315 852 2 1 36 178 … … … … … 对于多个特征的情况，我们需要对之前的一元线性回归进行推广。但在此之前，需要先约定一下使用的符号： 和前面一样，这里将用 $x^{(i)}$ 表示第 i 组样本中的特征。 $y^{(i)}$ 表示第 i 组样本对应的目标结果。不同的是，对于第 j 个特征组，也就是第j个特征对应的数值的序列，采用 $x_{j}$ 表示。那么很自然的， $x^{(i)}_j$ 表示第 j 个特征中的第 i 个值，或者说表示第 i 组样本中的第 j 个特征。 与上文中的列表相结合进行理解，相当于 $x^{(i)}$ 表示第 i 行中非房价的部分，$x_{j}$ 则表示第 j 列中的数值。 要对多元特征进行拟合，也就是找到适当的 $w_1, w_2, ..., w_n$ 使得对任意的 i，有 $$ y^{(i)} = w_1 * x^{(i)}_1 + w_2 * x^{(i)}_2 + ....

一、引言——房价预测问题 问题： 假设我们知道一些房价与距离的对应关系，通过这些已知的信息，能否预测在一定范围内任意距离对应的房价？ 首先考虑最为简单的情况，也就是只有两个房价信息的情况。 如图所示，1km时对应房价为300，2km 时对应房价为500。很容易可以在这两点间连一条直线，这条直线就可以作为对房价的预测。这样用曲线对已知数据中的关系进行估计的方法称为拟合。 （注意，本文只考虑以一元线性函数进行拟合） 类似的，增加房价信息为三个点，如果三点共线，则该直线依然可以作为对房价的拟合。 但更可能的情况是三点不共线，对于更多的数据的情况则更是如此。这样的话要如何找到一条直线来拟合房价信息呢？ 二、损失函数 我们需要找到一种标准来衡量直线对已有信息的拟合程度。 假设当前直线为： $$ y = wx+b $$ 房子距离为 $x^{(1)},x^{(2)},x^{(3)}...,x^{(m)}$，对应的房价为 $y^{(1)},y^{(2)},y^{(3)}...,y^{(m)}$。 则对于每个距离 $x^{(i)}$，当前直线所预测的房价为: $$ \hat{y}^{(i)} = wx^{(i)} + b $$ 该房价与真正的房价的差距为 $$ d = |y^{(i)} - \hat{y}^{(i)}| $$ 绝对值不可导，不妨用平方来代替 $$ d_2 = (y^{(i)} - \hat{y}^{(i)})^2 $$ 对于每个已知的房价信息，当前直线的预测都可能会有偏差，将这些偏差求和得到总的偏差 $$ \sum_{i=1}^{m}(y^{(i)} - \hat{y}^{(i)})^2 $$ 为了排除样本数量不同对偏差的影响，将偏差总和除以样本数量 $$ \frac{1}{m}\sum_{i=1}^{m}(y^{(i)} - \hat{y}^{(i)})^2 $$ 这也就是总体方差的计算式： $$ \sigma^2 = \frac{1}{m}\sum_{i=1}^{m}(y^{(i)} - \hat{y}^{(i)})^2 $$ 对于机器学习，我们将$\hat{y}^{(i)}$展开，并将方差除以2，得到一元线性回归的损失函数（loss function），即 $$ J(w, b) = \frac{1}{2m}\sum_{i=1}^{m}(y^{(i)} - wx^{(i)} - b)^2 $$ 在 $x^{(i)}$，$y^{(i)}$ 确定的情况下，损失函数是关于 $w$ 和 $b$ 的连续可导的二元函数。该函数可以用来衡量 $w，b$ 所确定的直线与已知数据之间的偏差。...