基于SVM的字符識別研究

張昊杰

（西安市高新第一中學，陜西西安，710075）

0 引言

近年來，隨著科技的日益發展以及電子設備的普及，輸入法的使用頻率越來預高，較新發展的手寫輸入受到一些不會拼音及五筆輸入法的人們的好評，近些年手寫字符識別已經迅速發展成為了一種成熟的輸入法，目前如何從浩瀚的字符庫中方便快捷的確定和篩選用戶所輸入的信息，已經成為迫切需要解決的難題，其核心問題是字符識別。

隨著科技的日益發展，人們輸入的方式早已多樣化，但是由于目前手寫輸入識別準確率不高，識別速度緩慢等問題，人們還是較少的使用手寫輸入。雖然如今已經誕生了很多優秀的字符識別系統，利于基于邏輯回歸的字符識別系統，但是這種識別系統識別率往往太低無法投入到實際的生產生活中。還有字符識別率較高的例如神經網絡模型，但是其計算過程、模型設計、資源的利用上更加復雜，對于簡單的數字識別來講，消耗的時間和計算資源成本過為龐大。

本文討論一種基于SVM的方式解決數字手寫字符的方法。一般的，如果一個線性函數能夠將樣本完全正確的分開，就稱這些數據是線性可分的，否則稱為非線性可分的。線性函數在一維空間里就是一個點，在二維空間里就是一條直線，三維空間里就是一個平面，在一個N的空間中，如果該數據線性可分，則存在一個N–1維的超平面將其分隔開。SVM在解決小樣本數據上相比傳統的模型有明顯較高的正確率，與神經網絡這種精確度更高的模型相比，其計算速度又有明顯優勢。

1 系統介紹

本文所研究的是SVM在字符識別中的應用，SVM(Support Vector Machine)指的是支持向量機，是常見的一種判別方法。在機器學習領域，是一個有監督的學習模型，通常用來進行模式識別、分類以及回歸分析。對于原始的分類問題，由于SVM是一個處理二分類的一個機器，但是本研究的主要研究對象是十個數字，因此，采用的方式是將其一個數字作為一個分類結果，另外9個數字統稱為另外一個分類結果，以此類推，劃分成10個分類情況，找到那個可能完美的將兩類不同樣本點分隔開的超平面。對于所有的訓練樣本，本文的SVM要設計出十個分隔面，然后對于新樣本，要將其用這十個SVM模型做預測，看它復合哪種得概率最高，其求得的值最大，就認為新樣本屬于哪個字符。

本文根據支持向量機的基本原理和要求，推導出最優分隔面的公式，它是一個有不等式約束條件的優化問題，對于該類問題，采用的是將其構造成一個包含KKT條件的拉格朗日式子。本文同時考慮利用高斯核函數解決面臨的問題，采用高斯核函數的優點是可以將數據升維，即可將線性不可分的問題轉化成線性可分的問題。利用SVM中的代價函數可以評判該模型在原始樣本以及新樣本中的表現情況，因為模型可能會出現過擬合的狀態，要采用正則化的方式將模型的復雜度降低，以達到一個最優的擬合狀態。

■1.1 數據集：MNIST

本文要研究的對象是手寫字符，如果在研究開始階段就自己去采集字符集訓練樣本無疑是一件工作量浩大且繁重的任務，因此本文采用的是網上現有的MNIST數據集。數據集來自美國國家標準與技術研究所（NIST），其中有70000個手寫體數字庫，60000個訓練集，10000個測試集，由250個不同人手寫的數字構成。數據采用同一大小的灰度圖像，即28×28=784像素的圖像。

圖1 MNIST數據集

■1.2 SVM數學原理

如圖2所示，將紅藍兩類二維的樣本點的坐標值放在直角坐標系中，可以得到一個點的位置關系分布圖（a），顯然存在一條直線可以將兩類樣本點完美的分隔開，但是這樣的直線是有無數條的。對于SVM來說，這樣的直線有且僅有一條，其名為“超平面”。

圖2 SVM分類

對于此例中出現的情況，如圖2(b)、2(c)所示，分別存在兩條直線A/B將兩類樣本點分隔開。直線A沿水平方向左右移動，且保證正確將兩類樣本點分開的極限是圖2（b）中A線兩邊的虛線位置，兩條虛線之間的距離稱之為分類間隔，分隔線A在這個間隔的正中間位置，明顯圖2(c)中的B線的分類間隔要小于圖2(b)中的A線，SVM就是要找到一個分類間隔最大的分隔線。

支持樣本點：虛線穿過的樣本點 ，即分隔線在保證正確劃分的前提下平移到最極端位置的點，點的坐標稱為支持向量。

下面是推導SVM尋找最優分隔面的計算方式：

假設式（1）為分隔線

改變自變量名，為了向量表示

向量表示

直線外一點到該分隔線的距離d為：

分母為二階范數，向量的長度為每一個樣本點xi加上一個類別的標簽yi。

假設決策面正好處于間隔區域的中軸線上且相應的支持向量對應的樣本點到決策面的距離為d。

公式（11）的幾何意義就是，支持向量樣本點到決策面的距離就是。我們原來的任務是找到一組參數ω， γ使得分類間隔W=2d最大化，根據公式（11）就可以轉變為的最小化問題，也就等效于的最小化問題。我們之所以要在上加上平方和1/2的系數，是為了以后進行最優化的過程對目標函數求導時比較方便，但這絕不影響最優化問題最后的解。

即，我們給出了線性SVM最優化問題的數學描述：

■1.3 拉格朗日函數

得到這個形式以后，就可以很明顯地看出來，它是一個凸優化問題，或者更具體地說，它是一個凸二次優化問題—目標函數是二次的，約束條件是線性的。

為了有效地求解凸優化問題，通常會將它作為原始最優化問題，應用拉格朗日對偶性，通過求解對偶問題得到原始問題的最優解。這樣做的優點有兩點：一是對偶問題往往更容易求解，二是為了更自然的引入核函數，進而推廣到非線性分類問題。

通過給每一個約束條件加上一個Lagrange multiplier，我們可以將它們融入到目標函數里去：

該式子用于解決有等式約束的優化問題。使用的方法就是拉格朗日乘子法，即把等式約束用一個系數與目標函數f(x)寫為一個式子，稱為拉格朗日函數，而系數稱為拉格朗日乘子。而當我們遇上有不等式約束的優化問題我們則會選擇KKT條件 。我們把所有的等式、不等式約束與f(x)寫為一個式子，也叫拉格朗日函數，系數也稱拉格朗日乘子，通過一些條件，可以求出最優值的必要條件，這個條件稱為KKT條件。

對于等式約束，我們通過一個拉格朗日系數a 把等式約束和目標函數組合成為一個式子L(a, x) = f(x) + a＊h_i(x),這里把a和h_i(x)視為向量形式，a是橫向量，h_i(x)為列向量，都是n維向量。然后求取最優值，可以通過對L(a,x)對各個參數求導取零，聯立等式進行求取。即對于具有等式和不等式約束的一般優化問題：

KKT條件給出了判斷x是否為最優解的必要條件，即：

■1.4 高斯核函數

線性支持向量機 (Linear–SVM) 被用于線性可分的數據集的二分類問題，當數據集不是線性可分的時候，需要利用到核函數將數據集映射到高維空間。這樣數據在高維空間中就線性可分。

高斯核函數（Gaussian kernel），也稱徑向基 (RBF)函數，是常用的一種核函數。它可以將有限維數據映射到高維空間，我們來看一下高斯核函數的定義：

上述公式涉及到兩個向量的歐式距離（2范數）計算，而且，高斯核函數是兩個向量歐式距離的單調函數。σ 是帶寬，控制徑向作用范圍，換句話說，σ 控制高斯核函數的局部作用范圍。當x和x′的歐式距離處于某一個區間范圍內的時候，假設固定x′，k(x,x′)k(x,x′)隨x的變化而變化的相當顯著。這里的x′稱之為地標。例如，假設我們的字符圖片只有兩個維度的分量，這里以地標（3，5）的一個二維向量為例，分別以不同的σ值可以得到不同的函數圖像。

圖3 經過核函數處理之后的函數圖像

從圖3可以明顯的看出，σ的作用在于改變圖像的陡峭程度，即從波峰到波谷的變化速率，σ越大表示數值變化得越緩慢，σ越小表示數值變化得越迅速。在坐標值與地標完全重合的時候，原坐標值在經過核函數的變化之后達到最大值1，并隨著坐標值與地標之間的距離變大，計算得到的值逐漸變小直到為0。

在真實的計算過程中，往往是將所有訓練集都設為地標，然后計算一個樣本點與所有地標之間的高斯核函數核函數值的集合作為新的樣本值，這樣新樣本點的維度就被升高到與原始訓練集個數相同的維度，又由于樣本個數往往是遠大于原始樣本點的維度數，這樣樣本點都被升高到了一個較高的維度，再采用解決線性可分的方式去解決這個問題，這樣就可以獲得一個更加完美的分割方案。

■1.5 解決過擬合

對于線性不可分SVM，如果我們強行采用升維讓其絕對分開，就容易導致過擬合的現象，過擬合指的是訓練得到的模型在原始的訓練集中表現很好，但是在測試集中則表現的差強人意，說明模型的泛化能力比較差，對于解決過擬合通常有兩種思路。首先是預防為主，要在模型設計初考慮到這個問題了，一般有兩種方法：

（1）在訓練和建立模型的時候，從相對簡單的模型開始，不要一開始就把特征做的非常多，模型參數非常復雜。

（2）增加樣本，要覆蓋全部的數據類型。數據經過清洗之后再進行模型訓練，防止其他數據干擾模型。

但是面臨更多的是過擬合已經發生了，這時候就需要考慮如何去降低模型擬合狀態，解決過擬合通常有兩種思路，一種比較簡單的做法是將其修改成一個稍微簡單的模型，但是這樣處理的問題在于又要重新設計模型并重新計算，而且結果也并并不一定就較為正確。因此，面對過擬合的問題，通常采用的是正則化的方法，即在模型算法中添加函數來防止過擬合。

因此，需評判模型在新樣本上的表現情況，這時需要引入代價函數：用來表示預測值與實際值之間的差距。

代價函數：

采用這種函數的優點：這里的橫軸表示的是樣本點帶入到模型中的值；縱軸表示cost代價，即預測值與真實值之間的差距。

當y=1，真實結果為真的時候，如果Z>=1,代價恒為0，當Z小于1時，誤差隨著Z的減小而增大；

當y=0，真實結果為假的時候，如果Z＜=–1,代價恒為0，當Z大于–1時，誤差隨著Z的減小而增大：

正則化一般有以下兩種：

L1正則化，即將所有參數絕對值的和加到代價函數后面：

L2正則化，即將所有參數絕對值的平方和加到代價函數后面：

我們想要最小化的正常代價函數是： J(w,b) = (1/m) ＊ Sum(L(y(i),y’(i)))，因此，在使用了L2正規化之后新的代價函數為： J(w,b) = (1/m) ＊ Sum(L(y(i),y’(i))) +(Lamda/2m) ＊ ||W||2，其中Lamda稱之為正則化參數，如果Lamda太大，為了使cost Function盡量小，這樣會導致大量的W將會很小，使其接近于0，這將使得其升維失去作用，此時SVM失去了能夠升維的特點，如果Lamda設置的過小，就沒有正則化的效果。

2 總結與展望

本文設計的基于SVM技術的字符識別模型，實現了對字符的仿真識別。并且通過結果檢測提高了結果的準確性與計算速度，但由于時間能力有限，本文尚還存在很多不足的地方有待改善：

（1）有限維空間的SVM理論發展較快，無限維空間的SVM理論還需深入研究和推廣；

（2）針對SVM理論中優化問題的特點，如何建立簡單、有效和實用的算法是迫切需要解決的問題；

（3）將神經網絡與模糊邏輯等領域已有的研究方法和思想與SVM理論相結合，提出新的方法；

（4）如何將SVM應用于人臉識別與人臉檢測以及文本分類等各種領域也是接下來所要考慮的問題。