nonlinear transformation

一、non-linear separable data set
可以说，在我们之前所学的知识中，linear binary classification是基石！对于linear binary classification问题，我们可以尝试使用linear regression 、logistic regression、pocket algorithm来处理。而multiclass classification问题，我们可以使用binary classification来处理！假设资料都是linear separable，所以我们的hypothesis都是linear的，现在我们把目光搁到non-linear separable问题上，可能资料可以使用多次曲线来分类！本篇文章就是来解决资料无法使用perceptron进行分类。

在这里，我们推导已知资料可以使用圆作为hypothesis进行分类，则存在另一个空间，在其空间内，存在着一个perceptron可将转化后的资料进行分类。

反之，我们在一个转化后的空间内得到一个perceptron，那么该perceptron对应着一个二次曲线（当w确定后，对应唯一一个二次曲线）。因此利用特征转化后的两个特征空间内的hypothesis是一一对应关系。

在上面的例子中，所假设的二次曲线只包含部分二次项，通过学习所得w也无法代表出所有可能的二次曲线，通用的二次hypothesis set应该是包含常数项、一次项、二次项。
因此，当原始资料不是线性可分的，我们可对其进行特征转化变为线性可分，在线性可分的空间内，利用转化后的资料做linear 分类（linear regression 、logistic regression 、pocket）求出最优的w，当进行预测时，将资料转化到线性可分的空间中，该空间的预测结果作为最终分类结果。
二、如何学习到good quadratic hypothesis？
选择转化函数、演算法，利用演算法求得w和选定的转化函数可以得到non-linear hypothesis

因此，有了nonlinear transform，处理的资料不再局限于linear separable，无论是什么资料，都可以使用一个多次曲线作为boundary进行分类，而这个boundary必然在某个空间内对应着一个线性可分的hypothesis，利用好feature transform，我们就可以linear model 来处理nonlinear 问题！！！

三、如何决定feature transform 阶数？
对于一个Q阶的转化函数所产生的特征维数是O（Q^d），显然当Q越大，维数越大，这会带计算和存储的代价。同时，在学习perceptron时，曾经说过模型*度近似等同于特征维数，因此做过特征转化后，模型复杂度也会增加，结合vc定理，会对E_in和E_out的趋势产生影响！可以说，做特征转化带来最不好的影响就是model complexity的增加！

选择合适的特征转化函数的阶数至关重要！影响最终学习的模型的准确性！

四、如何做才能得到预测模型接近真实模型？
由于转化函数存在递归的关系，因此hypothesis set存在着包含的关系

hypothesis set集合越大，其d_vc越大，E_in越小！这就是我们选择合适模型的关键！

特征函数的阶数从小到大，hypothesis set集合由小到大，若linear model的E_in就很小了，没必要再尝试高阶的hypothesis set！而且此时的d_vc小也可以保证模型复杂度低，此时hypothesis 最接近真实的模型！

总结一下，可以使用特征转化，用linear model处理non linear model，特征转化函数的阶数选择很重要，阶数决定了新的空间中特征的维数，会对模型复杂度产生影响，进而影响到模型预测的可靠性，因此，我们应该从linear model（低阶）开始学习，根据E_in大小来决定是否转向高阶的model！