C语言中的机器学习基础，第一部分Draft

2023年8月9日

欢迎来到我的N部分系列（N待定），关于C语言中的机器学习基础。这个系列将专注于基础，我认为这是许多与机器学习和神经网络相关的在线资源中所缺失的。

当我最初开始学习神经网络时，我发现的所有文章要么是

展示了几行Tensorflow代码，用于获取训练数据、训练模型并运行预测，要么是
提供了一些底层教程，给出了实现细节，但让我产生了更多的问题而不是答案

它们都没有带你走过那些（相当无聊的）基础概念，这些概念最终构建出神经元。这就是我在这系列文章中想要做的。它将

通过适量的数学建立直觉
将其转化为代码，全部用C语言编写，不使用任何库，以便隐藏的实现细节为零

预备知识

我将对您做出以下假设：

您熟悉 C 语言或类 C 语言（如 C++、Java、C# 等）
您理解导数（例如 $\frac{d}{d x}$ ）和偏导数（例如 $\frac{\partial}{\partial x}$ ）

引言

我们从线性回归这样平凡的内容开始；这与机器学习有什么关系？这如何帮助我创建下一个ChatGPT？

为了老生常谈，让我们问问ChatGPT它认为机器学习是什么：

什么是“机器学习”这一术语最基本且最简化的定义？

机器学习是一个过程，计算机通过数据学习，以在任务上提高性能，而无需显式编程（重点是我加的）。

本系列将关注的任务是预测。也就是说，我们希望我们的模型学会如何根据给定的输入数据预测结果。随着我们为它提供更多数据，它应该无需显式编程，就能在未见过的数据上做出更好的预测。

让我们首先定义一个简单的模型。

单变量线性模型

第一部分代码

该模型适用于以下预测任务：a) 只有一个输入变量，b) 只有一个输出变量，c) 输入和输出变量之间的关系近似线性。其定义如下。

\overset{y}{^} = w x + b

用代码表示为：

struct linear_model {
	double w;
	double b;
};

double predict(struct linear_model m, double x) {
	return m.w * x + m.b; // y hat
}

如你所见，模型本身由两个参数 $w$ 和 $b$ 定义，它们决定了预测输出 $\overset{y}{^}$ 与输入 $x$ 之间的关系。为了测试这个模型，我们生成一些数据。

// 房屋面积，单位为平方英尺。我们的 x 变量
static double xs[] = {2360, 5272, 4592, 1966, 5926, 4944, 4671, 4419, 1630, 3185};
// 对应的房屋价格，单位为千美元。我们的 y 变量
static double ys[] = {1359, 2576, 2418, 655, 2531, 2454, 2657, 1541, 1057, 1657};

现在，我们的任务是根据房屋面积预测房价，因此我们需要找到一个定义“最优”模型的 $w$ 和 $b$ 。但如何定义“最优”呢？它是误差最小的模型，或者说误差最小的模型。但如何定义“误差”呢？一种方法是

误差 = 预测值 - 实际值

这种方法的问题在于，最小化误差会使我们的模型的最优预测值为 $- \infty$ ，这是误差的最小值，但不是我们想要的。我们需要的是一个凹的误差函数，这意味着它有一个有界的最小值，该最小值实际上反映了良好的性能。

误差 = (预测值 - 实际值)^{2}

这个函数的最小值是 $0$ ，如果 $误差 \approx 0$ ，那么 $预测值 \approx 实际值$ 。因此，最小化这个函数将为我们提供最优模型。从现在开始，我们将其称为损失函数。

double loss(double y_hat, double y) {
	double diff = y_hat - y;
	return diff * diff;
}

但我们希望最小化所有数据样本的损失。因此，我们取所有 $m$ 个样本的平均损失，并将其称为总误差函数 $J_{w b}$ 。

J (w, b) = \frac{1}{m} i = 0 \sum m - 1 (\overset{y}{^}^{(i)} - y^{(i)})^{2}

double error(struct linear_model model, double *xs, double *ys, int m) {
	double sum = 0.0;
	for (int i = 0; i < m; i++) {
		double y_hat = predict(model, xs[i]);
		double _loss = loss(y_hat, ys[i]);
		sum += _loss;
	}
	return sum / ((double) m);
}

这为我们提供了一个数字，告诉我们模型有多差。现在我们需要将其降至零。

## 最小化误差

朴素方法

一种朴素的做法是生成大量具有不同 w 和 b 值的 linear_model，然后看看哪个模型在我们的数据集上具有最小的 error。

struct linear_model
optimize_brute_force(double *xs, double *ys, int m)
{
		const double min = -1000.0, max = 1000.0;
		const int num_samples = 1e4;
		const double increment = (max - min) / ((double)num_samples);

		double min_error = 1e10;
		struct linear_model curr;
		struct linear_model optimal;
		// 遍历 (w, b) 在 [min, max] x [min, max] 范围内
		// 并找到误差最小的组合
		for (int i = 0; i < num_samples; i++) {
				curr.w = min + increment * i;
				for (int j = 0; j < num_samples; j++) {
						curr.b = min + increment * j;

						double err = error(curr, xs, ys, m);
						if (err < min_error) {
								min_error = err;
								optimal = curr;
						}
				}
		}
		return optimal;
}

让我们在数据集上运行它：

暴力优化模型: {w: 0.400000, b: 331.800000}
误差: 88068.508000

它的预测效果如何？

相当不错！而且我们知道理论最优值在给定值的 $\pm increment$ 或 $\pm 0.2$ 范围内。

但说实话：这是一个极其次优的解决方案。相对于样本数量，运行时间是 $O (n^{2})$ ，如果我们只有两个参数 w 和 b，这还不算太糟糕。但如果我们有，比如说 10 个参数，那就会是 $O (n^{10})$ 。这使得它在有多个输入变量的情况下极其不切实际，而几乎所有现实世界的问题都有多个输入变量。

梯度下降

所以我们需要找到一种比盲目猜测每个数字更聪明的方法。

警告：微积分（😱）即将登场

开个玩笑。

想象一下：你被随机丢在一个丘陵地区的某个位置。之前有人告诉你，某个地方有一个山谷。在这个山谷里，有食物和水。如果你找不到这个山谷，你就会死。而且，这里有大雾，你只能看到周围一英尺的范围。如果你只知道山谷位于该地区的最低点，你该如何找到它？

策略：

观察你周围的地面
哪个方向的下降最陡峭？
朝那个方向移动一英尺
回到步骤1

只要山谷存在，这个方法就能带你到达谷底。剧情反转：这个丘陵地区实际上被称为误差山丘，而你的策略被称为梯度下降！数学时间到了。

数学

首先，我们需要观察稍微改变 $b$ 对误差的影响。这是误差函数对 $b$ 的导数。求解

J (w, b) = \frac{1}{m} i = 0 \sum m - 1 (\overset{y}{^}^{(i)} - y^{(i)})^{2} = \frac{1}{m} i = 0 \sum m - 1 (w x^{(i)} + b - y^{(i)})^{2}

\frac{\partial J}{\partial b} = 2 \frac{1}{m} i = 0 \sum m - 1 (w x^{(i)} + b - y^{(i)})

我们还需要改变 $w$ ，因此让我们计算误差对 $w$ 的导数。

\frac{\partial J}{\partial w} = 2 \frac{1}{m} i = 0 \sum m - 1 (w x^{(i)} + b - y^{(i)}) x^{(i)}

这里我们只是使用了乘积法则和链式法则。因此，这两个导数都回答了以下问题：“如果我稍微增加变量，误差会增加多少？”。现在，我们希望误差减小，因此我们应该朝相反的方向移动。

算法：

设置起点： $w := 0, b := 0$
朝导数的相反方向移动变量，步长为 $α$ ： $w := w - α \frac{\partial J}{\partial w}, b := b - α \frac{\partial J}{\partial b}$
转到步骤 2。

最终会发生的情况是，当 $w, b$ 达到最小值时，导数将趋近于 0。这是因为在最小值（或谷底）处，无论朝哪个方向移动，误差都不会显著变化。

代码

首先，我们编写一个计算导数的函数，并将其打包到一个名为 gradient 的结构体中。

struct gradient {
		double dJ_dw;
		double dJ_db;
};

struct gradient
calculate_gradient(struct linear_model model, double *xs, double *ys, int m)
{
		double dJ_dw = 0.0, dJ_db = 0.0;
		for (int i = 0; i < m; i++) {
				double y_hat = predict(model, xs[i]);
				double diff = y_hat - ys[i];
				dJ_db += diff;
				dJ_dw += diff * xs[i];
		}
		// 我们将把2的因子推到alpha中，以节省一次乘法运算
		dJ_dw /= ((double)m);
		dJ_db /= ((double)m);
		return (struct gradient){.dJ_dw = dJ_dw, .dJ_db = dJ_db};
}

接下来，我们使用这个函数来运行梯度下降算法。

struct linear_model
optimize_gradient_descent(double *xs, double *ys, int m, int num_iterations, double alpha)
{
		struct linear_model model = {0.0, 0.0};
		for (int i = 0; i < num_iterations; i++) {
				struct gradient g = calculate_gradient(model, xs, ys, m);
				model.w -= alpha * g.dJ_dw;
				model.b -= alpha * g.dJ_db;
		}
		return model;
}

num_iterations 和 alpha 的值需要通过实验调整。alpha 是学习率。如果它太低，算法将需要更多的步骤（和时间）才能到达误差谷底。如果它太高，算法将无法收敛。这就像在误差山上，谷底有半英里宽，而你每次只能朝一个方向移动一英里。你可能无法到达底部。

让我们尝试 num_iterations = 1e8 和 alpha = 1e-7

梯度下降优化模型: {w: 0.451677, b: 124.026882}
误差: 85341.496159

不错！通过这种方法，我们得到了更低的误差。但更重要的是，它没有疯狂的大O时间复杂度。对于 $n$ 次迭代和 $d$ 个参数，它的时间复杂度是 $O (n \cdot d)$ 。

这就是梯度下降——它是让机器能够自主学习的基础算法。它告诉程序如何调整其内部模型以更好地拟合预期结果。

结论与下一步

正如你所见，梯度下降法相当合理，至少在我们拥有如此简单的模型时是这样。在接下来的部分中，事情会变得稍微复杂一些，但仍然有望掌控。我们将探讨多元线性回归，即影响输出值的变量不止一个，例如卧室数量、地块面积、与城市的距离等。

如果文章中有任何不清楚的地方，请在下方留言，我会尽力澄清。如果你有任何建议，也请告诉我！感谢阅读。

前往第二部分

✦ No LLMs were used in the ideation, research, writing, or editing of this article.