题目：基于随机投影的学习问题

基于数据的机器学习是计算机科学、统计学、数学等学科中重要的研究领域之一。学习理论研究基于样本的学习算法的收敛性误差估计，探索数据在低维可视空间中的最优表达及其在模式识别等领域的应用。学习理论为机器学习与应用提供数学基础，具有重要理论价值和广泛应用前景。本论文讨论的主要问题是：基于随机投影数据，设计可学习性算法，分析了学习算法的相容性并给出了算法的学习率。首先，论文讨论了随机投影著名的Johnson-Lindenstrauss（JL）引理。我们建立了核形式的JL 引理，包括基于广义链的JL 引理。不仅如此，论文还讨论了JL 引理和压缩传感理论的RIP 条件的联系。此外，我们还给出了无限维空间上随机投影的JL 引理的核形式。其次，在凸损失情形下，讨论了基于随机投影的Tikhonov 正则化学习算法，建立了学习算法的收敛速率。为此，利用投影空间的学习目标函数的核函数表示定理，用其表示系数构造原始样本集空间的学习目标函数表示。这个算法直接在投影空间中进行，不需要再回到原始空间中，从而大大的降低了计算的复杂性。进而，利用表示系数及核函数的性质，估计过量误差的界，从而得到学习算法的相容性结果。此外，通过选择合适的投影数据的维数，获得最小二乘回归算法和支持向量机算法的学习率。到目前为止，给出基于随机投影学习算法的相容性和学习率尚属首次。第三，研究了函数型正则化回归算法的收敛性速率，利用Rademacher 平均的方法界定了过量误差的界。我们建立了与样本维数无关的界，并且建立了函数型数据的回归算法的快速学习率。在实际应用研究中，使用任意一种技术将实际数据纳入模型之前，要对函数型的数据首先进行降维，这样可有效地减少甚至消除维度的影响。随机投影方法，可作为一个有效的降维工具。本文利用JL 型随机投影对函数型数据进行预处理，将观察样本点投影到有限维的空间，得到投影数据集。基于投影数据集的正则化回归算法，我们可以将学习目标函数在投影空间中表示。通过在投影空间得到的表示系数逼近原始空间的学习目标函数的表示系数，达到估计回归预测子和回归函数之间过量误差的目的。本文针对不同的噪声条件，进行了多次仿真实验，实验结果表明该算法是有效的。最后，讨论系数正则化回归算法。假设空间不仅仅依赖于样本点个数，还依赖于样本集。这里，选择惩罚项为系数的ℓ2 范数，使得算法具有选择相关变量组的能力。我们通过在低维空间求解学习目标的系数，实现对高维空间中学习目标系数的逼近。基于此，我们证明了随机投影的系数正则化回归算法的收敛性，并建立了学习算法的误差估计。理论分析和实验表明，依据随机投影空间的数据学习是有效的，算法具有很高推广性能以及较低的计算复杂度。本文将随机投影引入到监督学习算法研究中，将数据降维与回归分类问题有机结合，进行数据自适应处理和分析。我们期望，基于随机投影的学习算法的研究，能为学习理论提供新的研究内容，促进学习理论研究领域的发展。