基础知识

normalization概要

1.

以基于机器学习来识别Android恶意程序为例，首先我们收集了一批应用程序的数据，例如其申明的权限、使用的api。

这组记录的集合称为一个“数据集”（data set）,其中每条记录是关于一个事件或对象的描述，称为一个“示例”（instance）或“样本”（sample）。反映事件或对象在某方面的表现或性质的事项，例如权限、api，称为“属性”（attribute）或“特征”（feature）；属性上的取值，例如申请了打电话的权限则该项属性为1（二值表示的话），称为“属性值”（attribute value）。属性张成的空间称为“属性空间”(attribute space)、“样本空间”（sample space）或“输入空间”。例如我们把“通话权限”“位置权限”“通讯录权限”作为三个坐标轴，则它们张成一个用于描述应用程序的三维空间，每个应用都可以在这个空间中找到自己的坐标位置。由于空间中的每个点对应一个坐标向量，因此我们也把示例称为一个“特征向量”。

一般地，令$D={x1,x_2,\ldots,x_m}$表示包含$m$个示例的数据集，每个示例由$d$个属性描述，则每个示例$x_i=(x{i1};x{i2};\ldots;x{id})$是$d$维样本空间$\mathcal X$中的一个向量，$xi\in \mathcal X$,其中$x{ij}$是$x_i$在第$j$个属性上的取值，$d$称为样本$x_i$的维数（dimensionality）。

如果希望能学得一个帮助判断是否是恶意程序的模型，就需要建立关于“预测”（prediction）的模型，我们需要获得训练样本的结果信息，例如“恶意程序”，称为“标记”（label）；拥有了标记信息的示例，则称为“样例”（example）。一般的，用$（\mathbf x_i,y_i）$，其中$y_i\in \mathcal Y$是示例$\mathbf x_i$的标记，$\mathcal Y$是所有标记的集合，亦称“标记空间”（label space）或“输出空间”。

若我们预测的是离散值，例如“良性应用”“恶意应用”，此类学习任务称为“分类”（classification）；若想要预测连续值，例如应用的威胁程度0.12、0.95，此类学习任务称为“回归”（regression）。对只涉及两个类别的“二分类”（binary classification）任务，通常称其中一个为“正类”（positive class），另一个为“反类”（negative class）；涉及多个类别时，则称为“多分类”（multi-class classification）任务。一般的，预测任务是希望通过对训练集${(\mathbf x_1,y_1),(\mathbf x_2,y_2),\ldots,(\mathbf x_m,y_m)}$进行学习，建立一个从输入空间$\mathcal X$到输出空间$\mathcal Y$的映射$f:\mathcal X \mapsto \mathcal Y$。 对于二分类任务，通常令$\mathcal Y={-1,+1}$或${0,1}$；对多分类任务，$|\mathcal Y|>2$；对回归任务，$\mathcal Y=\mathbb R$，$\mathbb R$为实数集。

我们还可以对应用程序做“聚类”（clustering）,即将训练集中的应用程序分成若干组，每组称为一个"簇"（cluster）；这些自动形成的簇可能对应一些潜在的概念划分，譬如应用自动分为“通讯类”“娱乐类”。这样的学习过程有助于我们了解数据内在的规律，能为更深入地分析数据建立基础，需说明的是，在聚类学习中，类似“通讯类”“娱乐类”这样的概念我们预先并不知道，而且学习过程中使用的训练样本通常不具标记信息。

在高维情形下易出现数据样本稀疏、距离计算困难等问题，被称为“维数灾难”（curse of dimensionality）。缓解维数灾难的一个重要途径就是降维，亦称“维数约简”，即通过某种数学变换将原始高维属性空间转变为一个低维“子空间”（subspace），在这个子空间中样本密度大幅提高，距离计算也变得更为容易。在很多时候，人们观测或收集到的数据样本虽是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维“嵌入”（embedding）（譬如前面提到的区分恶意应用和良性应用，有些权限或api特征并不起作用）。

（3）典型方法

监督：

  1. 决策树（decision tree）是一类常见的机器学习方法。顾名思义，决策树基于树结构来进行决策。一般的，一棵决策树包含一个根节点、若干个内部节点和若干个叶节点；叶节点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。
  2. 神经网络（neural networks）“神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能模拟生物神经系统对真实世界物体所作出的交互反应”。
  3. 支持向量机，分类学习最基本的想法就是基于训练集$\mathcal D$在样本空间中找到一个划分超平面，将不同类别的样本分开。而我们要找的划分超平面要是所产生的分类结果最鲁棒的，对未见示例泛化能力自强的。

无监督：

  1. k均值算法（k-means），把相似的观测向量分到一组，从而发现数据中的聚类结构。
  2. 流形学习（manifold learning）是一类借鉴了拓扑流形概念的降维方法。

  3. 主成分分析法（Principal Component Analysis，简称PCA）是最常用的一种降维方法。即对于正交属性空间中的样本点，用一个超平面对所有的样本进行恰当表达。这样的超平面具有两个性质：

  4. 最近重构性：样本点到这个超平面的距离都足够近；

  5. 最大可分性：样本点在这个超平面上的投影尽可能分开。

3.

考虑正则化问题 min⁡f∈H′λ2∣∣f∣∣H′2+12∑i=1N∣∣f(xj)−yj∣∣22 \min_{f\in H'} \frac {\lambda}{2}||f||_{H'}^2+\frac 12 \sum_{i=1}^{N}||f(\mathbf x_j)-y_j||_2^2 定义正定核$K$诱导上的$H_k$的内积： f(x)=Kα∣∣f∣∣H′2=∑i=1n∑j=1nαiαjK(xi,xj)=αTKα \begin{aligned} f(x)=K\alpha\\ ||f||_{H'}^2=\sum_{i=1}^n\sum_{j=1}^n \alpha_i \alpha_j K(\mathbf x_i,\mathbf x_j)=\alpha ^T K \alpha \end{aligned} 原问题变为： α∗=argminα∈RD(y−Kα)T(y−Kα)+λcTKc \alpha^*=argmin_{\alpha \in \mathbb R^D}(y-K\alpha)^T(y-K\alpha)+\lambda c^TKc

采用的是再生核Hilbert空间中L2范数定义的正则化项，由表现定理，其解的形式： f(x)=∑i=1nαiK(x,xi) f(x)=\sum_{i=1}^n \alpha_i K(x,x_i) 求梯度，令之为$0$，可以获得 α=(K+λ⋅In)−1⋅yf=K⋅α=K⋅(K+λ⋅In)−1⋅y \begin{aligned} \alpha =(\mathbf K+\lambda \cdot I_n)^{-1}\cdot y\\ f=K \cdot \alpha=K \cdot(K+\lambda \cdot I_n)^{-1}\cdot y \end{aligned}

results matching ""

    No results matching ""