在本科模式識(shí)別課程中引入最優(yōu)化方法教學(xué)內(nèi)容的思考

牟大中,王明飛,羅文秋

(高端印刷裝備信號(hào)與信息處理北京市重點(diǎn)實(shí)驗(yàn)室, 北京 102600)

一、引言

模式識(shí)別是指從樣本觀測(cè)數(shù)據(jù)中自動(dòng)提取有用模式,以實(shí)現(xiàn)樣本分類和進(jìn)行決策的過(guò)程[1]。作為人工智能的重要組成部分,模式識(shí)別一直以來(lái)都是智能類和計(jì)算機(jī)類等相關(guān)專業(yè)的核心課程,也是其他信息類本科專業(yè)的選修課程。從相關(guān)專業(yè)人才培養(yǎng)角度來(lái)看,模式識(shí)別在整個(gè)課程體系中占據(jù)著非常重要的地位。一方面,模式識(shí)別課程包含了人工智能領(lǐng)域中一些非常重要的基本概念、基本原理和經(jīng)典算法,對(duì)于夯實(shí)學(xué)生的理論基礎(chǔ)和后續(xù)發(fā)展具有非常重要的作用;另一方面,模式識(shí)別在相關(guān)專業(yè)課程體系中是第一門面向工程應(yīng)用的智能類課程,對(duì)培養(yǎng)學(xué)生的創(chuàng)新能力和思維方式具有重要的現(xiàn)實(shí)意義。

模式識(shí)別是一門理論性和交叉性都很強(qiáng)的課程,對(duì)學(xué)生的數(shù)學(xué)基礎(chǔ)要求比較高。數(shù)學(xué)類的先修課程主要包括高等數(shù)學(xué)、線性代數(shù)、概率論與數(shù)理統(tǒng)計(jì)、最優(yōu)化方法等。在上述課程中,前三門課程在理工科專業(yè)一般均作為公共基礎(chǔ)課在低年級(jí)階段開設(shè),而最優(yōu)化方法課程一般開設(shè)在本科高年級(jí)階段,往往與模式識(shí)別課程在開設(shè)時(shí)間上存在沖突[2]。另外,隨著人工智能技術(shù)的快速發(fā)展,一些新型的智能類專業(yè)課程,如機(jī)器視覺(jué)、自然語(yǔ)言處理、深度學(xué)習(xí)等也紛紛列入教學(xué)計(jì)劃中,使得模式識(shí)別課程在時(shí)間安排上也無(wú)法后移。因此,恰當(dāng)處理最優(yōu)化教學(xué)內(nèi)容與模式識(shí)別課程之間的相互關(guān)系顯得尤為重要。

對(duì)于模式識(shí)別課程來(lái)說(shuō),最優(yōu)化方法的教學(xué)目標(biāo)是為模式識(shí)別的具體工程問(wèn)題提供理論和算法指導(dǎo)[3]。最優(yōu)化方法內(nèi)容非常豐富,而模式識(shí)別課程的學(xué)時(shí)又相對(duì)有限。如何將最優(yōu)化內(nèi)容有效地融入模式識(shí)別的教學(xué)過(guò)程中,使得學(xué)生既能掌握必要的最優(yōu)化知識(shí),又不至于最優(yōu)化教學(xué)喧賓奪主,占用過(guò)多的學(xué)時(shí),是另一個(gè)值得深入探討的問(wèn)題。

二、現(xiàn)有教學(xué)模式的局限性

目前各相關(guān)高校在最優(yōu)化相關(guān)教學(xué)內(nèi)容安排上大相徑庭:有的學(xué)校安排在模式識(shí)別課程之前獨(dú)立設(shè)課;有的學(xué)校則在模式識(shí)別課程內(nèi)將涉及的最優(yōu)化知識(shí)點(diǎn)分散到相應(yīng)章節(jié)內(nèi)分別講授;但也有部分學(xué)校在教學(xué)安排上缺乏相應(yīng)的講授內(nèi)容。

將最優(yōu)化方法單獨(dú)設(shè)課的做法有利于學(xué)生系統(tǒng)地學(xué)習(xí)和掌握最優(yōu)化知識(shí),但往往數(shù)學(xué)抽象性較強(qiáng),過(guò)于強(qiáng)調(diào)數(shù)學(xué)公式推導(dǎo)和定理的證明,缺乏具體問(wèn)題導(dǎo)向性和針對(duì)性。這樣很多學(xué)生在學(xué)習(xí)過(guò)程中往往難以將模式識(shí)別的實(shí)際問(wèn)題和最優(yōu)化模型結(jié)合起來(lái),導(dǎo)致這些學(xué)生在學(xué)完本課程后不具備用最優(yōu)化方法分析和解決實(shí)際模式識(shí)別問(wèn)題的能力。而且在單獨(dú)設(shè)課情況下,授課教師往往過(guò)于注重知識(shí)體系的完備性,傾向于知識(shí)點(diǎn)的面面俱到,導(dǎo)致占用學(xué)時(shí)較多。

如果在模式識(shí)別教學(xué)環(huán)節(jié)中缺少最優(yōu)化教學(xué)內(nèi)容,會(huì)使得學(xué)生對(duì)實(shí)際問(wèn)題的最優(yōu)化模型和算法難以理解,對(duì)如何確定目標(biāo)函數(shù)和相應(yīng)的約束條件沒(méi)有深刻的認(rèn)識(shí),以至于在學(xué)習(xí)過(guò)程中出現(xiàn)生搬硬套教材內(nèi)容,知其然不知其所以然,無(wú)法靈活運(yùn)用相關(guān)知識(shí)的現(xiàn)象。甚至?xí)?dǎo)致學(xué)生在學(xué)習(xí)過(guò)程中產(chǎn)生畏難情緒,甚至?xí)a(chǎn)生逆反心理,嚴(yán)重影響課程的教學(xué)效果。

盡管有的學(xué)校在模式識(shí)別課程內(nèi)也涉及最優(yōu)化內(nèi)容的教學(xué)。但在具體的教學(xué)實(shí)施過(guò)程中,往往是根據(jù)教學(xué)內(nèi)容的先后順序講授所涉及的最優(yōu)化知識(shí)點(diǎn),即用到哪些知識(shí)點(diǎn)才進(jìn)行相關(guān)知識(shí)補(bǔ)充。例如,在線性分類器章節(jié)中講授梯度下降法和牛頓下降法,在支持向量機(jī)章節(jié)中講授KKT條件等。這種教學(xué)模式會(huì)導(dǎo)致最優(yōu)化方法講授內(nèi)容過(guò)于分散,不利于學(xué)生形成一個(gè)系統(tǒng)完整的知識(shí)體系。

三、模式識(shí)別課程最優(yōu)化方法教學(xué)內(nèi)容設(shè)計(jì)

(一)主要考慮因素與對(duì)策

幾乎所有模式識(shí)別問(wèn)題最后都可以歸結(jié)為一個(gè)最優(yōu)化問(wèn)題,其求解目標(biāo)是在一定約束條件下極小化代價(jià)(損失)函數(shù)。因此最優(yōu)化方法基本上貫穿了整個(gè)模式識(shí)別教學(xué)過(guò)程,在模式識(shí)別課程中占有非常重要的地位。

在模式識(shí)別課程中納入最優(yōu)化教學(xué)內(nèi)容,主要考慮因素及相關(guān)對(duì)策包括以下三點(diǎn):一是要充分考慮到學(xué)生已具備的相關(guān)知識(shí)基礎(chǔ),例如,在高等數(shù)學(xué)中的方向?qū)?shù)、梯度和拉格朗日函數(shù)的基本概念,多元函數(shù)的無(wú)條件極值和條件極值的基本求解思想等。對(duì)于這些已學(xué)習(xí)過(guò)的內(nèi)容,主要以復(fù)習(xí)回顧和補(bǔ)充講授為主。二是在選擇最優(yōu)化教學(xué)內(nèi)容時(shí)要充分考慮到模式識(shí)別的課程背景,將最優(yōu)化方法教學(xué)內(nèi)容與模式識(shí)別具體問(wèn)題緊密聯(lián)系起來(lái),對(duì)教學(xué)內(nèi)容進(jìn)行合理精練和規(guī)劃。在教學(xué)過(guò)程中應(yīng)盡量淡化各種定理的證明,壓縮數(shù)學(xué)公式推導(dǎo)過(guò)程,主要讓學(xué)生掌握基本概念和經(jīng)典算法。三是要充分考慮到最優(yōu)化教學(xué)內(nèi)容的條理性和系統(tǒng)性。在教學(xué)內(nèi)容上宜采用總分結(jié)構(gòu),即首先將最優(yōu)化作為一個(gè)獨(dú)立章節(jié)講授,主要介紹最優(yōu)化的基本思想和典型算法框架;其次在后續(xù)各章節(jié)中,根據(jù)具體模式識(shí)別問(wèn)題講授相應(yīng)的優(yōu)化方法及算法實(shí)現(xiàn)。這樣既不破壞最優(yōu)化方法教學(xué)內(nèi)容的相對(duì)獨(dú)立和完整,又能促進(jìn)學(xué)生在學(xué)習(xí)過(guò)程中理論基礎(chǔ)與實(shí)際應(yīng)用相結(jié)合。

(二)整體教學(xué)內(nèi)容規(guī)劃

根據(jù)本科模式識(shí)別課程的教學(xué)目標(biāo),應(yīng)適當(dāng)調(diào)整最優(yōu)化方法的傳統(tǒng)教學(xué)內(nèi)容[4,5],重點(diǎn)講授基本的最優(yōu)化思想和必要的優(yōu)化算法,強(qiáng)化最優(yōu)化方法的直觀幾何解釋。為滿足模式識(shí)別課程教學(xué)的實(shí)際需要,最優(yōu)化方法的教學(xué)內(nèi)容可規(guī)劃為以下三個(gè)主要部分:

1.最優(yōu)化方法的基礎(chǔ)知識(shí),主要包括最優(yōu)化問(wèn)題的數(shù)學(xué)模型、多元函數(shù)分析、凸性等。

對(duì)模式識(shí)別問(wèn)題進(jìn)行分析和求解的第一步是建立一個(gè)合適的優(yōu)化模型,即確定優(yōu)化問(wèn)題的目標(biāo)函數(shù)和可行域。優(yōu)化模型是對(duì)實(shí)際模式識(shí)別問(wèn)題進(jìn)行抽象描述的必備數(shù)學(xué)工具。掌握一些規(guī)范和常用的數(shù)學(xué)符號(hào)(如極大極小化符號(hào)、上下確界符號(hào)等),可為課程后續(xù)內(nèi)容的所有優(yōu)化模型提供簡(jiǎn)潔和統(tǒng)一的描述方式。

最優(yōu)化方法非常依賴于多元函數(shù)分析的基礎(chǔ)知識(shí),如方向?qū)?shù)、梯度、Hesse矩陣以及多元泰勒展開等。這些內(nèi)容是后續(xù)許多重要優(yōu)化算法的數(shù)學(xué)基礎(chǔ)。

凸性是較線性更為一般的性質(zhì),在最優(yōu)化中具有重要的作用。例如,凸集分離定理是凸性在最優(yōu)化理論中的一個(gè)重要應(yīng)用結(jié)果,它為分類問(wèn)題提供了理論上的支持。在分類問(wèn)題中,通常把帶有不同類別標(biāo)簽的訓(xùn)練樣本集看作不同的凸集,而分類器就是分隔這些凸集的超平面。

2.無(wú)約束問(wèn)題的優(yōu)化,主要包括無(wú)約束問(wèn)題優(yōu)化的最優(yōu)性條件、最速下降法、牛頓法、共軛梯度法等。

無(wú)約束優(yōu)化方法是最優(yōu)化問(wèn)題的基礎(chǔ)求解方法。不僅許多實(shí)際的模式識(shí)別問(wèn)題可以轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題,而且求解該類問(wèn)題的許多算法經(jīng)過(guò)適當(dāng)修改后也可用于約束優(yōu)化問(wèn)題的求解。無(wú)約束問(wèn)題優(yōu)化的最優(yōu)性條件包括一、二階必要條件和二階充分條件。在目標(biāo)函數(shù)滿足凸性的假設(shè)下,則可給出全局極值的充分必要條件。這些最優(yōu)性條件是后續(xù)各種優(yōu)化算法推導(dǎo)和分析的理論基礎(chǔ)。

無(wú)約束優(yōu)化問(wèn)題通常采用數(shù)值迭代法求解,搜索方向和步長(zhǎng)的選擇是無(wú)約束優(yōu)化算法的核心。選擇不同的下降搜索方向,會(huì)形成不同的迭代算法。最速下降法是一種采用負(fù)梯度方向作為搜索方向的無(wú)約束優(yōu)化算法,它是最經(jīng)典的無(wú)約束優(yōu)化算法,也是許多現(xiàn)代優(yōu)化算法的基礎(chǔ)。除最速下降法之外,還可根據(jù)實(shí)際教學(xué)情況選擇性地講解牛頓法、擬牛頓法和共軛梯度法等改進(jìn)的無(wú)約束優(yōu)化算法。

3.約束問(wèn)題的優(yōu)化,主要包括一般約束優(yōu)化問(wèn)題與KKT條件、拉格朗日乘子法、拉格朗日對(duì)偶性等。

在約束優(yōu)化問(wèn)題中,自變量的取值受到某種約束條件的限制,目標(biāo)函數(shù)在無(wú)約束條件下的平穩(wěn)點(diǎn)很可能不在可行域內(nèi),通常情況下不能直接使用無(wú)約束最優(yōu)條件來(lái)處理約束優(yōu)化問(wèn)題。

約束優(yōu)化問(wèn)題的約束條件一般包括等式約束條件和不等式約束條件。研究約束優(yōu)化問(wèn)題的一種重要方法是拉格朗日乘子法,它的基本思想是為每個(gè)約束條件引入一個(gè)拉格朗日乘子,以該乘子為加權(quán)因子將約束條件增加到目標(biāo)函數(shù)里,從而將原約束優(yōu)化問(wèn)題轉(zhuǎn)化為相應(yīng)的無(wú)約束優(yōu)化問(wèn)題。

KKT條件是約束優(yōu)化問(wèn)題局部最優(yōu)解的一階必要條件,包括平穩(wěn)點(diǎn)條件、等式約束的原始可行性條件、不等式約束的原始可行性條件、對(duì)偶可行性條件和互補(bǔ)松弛條件。而對(duì)于凸優(yōu)化問(wèn)題,當(dāng)滿足Slater條件時(shí),KKT條件則成為局部最優(yōu)解(也是全局最優(yōu)解)的充分必要條件。

拉格朗日對(duì)偶性是求解約束優(yōu)化問(wèn)題的有力工具,在許多實(shí)際應(yīng)用中經(jīng)常利用拉格朗日對(duì)偶性將不容易求解的原始問(wèn)題轉(zhuǎn)變?yōu)橄鄬?duì)容易求解的對(duì)偶問(wèn)題。

(三) 具體教學(xué)內(nèi)容設(shè)計(jì):以支持向量機(jī)為例

支持向量機(jī)是Vapnik于1995年基于結(jié)構(gòu)風(fēng)險(xiǎn)極小化原則提出來(lái)的一種有監(jiān)督的學(xué)習(xí)方法。作為機(jī)器學(xué)習(xí)領(lǐng)域中最重要方法之一,支持向量機(jī)被廣泛應(yīng)用于模式分類和回歸分析中,也因而成為當(dāng)前主要模式識(shí)別課程教學(xué)或參考教材的主要內(nèi)容[1,6,7]。支持向量機(jī)分析與求解的各方面涉及許多最優(yōu)化知識(shí),在教學(xué)過(guò)程中相關(guān)最優(yōu)化教學(xué)內(nèi)容可設(shè)計(jì)為以下五個(gè)部分。

1.基本優(yōu)化問(wèn)題

支持向量機(jī)基本模型是定義在線性可分特征空間上間隔最大的線性分類器,該模型是學(xué)生深入理解掌握支持向量機(jī)的基礎(chǔ)。如果訓(xùn)練樣本集是完全線性可分的,則該分類器以最大化幾何間隔為優(yōu)化目標(biāo),來(lái)確定一個(gè)最優(yōu)的分隔超平面。優(yōu)化目標(biāo)函數(shù)是一個(gè)二次函數(shù)并且約束條件是仿射函數(shù),因此該基本優(yōu)化問(wèn)題是一個(gè)典型的凸二次規(guī)劃問(wèn)題。

2.松弛與懲罰

這部分教學(xué)內(nèi)容的重點(diǎn)是讓學(xué)生理解和掌握最優(yōu)化方法中一些特殊的處理技巧。例如,如果訓(xùn)練樣本集不是完全線性可分的,即在訓(xùn)練樣本集存在一些少數(shù)的奇異點(diǎn)(outlier),那么基本優(yōu)化問(wèn)題中的約束條件將無(wú)法全部得到滿足。此時(shí)可考慮采用最優(yōu)化方法中常用的松弛技巧,為約束條件中的每個(gè)樣本點(diǎn)引入一個(gè)松弛變量,從而將原始問(wèn)題的可行域進(jìn)行放大。同時(shí),為將引入的松弛變量限制在一個(gè)合理范圍內(nèi),在原目標(biāo)函數(shù)中增加松弛變量的和函數(shù)作為懲罰項(xiàng),這實(shí)際上是對(duì)松弛變量進(jìn)行懲罰,并且為懲罰項(xiàng)引入一個(gè)正的懲罰系數(shù),增大該系數(shù)將增大對(duì)松弛(誤分類)的懲罰,反之將減小對(duì)松弛(誤分類)的懲罰。

3.拉格朗日對(duì)偶問(wèn)題

支持向量機(jī)原始問(wèn)題是一個(gè)典型的凸二次規(guī)劃問(wèn)題。對(duì)于凸二次規(guī)劃問(wèn)題,可以調(diào)用現(xiàn)成的凸二次規(guī)劃軟件包直接進(jìn)行求解,但借助拉格朗日對(duì)偶性有可能將原始問(wèn)題轉(zhuǎn)化為更容易求解的對(duì)偶問(wèn)題。這部分教學(xué)內(nèi)容的理論抽象性較高,對(duì)于本科學(xué)生而言,講授時(shí)不應(yīng)過(guò)多糾結(jié)于數(shù)學(xué)概念和定理證明的嚴(yán)密性。幫助學(xué)生理解拉格朗日對(duì)偶問(wèn)題的構(gòu)建過(guò)程和對(duì)偶算法的求解過(guò)程是該部分教學(xué)的關(guān)鍵,具體可分為兩個(gè)講授環(huán)節(jié):

第一個(gè)講授環(huán)節(jié)是應(yīng)用拉格朗日對(duì)偶性將原始問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題。在這一環(huán)節(jié)中應(yīng)重點(diǎn)向?qū)W生闡明在對(duì)偶問(wèn)題中目標(biāo)函數(shù)僅與拉格朗日乘子有關(guān),而與原始問(wèn)題中的參數(shù)無(wú)關(guān)。另外,在對(duì)偶問(wèn)題中樣本點(diǎn)總是以內(nèi)積的形式成對(duì)出現(xiàn),這一現(xiàn)象對(duì)非線性支持向量機(jī)中引入核方法非常關(guān)鍵。

第二個(gè)講授環(huán)節(jié)是通過(guò)對(duì)偶問(wèn)題的最優(yōu)解來(lái)求得原始問(wèn)題的最優(yōu)解。支持向量機(jī)的原始問(wèn)題和對(duì)偶問(wèn)題強(qiáng)對(duì)偶性、原始問(wèn)題最優(yōu)解和對(duì)偶問(wèn)題最優(yōu)解之間的關(guān)系等內(nèi)容是這部分的教學(xué)重點(diǎn),還應(yīng)重點(diǎn)向?qū)W生講清楚這一關(guān)系是通過(guò)KKT條件建立起來(lái)的。

4.序列最小最優(yōu)化算法

序列最小最優(yōu)化算法又稱為SMO算法,是一種快速的啟發(fā)式二次規(guī)劃優(yōu)化算法,這一算法對(duì)于求解支持向量機(jī)對(duì)偶問(wèn)題非常有效。SMO算法的巧妙思路是在每次迭代步中只優(yōu)化兩個(gè)參數(shù)而固定其他參數(shù)不變,從而降低了優(yōu)化問(wèn)題的規(guī)模。同時(shí)在求解過(guò)程中可以解析求解,進(jìn)一步提高了算法的計(jì)算速度。SMO算法是一種相對(duì)較難的最優(yōu)化算法,在講授過(guò)程中應(yīng)重點(diǎn)講解算法的核心部分,使得學(xué)生能夠把握算法的基本步驟和思想,而不至于陷入算法的局部細(xì)節(jié)忽略了整體框架。

5.Python編程實(shí)踐

在教學(xué)過(guò)程中,應(yīng)通過(guò)設(shè)計(jì)合適的實(shí)驗(yàn)案例來(lái)引導(dǎo)學(xué)生學(xué)以致用,通過(guò)實(shí)踐促進(jìn)理論教學(xué)效果的提升。根據(jù)筆者的教學(xué)經(jīng)驗(yàn),經(jīng)典的鳶尾花(Iris)屬種分類問(wèn)題涵蓋了支持向量機(jī)的三種基本形式,適合作為相關(guān)優(yōu)化算法的Python編程實(shí)驗(yàn)案例。例如,山鳶尾花的分類問(wèn)題可以設(shè)計(jì)為線性可分支持向量機(jī)算法實(shí)驗(yàn)案例,以加深學(xué)生對(duì)支持向量機(jī)基本模型和對(duì)偶學(xué)習(xí)算法的理解,并可與感知器算法分類實(shí)驗(yàn)進(jìn)行對(duì)比;弗吉尼亞鳶尾花的分類問(wèn)題可設(shè)計(jì)為線性支持向量機(jī)算法的實(shí)驗(yàn)案例,以加深學(xué)生對(duì)松弛和懲罰的理解;變色鳶尾花的分類問(wèn)題可以設(shè)計(jì)為非線性支持向量機(jī)算法的實(shí)驗(yàn)案例,以加深學(xué)生對(duì)核方法和支持向量機(jī)特點(diǎn)的理解。