他當初剛寫第一篇論文的時候，就擬好了這個題目，只是由于數學基礎不夠，一直停留在構思階段。
這兩天他利用碎片時間，稍微補了補高數知識，這才真正動筆。
江寒將近期一些想法整理了一下，羅列了個大綱出來。
很多機器學習分類算法，都要求假設數據線性可分，“感知機”也不例外。
如果數據不是線性可分的，就必須采用一些特殊的方法，把數據非線性地投射到更高的維度上。
在高維空間里，數據更有可能變成線性可分的，這就是所謂的Cover定理。
對于感知機來說，處理線性不可分的問題，有個最簡單的解決辦法，那就是把單層感知機拓展為多層感知機。
多層感知機的關鍵，在于如何訓練各層之間的連接權值。
一種常用的辦法是只訓練某兩層間的連接權值，而將其它連接權值進行固定。
可以從數學上證明，對于所有非線性可分的樣本集，這種方法都是收斂的。
也可以采用BP技術，也就是另一個世界里，大名鼎鼎的“反向傳播神經網絡”。
當然，這個世界里，“感知機”都還沒正式登場，說這些還有點早。
至于BP技術什么時候問世，基本上是江寒自己說了算……
此外，還可以將數據帶到核空間，再進行分類。
在另一個世界里，有很多著名的算法，例如支持向量機（SVM）、徑向基神經網絡（RBFNN）等等，都采用了所謂的“核方法”。
核方法的核心，是核函數。
工業生產中，常用的核函數有線形核、多項式核、高斯核等等。
所謂核空間，百度百科上說：“核型空間是一類局部凸空間。”
具體來說：如果對零元的任何均衡凸鄰域V，存在另一零元的均衡凸鄰域U?V，使得典型映射T：XV→XU是核映射，則局部凸空間X稱為核型空間。
這里，XU是商空間(X，PU(·))/{x|PU(x)=0}，而XV是商空間(X，PV(·))/{x|PV(x)=0}的完備化空間，PU(·)及PV(·)是由U和V各自產生的閔可夫斯基泛函。
嗯，江寒剛開始看到這個的時候，還真有點懵逼。
所以，再加強一點數學素養，還是很有必要的說……
當然，就算不懂上面的數學表達，一樣可以理解核函數的功能。
核函數主要做的事情，就是將樣本映射到更高維的空間。
但是，這樣做雖然能使樣本變得可分，但卻會造成維數過高，使得計算量急遽增大。
這就是“高維NP難”問題。
所謂NP難（NP-hard），是指：非確定性多項式問題的大型實例，不能用精確算法求解，只能尋求有效的近似算法。
而解決的辦法，也有很多……
好吧，先回到一開始的問題：如何判斷數據是線性可分的？
最簡單的情況，比如數據向量是一維、二維或者三維的，只要把圖像畫出來，直觀上就能判斷出來。
但如果數據向量的維度變得很高，又該怎么辦？
答案是檢查凸包（vexhull）是否相交。
所謂凸包，簡單的說，就是一個凸的閉合曲線（曲面），它剛好包住了所有的數據。
以二維的情況為例，如果我們的數據訓練集有兩類：M+和M-。
當我們畫出兩個類的凸包，如果兩者不重疊，那么兩者線性可分，反之則線性不可分。
靠畫出圖形，然后用眼睛來判斷是否線性可分，雖然比直接看數據更加容易了些……
但好像依然沒有解決高維數據的問題？
其實不是這樣的。
判斷兩個凸包是不是有重疊，可以通過判斷兩個凸包（M+和M-）的邊是否相交來實現，而無需把凸包畫出來。
要想高效地找到一組數據的凸包，在計算幾何中有很多現成的算法：
窮舉法、分治法、Jarvis步進法、Graham掃描法、Melkman算法……
江寒在這篇論文中選擇的算法，稱之為快速凸包算法（quickhull）。
第二個問題，如何高效地判斷出，兩個凸包的邊緣是否相交？
也有許多可選的算法，江寒使用了所謂的掃描線算法（sweepline）。