cs_notes

1. Introduction, Optimization Problems (MIT 6.0002 Intro to Computational Thinking and Data Science)

这个视频介绍了优化问题。优化问题是指寻找使目标函数取得极值的解决方案。目标函数通常取决于一组决策变量。

优化问题包括最大化问题和最小化问题。最大化问题是找出使目标函数取得最大值的决策变量组合。最小化问题则是找出使目标函数取得最小值的决策变量组合。

优化问题在科学、工程和商业中的应用很广泛。例如计算机程序优化、生产计划、电路设计等都可以表述为优化问题。

解决优化问题需要考虑目标函数和决策变量的关系,找出目标函数极值点。通常使用计算机进行求解。求解方法包括穷举搜索、梯度下降法等。

优化问题的求解过程中,决策变量可能受限制条件的约束。约束条件分为等式约束和不等式约束。满足所有约束的决策变量组合才是问题的可行解。

优化问题求解的最终目的是找到使目标函数取得极值的可行解,也就是优化问题的解答。

2. Optimization Problems

优化问题是指寻找一个目标函数所取值最大或者最小的问题。目标函数取决于一组决策变量。

优化问题可以分为最大化问题和最小化问题两种:

• 最大化问题(maximization problem):目标是找到一组决策变量值,使目标函数取得最大值。

• 最小化问题(minimization problem):目标是找到一组决策变量值,使目标函数取得最小值。

优化问题广泛应用于科学、工程和商业等领域。例如:

• 计算机程序优化:寻找让程序运行最快或占用内存最小的变量设置;

• 生产计划:寻找生产数量和安排可以最大限度地满足需求并缩小成本的计划;

• 电路设计:寻找电路性能最好并满足尺寸和功耗限制的设计方案。

求解优化问题需要考虑目标函数与决策变量之间的关系,找到目标函数值的极值点。通常使用计算机和算法求解,如穷举搜索法和梯度下降法。

在实际问题中,决策变量可能受限于一定的约束条件,如等式约束和不等式约束。只有决策变量组合满足所有约束条件,才是问题的可行解。优化问题的最终 goal 是找到一个使目标函数取得极值的可行解。

3. Graph-theoretic Models

图论模型可以用来描述许多优化问题。

图通常由顶点和边组成。在优化问题中:

• 顶点可以表示任务、城市或决策变量等对象;

• 边代表对象间的关系或cost,如任务之间的依赖关系、城市间的距离或变量取值之间的成本;

• 权值可以赋予每条边,代表关系的数量级,如任务间依赖时间、城市间路程或变量取值之间的费用成本等。

常见的图论模型包括:

• shortest path问题:找到一条从源点到汇点总权值最小的路径;

• minimum spanning tree问题:连通所有顶点但总权值最小的树状结构;

• max-flow问题:从源点到汇点的最大流量;

• matching问题:给顶点匹配对象的最优方案。

这些图论模型可以用于运筹问题求解,如作业安排、城市规划或网络流设计等。利用图的结构化特征也常常可以简化问题求解的难度。

4. Stochastic Thinking

许多优化问题中,决策变量的值或目标函数结果会受到随机因素的影响,我们称这些问题为随机优化问题。

随机优化问题需要考虑不确定性,常用的方法包括:

• 概率模型:使用概率分布描述不确定参数,比如客户需求量服从正态分布;

• 期望值:将随机目标函数的期望取最大或最小,转化为确定问题;

• 敏感性分析:考察不同参数走势下问题求解的变化范围;

• 蒙特卡洛法:通过大量随机模拟得到近似解;

• 动态规划:考虑不同阶段决策及其影响,求最优决策树;

• 待定模型:先求解决策树枝的期望收益最大化问题。

随机优化问题于是也可以看作是相对优化问题的一个概括,其中包含有确定性和不确定性因素的影响。正确处理随机因素对问题求解至关重要。

5. Random Walks

随机游走是一个简单并广泛使用的随机过程。它可以用于描述和模拟许多不同类型的随机优化问题。

随机游走定义为:一个对象(通常简称为“行者”)在一个 discreet 状态空间中的位置,在每一个时间步中有基于其当前位置的概率转移到相邻的位置。

简单随机游走的基本假设包括:

• 行者在离散的状态空间上移动,如整数坐标或有限图结构;

• 每个时间步,行者选择每个相邻状态的概率都相同;

• 行者的选择仅依赖于当前状态,与历史记录无关;

• 随时间的行为趋于稳定,形成均匀分布。

随机游走在许多应用中都有用处,比如模拟分子的Brownian motion,计算PageRank算法,描述病毒在网络中的传播等。

通过改变基本假设,也可以建立各种有趣的随机游走变体来模拟更复杂的随机优化问题。

6. Monte Carlo Simulation

蒙特卡洛模拟是一个通过随机采样来解决某些问题的计算技术。它广泛应用于优化问题的随机求解。

蒙特卡洛模拟的基本思想是:

• 根据问题条件设置状态空间和概率分布;

• 随机重复抽样状态,迭代计算各状态下目标函数值;

• 随着抽样次数的增加,目标函数的期望值会趋于稳定。

具体应用包括:

• 计算多重积分,如价格模型中的期权定价问题;

• 优化问题的近似求解,如实时资源调度、运筹计划问题;

• 绘制复杂系统的性能曲线,如计算机网络的拥塞情况;

• 物理系统的可靠性分析,比如核反应堆的安全性研究等。

蒙特卡洛模拟的优点是数学形式没有限制,可以用于任何概率空间。其结果虽不确定但随抽样次数增加逼近真实分布。

7. Confidence Intervals

置信区间是描述抽样统计量分布情况的一个统计概念。它可用于分析蒙特卡洛模拟的结果。

置信区间的定义为:给定一个置信水平(如95%),该区间统计量的真实值落入该区间的概率便等于该置信水平。

例如当通过蒙特卡洛模拟估算期望值为μ,若其95%置信区间为[a, b],则μ的真实值落在a和b之间的概率为95%。

计算置信区间的常用方法包括:

• 正太分布逼近:当样本量大时,平均值的分布接近正太分布。根据标准误来计算置信区间;

• 百分比法则:直接使用已有样本的百分比来确定下限和上限;

• 重复抽样法:重复模拟很多次,记录每组样本的统计量,确定界限范围的观测值。

正确理解模拟结果的置信区间,可以反应样本数量对精度的影响,并给出数值结果的可信程度。这对分析随机优化问题十分重要。

8. Sampling and Standard Error

抽样和标准误是分析模拟结果的重要概念。

• 抽样:从总体中随机选取一小部分样本,对总体的某些统计量进行估计。

• 标准误:抽样采用不同样本进行估计的结果会有差异,这个差异程度可以通过标准误来衡量。

标准误指的是采用不同样本计算的统计量的标准差。它反映了估计值的随机误差大小。

标准误与样本量成反比。样本量越大:

1. 各样本计算出来的统计量分布将更紧密地集中在总体真实值周围;

2. 标准误将越小,估计值的准确性就越高。

在评估蒙特卡洛模拟结果时,标准误可以指出:

• 采样数量是否足以;

• 不同模拟间目标函数结果的可靠程度;

• 是否需要增加采样来提高估计值的准确性。

正确理解标准误对分析随机性问题和求解是否收敛都很重要。

9. Understanding Experimental Data

理解实验数据对优化问题的求解很重要。主要包括:

• 数据采集:如何设计实验、选择随机样本等都会影响数据质量;

• 数据描述:利用统计方法总结数据特征,如均值、中位数、标准差等;

• 搜索规律:采用可视化和机器学习算法寻找数据内在关系;

• 噪声识别:分辨哪些数据是噪声,哪些反映规律;噪声如果过多会影响学习;

• 参数调优:根据数据调整模型参数,如神经网络结构、核函数选择等;

• 验证效果:利用测试集验证模型效果,避免过拟合问题;

• 收集新数据:在解决初步问题后,会产生新的疑问,需要额外的数据;

• 应用转化:将学习到的规律应用到实际问题中,如预测新情况。

数据驱动的方法,需要深入理解数据背后的物理意义,把控变量和参数关系,才能有效解决优化问题。

10. Understanding Experimental Data (cont.)

理解实验数据对优化问题求解至关重要。

除数据描述和模型学习外,还需要关注:

• 循环学习:在初步学习后,回到实验阶段收集新数据对模型进行修正;

• 解释能力:优良模型不仅准确,还能解释背后的因果关系;

• 偏差-变差权衡:高变差模型过于灵活可能带来过拟合;低变差模型过于简单无法表达真实规律;

• 实用性:学习结果是否能很好地应用于实际问题,如预测、决策支持等;

• 不确定度考量:数据是否完整反映问题,是否存在未知变量;学习结果的稳定性如何;

• 基准测试:与其他方法比较,评价所建模效果和经济效益;

• 动态更新:随时间更改的问题需不断更新数据集与模型;

• 新见解:数据分析是否产生新的理解角度和优化思路。

全面高质量的数据是优化问题重要一环,深入研究数据尤其重要。

11. Introduction to Machine Learning

机器学习是一个数据驱动的方法,可以应用于解决优化问题。

机器学习的基本思想是:

• 利用样本数据来建立模型来描述关系与规律;

• 模型通过学习样本来自动进行建模,这种「自行学习」的功能区别于 traditional 算法;

• 在没有明确的编程的情况下,可以实现自动化建模。

常见机器学习方法包括:

• 监督学习:学习带标签的数据比如分类与回归问题;

• 无监督学习:寻找数据内在模式比如聚类;

• 强化学习:在和环境交互中学习行为策略。

机器学习的优点是:

• 从大量样本中自动学习复杂关系;

• 在线更新模型适应新数据;

• 处理高维、非线性问题;

• 解决传统算法难以学习的问题。

机器学习逐步成为解决优化问题重要技术之一。

12. Clustering

聚类是一种无监督机器学习技术。它可以用来识别结构和寻找数据中的模式。

聚类的目的是:

• 将数据样本分为多个互斥的组(集群),同组元素间相似度高,不同组间相似度低;

• 帮助理解数据的内在分布,压缩信息,提高计算效率。

常用的聚类算法有:

• K-Means:选择K个质心,反复计算样本到最近质心的距离,直到质心位置确定;

• 平均连结:计算样本间距离产生连接图,将强连接组合为一个簇;

• 层次聚类:按距离近邻性产生样本间的层次结构树;

• 密度聚类:基于样本点间距离的核函数估计密度,将密度较高区域聚合。

聚类可用于:

• 市场细分;
• 数据库里异常值的检测;
• 语料分类。

通过识别数据模式,有助于理解规律并优化相关问题。

13. Classification

分类是监督学习的一个重要任务。它通过学习真实样本的类别标记,构建一个分类模型或分类器,用以预测新样本的类别。

常见分类算法包括:

• 决策树算法:通过 jerk 分裂变量选择生成树状结构;

• 贝叶斯分类算法:基于概率论给分类决策提供理论支持;

• 神经网络分类算法:模拟人脑神经网络的结构进行预测;

• Logistic回归:通过对数函数建立预测类别的数学模型;

• SVM(支持向量机):将非线性间隔问题转化为线性间隔问题求解。

分类在优化问题中的应用包括:

• 客户分群分类;

• 应急响应分类预测;

• 生产过程质量异常检测等。

通过有监督学习建立分类器,能有效识别样本模式,为优化提供建议。分类算法选择需视问题性质而定。

14. Classification and Statistical Sins

分类算法学习过程中需要避免的一些统计失误包括:

过拟合:模型过于复杂,学习到训练集的随机噪声,而丧失新的样本的预测能力。

解决方法为增加正则项进行惩罚和特征选择简化模型。

数据泄漏:测试集信息走入模型的训练过程中。

解决方法为严格区分训练集和测试集,采用交叉验证的方法。

多重分类:一个样本可能属于多个类别的情况。

解决方法为使用概率模型进行软分类,或使用重叠度较低的新特征。

数据偏差:训练集不均衡或缺失关键特征。

解决方法为采样平衡不同类样本,或者采集新的有效特征进行 augument。

仍需要注意分类结果不等同于实际原因或机制。模型能提供参考支援,但决不等同于真相。全面深入理解数据至关重要。

15. Statistical Sins and Wrap Up

机器学习过程中容易发生的一些统计失误包括:

过拟合:模型过于复杂,学习到训练集的随机噪声,丧失预测能力。解决方法为增加正则化项或者特征选择简化模型。

数据泄漏:测试集信息进入训练集的训练过程中。解决方法为严格区分训练集与测试集,采用交叉验证方法。

多重分类:一个样本可能同时属于多个类别。解决方法为使用概率模型进行软分类,或者采用特征选择降低相关性。

数据偏差:训练集分布与真实数据分布不匹配,如 samples 不平衡或缺少关键特征。解决方法为采样均衡不同类样本,或采集新特征增强训练集。

样本规模有限:结果可能仅适用于特定数据集。需要测试新数据的泛化能力。

在应用机器学习解决优化问题时,需要注意避免统计失误,了解学习结果的可靠性与限制。同时,优化问题复杂,需综合多个方法与细致数据。机器学习提供一种有效路径,但不等同于成功解决。