使用 NVIDIA CUDA 进行大规模机器学习
从垃圾邮件过滤器到电影推荐和人脸识别，如今机器学习算法无处不在，让机器替我们思考。但是，运行这些算法需要强大的计算能力，在大多数情况下需要超级计算机。这就是 500 核 GPU 发挥作用的地方……
引言
您可能听说过安德鲁·恩（Andrew Ng）教授在 2011 年提供的斯坦福大学机器学习在线课程；这是一门很棒的课程，包含许多实际案例。在这门课程中，我意识到 GPU 是解决大规模机器学习问题的完美方案。事实上，互联网上充斥着监督学习和无监督学习的许多例子。作为 GPGPU 和机器学习技术的爱好者，我提出了自己的观点，即在 GPU 上运行海量数据的机器学习算法。
我最近在 2012 年南佛罗里达州代码营（South Florida Code Camp 2012）上展示了该解决方案。这两个主题引起了大家的极大兴趣；因此，我决定在我的博客上分享它。这篇博文中的示例既不是唯一的解决方案，也不是最佳解决方案。希望它有一天能帮助您解决自己的机器学习问题。
机器学习涉及许多概念，但在这篇博文中，我只触及了表面。如果您已经了解 GPGPU 和机器学习，可以直接跳转到此链接处的源代码，下载 Visual Studio 2010 项目并进行尝试。
我还准备了使用 CUBLAS 和多项式回归算法矢量化实现的相同示例，但 CUBLAS 示例需要更深入的解释。因此，我首先发布这个简化实现的示例。如果您对 CUBLAS 实现感兴趣，请告诉我，我可以发送副本给您。
背景
机器学习
如果您已经熟悉机器学习，可以跳过简短的介绍，直接跳转到“大规模机器学习”部分。或者，如果您想了解更多关于机器学习的信息，请关注链接或查看我开头提到的斯坦福课程。
机器学习算法使计算机能够识别复杂模式。它侧重于基于从训练数据中学到的已知属性进行预测。我们可能每天在不知情的情况下使用机器学习算法数十次：每次我们收到图书或电影推荐，或每次我们进行网络搜索时。1959 年，Arthur Samuel 将机器学习描述为：一种让计算机在无需明确编程的情况下学习的学科领域。机器学习自首次引入以来已经有一段时间了，随着大数据时代的兴起，它再次受到关注。
图 1 展示了一些机器学习过程的工作原理。在阶段 1，给定一个数据集，机器学习算法可以识别复杂模式并提出一个模型。在大多数情况下，这个阶段是计算的主要部分。在第二阶段，任何给定数据都可以通过模型进行预测。例如，如果您有一个房屋价格与面积的数据集，您可以让机器从数据集中学习，并让它预测任意给定面积的房屋价格。
它是通过识别定义问题不同特征之间关系的函数来实现的。一个二维线性问题，如房屋价格（房屋面积是特征，房屋价格是标签数据），可以用 f(x) = ax + b 模型来表示。图 2 展示了如何使用一个特征在線性回归问题中预测新的房屋价格。在斯坦福课程中，“假设”一词被用来描述模型。
根据数据集，可以使用更复杂的函数。在图 3 中，您可以看到从二维线性到数百维多项式的复杂性是如何轻松增长的。在垃圾邮件过滤问题中，不同的特征可以是电子邮件中的单词；在人脸识别问题中，特征可以是图像的像素。在房屋价格预测示例中，特征是影响价格的房屋属性，例如面积、房间数、楼层、社区、犯罪率等。
对于不同类型的问题，存在许多机器学习算法。这些算法最常见的两类是 监督学习 和 无监督学习。监督学习用于我们可以为学习算法提供输出值的场景。例如：一些房屋特征对应的房屋价格是输出值，因此房屋价格预测是一个监督学习问题。具有这些输出值的数据称为“标记数据”。另一方面，无监督学习不需要输出值，仅通过特征数据就可以识别模式或隐藏结构。例如：通过聚类社交数据来根据兴趣确定人群分组，不需要定义任何输出值，因此这是一个无监督学习问题。
梯度下降
在监督学习问题中，机器可以通过运行带有不同变量的假设并测试结果是否接近提供的标签（计算误差）来学习模型并得出假设。图 4 显示了训练数据的绘制方式以及误差的计算。可以使用一个名为 梯度下降（图 5）的优化算法来找到最佳假设。在这个简单的二维问题中，算法将针对“a”和“b”的每个不同值运行，并尝试找到最小总误差。
下面的伪代码展示了图 5 中的梯度下降算法的工作原理。
for every a and b loop until converge
errors = 0
for i = 1 to data.length
fx = a * data[i] + b
errors += (fx - labelData[i]) * data[i]
end for
gradient = gradient - learningRate * 1/data.length * errors
end for
大规模机器学习
当复杂性（维度和多项式次数）增加以及/或数据量增加时，机器学习问题会变得计算密集。尤其是在拥有数亿个样本的大数据源上，运行优化算法的时间会急剧增加。这就是我们寻找算法并行化机会的原因。梯度下降算法的误差求和是并行化的完美候选。我们可以将数据分成多个部分，并在这些部分上并行运行梯度下降。在图 6 中，您可以看到数据如何被分成四个部分并输入到四个不同的处理器中。下一步，将结果收集起来以运行算法的其余部分。
显然，这种方法会将机器学习计算速度提高近四倍。但是，如果我们有更多的核心并将数据进一步分割呢？这正是 GPU 发挥作用的地方。借助 GPU，我们可以分两层进行并行化：多个 GPU 以及每个 GPU 中的多个核心。假设配置有 4 个 GPU，每个 GPU 有 512 个核心，我们可以将数据再分割成 512 份。图 7 显示了此配置以及 GPU 核心上的并行化部分。
GPGPU
利用 GPU 为通用科学和工程计算的性能带来巨大提升被称为 GPGPU。NVIDIA 提供了一个名为 CUDA 的并行计算平台和编程模型，用于在 C、C++ 或 Fortran 中开发 GPGPU 软件，这些软件可以在任何 NVIDIA GPU 上运行。NVIDIA CUDA 提供了许多高级 API 和库，如基本线性代数、FFT、图像处理等，让您可以专注于业务逻辑，而不是重写众所周知的算法。
您可以访问我以前的 博客文章，其中我解释了如何使用 NVIDIA CUDAGPUs 进行大规模并行计算。这些示例包括 蒙特卡洛模拟、随机数生成器 和 排序算法。
房屋价格预测示例
在这篇博文中，我将向您展示如何在 NVIDIA CUDA 上实现房屋价格预测。给定一个基于卧室数量、面积和建造年份的房屋价格数据集，可以使机器从该数据集中学习，并为我们提供一个用于未来预测的模型。由于梯度下降算法的误差计算部分高度可并行化，我们可以将其卸载到 GPU。
本示例中的机器学习算法是 多项式回归，它是众所周知的 线性回归 算法的一种形式。在多项式回归中，模型拟合一个高阶多项式函数。在本例中，我们将使用卧室数量、面积、建造年份、卧室数量的平方根、面积的平方根、建造年份的平方根以及卧室数量与面积的乘积。之所以向函数添加四个多项式项，是因为我们数据的性质。正确 拟合曲线 是为我们的机器学习问题构建模型的主要思想。从逻辑上看，房屋价格随着这些特征的增加而不是以线性或指数方式增长，并且它们在某个峰值后不会下降。因此，图形更像是 平方根函数，其中房屋价格相对于任何其他特征的增加而增长得越来越少。
找到正确的多项式项对于机器学习算法的成功至关重要：拥有一个非常复杂、紧密拟合的函数会产生过于具体的模型并导致 过拟合；拥有一个非常简单的函数，如直线，会产生过于通用的模型并导致 欠拟合。因此，我们使用诸如添加 正则化 项等附加方法来更好地拟合您的数据。图 8 显示了包含正则化项 lambda 的梯度下降算法。
应用程序架构
示例应用程序包含一个名为 LR_GPULib 的 C++本机 DLL，用于在 GPU 上实现机器学习，以及一个名为 TestLRApp 的 C# Windows 应用程序，用于用户界面。该 DLL 使用 NVIDIA CUDA 的高级并行算法库 Thrust 实现数据 归一化 和多项式回归。我在之前的博客文章中详细介绍过 Thrust，因此在这篇博文中不再赘述。图 9 展示了应用程序架构以及从加载训练数据到进行预测的程序流程。
该应用程序提供了图 10 所示的用户界面，用于加载数据、训练和使用新数据集进行预测。用户界面还在对话框底部显示了假设，包括所有常数和特征。
实现
DLL 中的 LR_GPU_Functors.cu 文件包含用作 Thrust 方法内核的函数对象。DLL 中的 LR_GPU.cu 文件包含归一化、学习和预测方法。Learn 方法接受训练数据和标签数据，它们是两个浮点数数组中的所有特征和所有价格。Learn 方法首先要做的就是分配内存、添加偏置项并归一化特征。我们添加偏置项的原因是为了简化梯度循环，而归一化特征的原因是数据范围差异太大。例如，面积是四位数，而卧室数量是单个数字。通过归一化特征，我们将它们带入相同的范围，即零到一之间。归一化也在 GPU 上使用 NormalizeFeatures 执行。但归一化需要 均值 和 标准差 (std)，因此首先计算 mean 和 std，并将它们提供给 NormalizeFeaturesByMeanAndStd 方法来计算 mean 归一化。
void NormalizeFeaturesByMeanAndStd(unsigned int trainingDataCount, float * d_trainingData,
thrust::device_vector<float> dv_mean, thrust::device_vector<float> dv_std)
{
//Calculate mean norm: (x - mean) / std
unsigned int featureCount = dv_mean.size();
float * dvp_Mean = thrust::raw_pointer_cast( &dv_mean[0] );
float * dvp_Std = thrust::raw_pointer_cast( &dv_std[0] );
FeatureNormalizationgFunctor featureNormalizationgFunctor(dvp_Mean, dvp_Std, featureCount);
thrust::device_ptr<float> dvp_trainingData(d_trainingData);
thrust::transform(thrust::counting_iterator<int>(0), thrust::counting_iterator<int>
(trainingDataCount * featureCount),
dvp_trainingData, dvp_trainingData, featureNormalizationgFunctor);
}
在 GPU 上运行的归一化代码在 FeatureNormalizationgFunctor 函数对象中实现，该函数对象只是并行计算每个数据元素的 data - mean / std，如下所示。
...
__host__ __device__
float operator()(int tid, float trainingData)
{
int columnIdx = tid % featureCount;
float fnorm = trainingData - meanValue[columnIdx];
if (stdValue[columnIdx] > 0.0)
fnorm /= stdValue[columnIdx];
return fnorm;
}
...
在 Learn 方法中的下一步，梯度下降通过 for(int i = 0; i < gdIterationCount; i++) 循环计算。正如我之前提到的，梯度下降的误差计算部分是并行执行的，但其余部分是顺序计算的。thrust::transform 与 TrainFunctor 一起用于并行计算每个样本的 f(x)-y。f(x) 只是 A*x1 + Bx2 + Cx3 + Dx4 + Ex5 + Fx6 + Gx7 + H 假设，其中 x1 到 x7 是特征（x1=卧室数量，x2=面积，x3=建造年份，x4=卧室数量的平方根，x5=面积的平方根，x6=建造年份的平方根，x7=卧室数量与面积的乘积），而 A 到 H 是梯度下降将要找出常数。这在图 11 的绿色方块中显示。TrainFunctor 代码片段和用法代码片段如下所示。
...
__host__ __device__
float operator()(int tid, float labelData)
{
float h = 0;
for (int f = 0; f < featureCount; f++)
h += hypothesis[f] * trainingData[tid * featureCount + f];
return h - labelData;
}
...
...
thrust::transform(thrust::counting_iterator<int>(0),
thrust::counting_iterator<int>(trainingDataCount),
dv_labelData.begin(), dv_costData.begin(), tf);
...
thrust::transform_reduce 与 TrainFunctor2 一起使用，将特征应用于误差结果并将它们全部加起来。这在下面的代码片段和图 11 的红色方块中显示。Learn 方法的其余部分计算图 11 中蓝色方块标记的梯度下降部分。
float totalCost = thrust::transform_reduce(thrust::counting_iterator<int>(0),
thrust::counting_iterator<int>(trainingDataCount), tf2, 0.0f, thrust::plus<float>());
一旦梯度下降收敛，假设的常数 A 到 H 将通过 result 数组返回到 TestLRApp。
正如您可能猜到的，预测是通过在假设中使用新样本数据和常数来完成的。这通过 LR_GPULib 库中的 Predict 方法完成。如下所示，Predict 方法归一化给定的特征集，并通过 PredictFunctor 借助常数和归一化数据来计算假设。结果是给定特征的预测房屋价格。
...
NormalizeFeaturesByMeanAndStd(testDataCount, pdv_testData, dv_mean, dv_std);
//Predict
PredictFunctor predictFunctor(pdv_testData, pdv_hypothesis, featureCount);
thrust::transform(thrust::counting_iterator(0),
thrust::counting_iterator(testDataCount), dv_result.begin(), predictFunctor);
...
struct PredictFunctor : public thrust::unary_function
{
float * testData;
float * hypothesis;
unsigned int featureCount;
PredictFunctor(float * _testData, float * _hypothesis, unsigned int _featureCount)
: testData(_testData), hypothesis(_hypothesis), featureCount(_featureCount)
{}
__host__ __device__
float operator()(int tid)
{
float sum = 0;
for(int i = 0; i < featureCount; i++)
sum += testData[tid * featureCount + i] * hypothesis[i];
return sum;
}
};
结论
GPGPU、机器学习和大数据是 IT 行业中三个新兴领域。这些领域的内容远不止我在本篇博文中提供的内容。随着我深入研究这些领域，我发现它们多么契合。我希望这个示例能为您提供一些基本想法，以及如何轻松地在机器学习问题中使用 NVIDIA CUDA 的一种视角。与任何其他软件解决方案一样，这个示例并不是在 GPU 上进行房屋价格预测多项式回归的唯一方法。事实上，一个增强功能将是支持多个 GPU 并将数据集分成更多部分。
