名词解释

• 机器学习：代表某现象的样本数据构建算法。或者解决实际问题的流程，数据收集、统计建模、利用模型解决实际问题。数据来源：自然产生、人工生成、其他算法输出。
• 监督学习：特征和标签对的表示方法（标签除了实数还能是向量、矩阵、树、图）输入是样本信息，输出是标签信息。
• 半监督学习：无标签数远超过有标签数，获得的信息更多。
• 非监督学习：输入无标签的数据，变成其他数据，比如聚类、降维、异常值检测（outlier detection）
• 强化学习：输入某种状态的特征向量，输出当前状态下可执行的最优动作（策略）。解决按顺序做决策，并且具有长期目标的事情（电子游戏、资源管理、物流管理、机器人控制）。
• 回归与分类：回归问题也是对无标签样本进行预测，只不过，不是分类问题里的标签。而是给出一个实数值(目标)如房价预测。
• 深度学习：浅层学习是算法直接从训练样本特征中学习模型的参数。大多数监督算法都这样。如果输入和输出之前有很多层，模型参数从网络前一层学得，而不是从训练样本的特征中直接学得，称为深度学习也就是深度神经网络。

模型失误的原因：Probably Approximately Correct（PAC）该理论主要分析算法在什么情况下生成一个近似正确的模型。

线性回归（linear regression）

线性模型与SVM模型相比，没有sign运算（正数返回1负数-1），主要区别在于SVM的超平面是决策平面，与两类样本越远越好，线性回归则希望越近越好。

类比一维的情况 $y=wx+b$ , $y_i$ 是一个实数标签，$\mathbf{x}_i$是第i个样本的多维特征向量。通过样本的训练，找到最优的参数$\mathbf{w}^*$ 和 $b^*$. （粗体的是向量）

基于应该和所有样本靠近的观点，这里的损失函数是方差损失（squared error loss）： $$ (f_{w,b}(\mathbf{x}_i)-y_i)^2 $$ 一个模型的平均损失或者说经验风险（empirical risk）是将其应用于所有样本后的累积总损失平均数。这个需要被最小化（有的情况最大化）的表达式一般叫做目标函数（成本函数（cost function））：$\frac{1}{N}\sum\limits_{i=1…N}(f_{w,b}(\mathbf{x}_i)-y_i)^2$

比如通过硬件计数器的采样数据作为特征向量，建模内存子系统性能，字典里k是某个pcm输出的值，v是采样值，coeff_dict线性回归中获得的权重，系统性能accu_avg，训练时的实数标签 $y_i$ 是吞吐量，用DLRM训练的。获得一段时间的采样平均值，作为这一轮的性能。

coeff_dict = {
    'norm_ipc': 99.55281,
    'L1.miss.lats': -0.04686,
    'DDR.read.lats': -0.48751,
}
for k, v in self.arr.items():
    mean = sum(v) / len(v)
    accu_avg += coeff_dict[k] * mean
    self.arr[k] = []
    print(k, mean)

调整交错分配内存的比例：如果当前阶段的内存子系统性能比上一阶段有所提高，认为其先前的决定是正确的，即增加（或减少）分配给 CXL 内存的页面百分比。然后，它将继续以固定幅度递增（或递减）该百分比。否则，它将开始将步长反转一半，从而减少（或增加）百分比，并在未来一段时间内评估决策，以确定分配给 CXL 内存的页面的有利百分比。请注意，步长变量的绝对值有最小限制，以防止其接近零。

'''
dynamic_state当前的性能
static_state之前的性能
prev_step上次调整的步长
bot_ratio上次交错分配的占比
'''
MIN_STEP = 1
IL_TOP_RESET = 10

def algo(dynamic_state, static_state, prev_step, bot_ratio):
    diff = dynamic_state - static_state
    abs_diff = abs(diff)

    curr_step = prev_step
    if diff > 0: # gets better
        curr_step = prev_step
    else: # gets worse
        curr_step = -prev_step / 2 # apply reversed half step

    # ================================== bound step
    if curr_step < MIN_STEP and curr_step > -MIN_STEP:
        if curr_step < 0:
            curr_step = -MIN_STEP
        else:
            curr_step = MIN_STEP
    curr_step = int(curr_step)

    ## ================================== bound ratio
    bot_ratio += curr_step 
    if bot_ratio <= 1: # cap at ddr:cxl = 10:1
        bot_ratio = 1
    elif bot_ratio >= (IL_BOT_MAX):
        bot_ratio = IL_BOT_MAX

    # ================================== set
    bot_ratio = int(bot_ratio)
    set_ratio(IL_TOP_RESET, bot_ratio)

    return curr_step, bot_ratio

支持向量机SVM（Support Vector Machine）

SVM将特征向量看作高维空间里的一个点，比如用汉字表（3500常用字）表示收集的邮件，邮件中有的字置为1，没有的置为0，这个邮件有3500个特征。SVM会用一个3499维的超平面，决策是否是垃圾邮件。这个算法表示为 $f(\mathbf{x})=sign(y=\mathbf{wx}+b)$

找最优的参数$\mathbf{w}^*$ 和 $b^*$ 的方式是sign隐含的约束：

$$ \left\{ \begin{aligned} &\mathbf{wx}_i-b \ge 1 \\ &\mathbf{wx}_i-b \leqslant -1 \\ \end{aligned} \right. $$

同时希望距离越大越好还要同时最小化 $\mathbf{w}$ 的欧几里得范数 $||\mathbf{w}||$，为了方便用二次规划（quadratic programming）求解，实际可以算 $min\frac{1}{2}{||\mathbf{w}||}^2$

如果数据无法在原空间被超平面分割，那么将数据变换到另一个高维空间，这个方法称为核技巧（kernel trick），这样就有可能在新空间被线性分割，他的实现是使用核函数。这样原空间就会有一个平滑或者弯曲的决策边界了。

决策树（decision tree）

一个用于决策的非循环图，每个分支节点上，一个特征 $j$ 会被测试，然后选择一个分支。也就是可以用叶节点的标签决定一个样本标签。决策树的构建有很多方法ID3采用平均对数似然（log-likelihood），每次划分的效果使用熵（entropy）来衡量。

每次划分是局部的，所以ID3无法获得最优解，回溯（backtracking）可以搜索最优解。树构建完后，除去对降低误差影响不大的分支用其叶节点取代称为剪枝（pruning）。

算法的组成部分为：
-该算法的损失函数
-基于损失函数的优化标准（比如代价函数，常见的梯度下降（专门优化可导的损失函数））
-利用训练数据求解优化标准程序
有的算法的设计有一个明确的优化标准，而其他算法则没有一个明确的全局优化标准比如决策树和K邻近

特征工程

当算法只接受数值向量时，可以用1，2，3，4之类的表示类型，如体测评级{优，良，合格，不合格}，这里变量值递增和做决策是有关系的。这些信息也会被算法学习。如果没有顺序关系的类型表示，应该采用独热编码，虽然这会增加数据维度。

分箱（binning）或者分桶（bucketing）将连续特征转化为多个二元特征。这种转化通常按照值域来决定，转化后特征变为了箱或者桶。这样的好处是精心设计的分箱给算法一个“暗示”，具体值域不重要，只要在这个值域内就行。

数据归一化（normalization）虽然并不是硬性要求，但是实践中发现可以使学习速度加快，这和求偏导有关。一般转换后的区间是[-1,1]或[0,1]。

标准化（standardization）又称z标准化（z-score normalization）讲数据特征值调节到符合μ=0和σ=1的标准正态分布中。

使用归一化或者标准化的经验：

• 非监督算法标准化比归一化受益；
• 如果本身分布近似标准正态分布，标准化首选；
• 特征的值特别大或者特别小，标准化首选（且归一化不适合）；
• 除此之外都可以先实验一下归一化。
  重新调整特征对大多算法都有利，开源库里的算法本身可能已经包涵这一步了，具体看库提供的文档吧。

处理特征值缺失

数据集中某些样本的某个特征值可能因为各种原因遗漏了。除了移除这些样本以外，有的ML算法可以处理缺失的特征值（具体得根据情况查查），还有一些数据补全技术可以用到。

1. 将缺失的特征值替换为数据集中该特征的平均值。
2. 将缺失的值替换为正常值域之外的值，这样做为了让算法自己把它筛选掉。
3. 替换为正常值域中间值，这不会严重影响预测结果。
4. 缺失值看做回归问题的目标变量。也就是说其他所有剩下的特征是特征向量，这样用完整的数据预测缺失的数据。
5. 数据集很大，缺失特征是少数时。加一个称为二元指示器特征，由这个新的特征表示某个特征是否缺失。如果缺失要用0或者任意值代替。
   同样，哪种补全方法更好只有多试几次。

处理不平衡数据集

过抽样法，通过重复少数样本增加样本重要性。欠抽样法，训练集中多数类别的样本随机删除。通过合成样本进行过抽样的是合成少数类别过抽样法synthetic minority oversampling technique SMOTE和自适应合成抽样法adaptive synthetic sampling method ADASYN. 决策树，随机森林和梯度提升在存在不平衡数据情况下仍表现较好。

算法选择

数据集如果不能完全载入内存中需要考虑增量学习算法（incremental learning algorithm）逐步增加数据提高模型表现。选择算法时还要考虑特征数与样本数，考虑数据是否线性可分割，是否可以用线性模型建模再去考虑深度神经网络或集成算法。考虑训练时间。考虑预测时间，比较深或者循环的神经网络相对较慢的。（有意思的是scikit-learn有一个机器学习算法选择图可以参考。）

样本划分

如果数据集含上百万个样本，那么一般95％用于训练模型，2.5％用于验证和测试。根据过去经验，如果量比较少就70％训练，15％验证和测试。交叉验证训练样本有限，倾向于用更多的数据来训练时，分为训练集和测试集就够了，然后在训练集使用交叉验证模拟验证集。异常值检测主要为了找出数据集中与大多数其他样本看起来不一样的异常值。可以考虑自编码器和单类别分类学习。

欠拟合和过拟合

欠拟合的影响因素主要是：1.复杂的数据配上简单的模型。2.特征信息量不足。
过拟合的影响因素主要是：1.模型太复杂了，数据没那么复杂。2.特征值太多而训练样本太少。

正则化

避免模型过于复杂的一个方法是正则化，L1和L2正则化都是在目标函数中加入一个惩罚项，令该项在模型约复杂时越大。对于线性回归，正则化后的目标函数是：

${C|\mathbf{w}|+\frac{1}{N}\sum\limits_{i=1…N}(f_{w,b}(\mathbf{x}_i)-y_i)^2}$ 其中，$|\mathbf{w}|=\sum\limits_{j=1…D}|w^{(j)}|$，$C$为超参数

弹性网络正则化（elastic net regularization）结合了L1与L2，L2的对应优化有岭回归正则化（ridge regularization），L1对应套索回归（lasso）。两种常用于神经网络的正则化方法丢弃（dropout）和分批标准化（batch normalization）。有正则化效果的非数学的方法数据增强法（data augmentation）和早停法（early stopping）.

神经网络和深度学习

个人比较熟悉的是做图像处理的卷积，不过深度学习一些模型的发展大致如下。（1）普通神经网络（vanilla neural network，多层感知机multilayer perceptron），每一个元都是一个回归函数，一层有多个元，可以有多层。（2）卷积（3）循环神经网络（recurrent neural network，RNN）的延伸有双向循环神经网络（bi-directional）、含注意力的循环神经网络、序列到序列循环神经网络（sequence-to-sequence）、递归神经网络。

跳过（略过）部分

模型效果评估、超参数调试这些根据具体模型需要可以再仔细去实验对比选择。