怎麼理解二階偏導與凸函數的Hessian矩陣是半正定的?
---20160212補充--
感謝grapeot和顧凌峰同學的回答,我在總結兩位同學的答案後又提出了一個新的疑問,和大家一起思考。首先總結一下兩位同學的答案:第一步 凸函數判定有1st-order condition,對於凸函數有以下充分必要條件:當然凸函數的定義域是一個凸集,這個1st-order condition非常好理解,就是凸函數任意一點處的切平面,永遠在下方,你可以理解成開口向上的拋物線,切線在它下方。第二步 證明1st-order condition與2nd-order condition等價,從而由2nd-order condition得到函數是凸函數的判定。
首先在處的二階泰勒展開如下(此處不嚴謹,沒有寫出二階以上的余項,但是方便接下來的討論,與之後我的疑問的引出,疑問就是與余項相關的):顯然只要1st-order condition就會成立,而要求只要(點處的Hessian矩陣)是半正定矩陣就可以了以上推理是非常清晰,但是我仍然有有個疑問(此處重點!!!):因為只考慮了泰勒的二階展開,如果泰勒展開的余項如果足夠大,會不會在二階項小於0的情況下,使得二階項與高次項的和大於等於0,從而使1st-order condition在二階項小於0的情況下成立,更有一個值得注意的情況是,泰勒的余項甚至都有可能是不收斂的!!!--原話--
一直比較困惑Hessian矩陣的性質,微積分的大磚頭教材里認為這是「高級的」話題,只給了個結論,而凸優化(Boyd)的書上也只給出了結論,所以我對這個結論理解的並不是很好,請問有沒有微積分進階的教材推薦呢,比如說清楚Hessian矩陣的。。還有機器學習方向的童鞋是不是有必要在看完大磚頭微積分書之後再去學習數學分析呢?謝謝。
教科書上有嚴格的證明,這個答案試圖通過類比來提供一些直觀上的理解。大概的結論是,多元函數的Hessian矩陣就類似一元函數的二階導。多元函數Hessian矩陣半正定就相當於一元函數二階導非負,半負定就相當於一元函數二階導非正。如果這個類比成立的話,凸函數的Hessian恆半正定就非常容易理解了——這是一元凸函數二階導必非負的多元拓展。
至於為什麼這個類是有道理的,你要這麼看。對一元函數f(x)來說,就極值而言,一階導為0是極值點的必要但不充分條件,一階導為0切二階導非負是極小值的充要條件。為什麼呢,因為有泰勒展開。如果一階導為0,二階導非負,dx不論是多少,f(x)一定不比f(x0)小。
你把多元函數也個泰勒展開,主要區別在於:
1) 二階導變成了Hessian。2) 以前只要考慮x怎麼變,現在還要考慮y怎麼變,x和y怎麼一起變,頭疼了很多。以二元為例,從一元的情況類比過來,如果一階導為0,是不是極小值完全取決於不同的dx, dy下,能不能做到最後一項一直非負。只有對於任意,一直非負的情況,我們才能說這是極小值。如果一直非正,這就是極大值。如果它一會正一會負,就是鞍點。
然後「對於任意,一直非負」這是啥?半正定的定義嘛!它就是這麼引出來的,也是我們為什麼需要半正定這個概念的原因(之一)。
(為了突出直覺,我們假設函數有一些「良好」的性質,比如連續,可微等。)更新:
我已經委託我的同學 @李欣宜重寫按照我的思路寫了篇更詳細更科普性質的博客,充要性的證明都在裡面,再加上知乎本身的排版不太友好,大家可以移步她的文章這麼早就說Hessian矩陣是半正定的,會不會給人一種凸函數的感覺?------------------------------------------數分教材基本都會有關於凸性(1st-order condition和2nd-order condition)的嚴格證明吧,我現在寒假在家手上沒有教科書,回校以後我再確認一下。@grapeot 寫的非常非常好,深入淺出,直觀易懂。但是在1st-order condition到定義的部分的證明有點太簡略了,也就是為什麼是函數為凸的充要條件。
為方便起見我們首先假設- 函數在定義域上連續
- 函數在定義域上二階可導
現在要證明的是:
- definition 1st-order condition
- 1st-order condition 2nd-order condition
實際上這些都是充要關係,但是因為題主的問題並沒有要求證明必要性我這裡就偷懶只證明充分性了。
首先凸函數(一元)的定義是:
任意屬於定義域的兩個自變數和,且對於任意,如果函數滿足,那麼函數是凸函數。直觀的理解就是函數曲線上任意兩點為短點的線段一定在函數曲線的上方。多變數函數可以把自變數寫成一個向量,同理對於定義域的任意兩個自變數和,以及任意,如果函數滿足,那麼函數是凸函數。1st-order condition 一階條件,還是以一元函數為例:
對於定義域內任意兩個自變數和,函數滿足則函數為凸函數。現在要證明的凸函數有的性質。
假設函數在定義域上是凸函數,那麼有:
然後稍微變形可以得到令,則,那麼有,當趨近於0時,有這一項也就是函數在處的導數值,實際是與的複合函數,容易求導得,由於只要求在處的導數值所以容易得,代入回不等式即可得到從圖形上也可以直觀去理解這個推導結果,取函數曲線上兩點作直線,被函數圖像截斷的那部分始終在曲線上方,而其他部分始終在曲線下方,那麼這兩個點取的無限接近,也就是通常我們說的「割線逼近切線」,那麼切線就始終在曲線下方了,曲線不知道高到哪裡去了。
現在我們來做第二部分也就是用1st-order condition推導2nd-order condition的部分的證明了。
2nd-order condition的內容就是凸函數的Hessian矩陣半正定。多元Taylor展開如果不熟悉的話可以參考Taylor"s theorem的公式自己理解,我這裡就不詳細展開了,直接寫在點處二階展開形式:
,這裡的即在點處的Hessian矩陣,也可以寫作,可以理解為把梯度向量推廣為二階形式,梯度向量本身也是Jacobian矩陣的一種特例。的Hessian矩陣第行第個元素為對第個變數先求導,對第個變數後求導的二階導數,也就是,寫成矩陣形式就是:回到上面那個Taylor展開式,對於一個凸函數,我們可以試用1st-order condition得到對於任意的和都成立,那麼二次項必須對於任意的兩個自變數和恆成立,我們這裡以增量簡寫,這個增量可以任意取值,那麼需要對於任意一個恆成立,而這就是是半正定的充要條件。證畢。
這個證明主要的就是三件事,弄清定義,弄清1st-order condition的推導,弄清2nd-order condition的推導。當然熟練求導也是很重要的。一個上/下凸函數的極值啊,一階導數固然重要,但也要考慮二階導數的行程。
後記:- 如果Hessian矩陣是正定的(不是半正定),那麼函數是嚴格的凸函數。
- 實際上我們說的問題可以擴展到廣義函數,也就是定義域內函數值依然是函數值,而定義域外的自變數對應的函數值規定為正無窮,那麼這些證明和推導依然是成立的。
- 對於凸性的要求並沒有那麼嚴格,這些定理中1st-order規定的只需要一階可導,2nd-order只要求二階可導。
- 因為我個人的書寫習慣原因,自變數構成的向量空間我使用的列向量,也就是說變數很多的時候,是個高高的向量,其他地方可能會把它寫成一個寬寬的行矩陣,注意對應矩陣都需要轉置一下就行了,對於這個證明的本質沒有太大的不同。
- 我認為一個做機器學習的學生沒有必要對證明的每個細節了解清楚,計算機系開的數學類課程能聽明白就行,數分不用太深入學,非要說ML和數學相關我也覺得只能算應用數學的分支,沒必要對自己那麼苛刻,會搬磚就行。
- 很慚愧,只做了一些微小的工作。
還有一個問題是為什麼不用考慮泰勒二階以上的值,有沒有可能二階非正定,但是後面項把值「加回來了」,使得1st-order condition成立?
這是一個很好的問題。
完整的帶Peano余項的二階Taylor展開應該是:
但是這裡不使用這個余項,因為這個余項在時相對於是更高階的無窮小,而一階條件必須對於任意小的增量成立。大概是我的書寫習慣讓你產生了困惑,是我的不對我道歉,那我用,這裡抽象的說表示長度,而可以近似於一個只有方向的向量。根據1st-order condition 可得,對於任意一個不為0的,可以寫成,這個關係在的時候依然成立(注意1st-order condition 的限定詞「任意」),此時,那麼必須滿足的條件就是關於一階條件的必要性「因為在每個很小的"x-x0"局部可以從hessian矩陣半正定推出1st-order condition成立,那麼在整體的大範圍上也是。"從直觀感覺上來說顯然是成立的,因為在切點附近切平面的點都在下方,那麼切平面也就在下方了,所以1st-order condition成立
我想了一下,這個思路應該是不可行的。只能保證在切線附近函數高於切線,而這個性質是無法累加到全局的。舉個不太恰當的例子,函數在處的切線是與函數曲線相交的,函數曲線上任意一點作切線也會和函數曲線相交。這最多只能證明某個點附近的凸性,不能證明1st-order condition所表達的一個區間或者整個定義域上的凸性。
我這裡簡單的寫一種必要性證明思路。現在已知在定義域內Hessian矩陣都是半正定的。那麼在使用帶有Lagrange余項的一階Taylor展開式為
其中為點處的Hessian矩陣,為與之間的一個值(閉區間),且因為是半正定的,所以必然有,因此對於任意的在定義域內的和都有本來應該提供一下這個證明的直觀解釋,但是我今天有點累,懶得開作圖包和打公式了,就放一張剛剛寫的草稿權當解釋了。以下為方便起見全部以一階為例。且假設我們可以類比0階的帶Lagrange余項Taylor展開,區間上必然有一個點的切線斜率正好是增長的方向。對於增函數來說,這個點的切線斜率始終大於0,所以函數的值必然是增大的。函數的增量也就是紅框中的部分,顯然兩部分應該是相等的,若這個等式成立那麼說明處的導數值必然小於區間內某個處的導數值,如果導函數單調減那這個條件就始終成立,反之如果始終成立也就是說這個區間內導函數始終單調減。(以上說法非常不嚴謹,僅僅是為了給證明過程提供一個直觀的解釋)其實這件事很簡單,你只要Google一下convex function + second order condition,隨便找一個名校的講義就可以了……
比如隨手我搜到這麼一篇:http://www.math.udel.edu/~angell/Opt/conv_fcn.pdf證明在第18頁到19頁。
簡單地說就是如果Hesse陣半正定就意味著存在支撐超平面,從而函數是凸的;反過來,如果函數是凸的,Hesse陣一定半正定(反證:假如Hesse陣不是半正定的,則存在負特徵值和相應的特徵向量,沿該特徵向量移動一小段距離就會走到當前位置的切平面以下)
關於Tayler展開式余項的問題,主要是因為你不知道多元函數的Taylor展式的余項的形式。wiki的Taylor"s Theorem頁面倒是有相應的內容,不過對機器學習來說,沒必要了解那些複雜的記號,只會把人弄暈:在數值優化中,通常只需要展開到二階,至於三階以上的項愛怎麼怎麼著吧。
於是,我在這裡安利一下Jorge Nocedal Stephen J. Wright的Numerical Optimization一書中提到的兩種泰勒展開式的形式(積分余項和拉格朗日余項,上面那個證明用的是拉格朗日余項):http://pan.baidu.com/s/1jGFBSNk
(知乎傳圖片死活傳不上去傳網盤了。share文件夾下面有一個taylor.png)
其他關於數學方面的建議是,數分就不要學了,畢竟你遇不到那些奇奇怪怪的(比如處處連續但處處不可導)函數,算功 和 你對你所研究的問題的認識更重要。如果題主對優化方面的內容感興趣,可以看一下我上面提到的Numerical Optimization,按這本書作者的原話,"We hope, too, that this book will be used by practitioners in engineering, basic science, and industry, and our presentation style is intended to facilitate self-study."
以及
"We have used a conversational style to motivate the ideas and present the numerical algorithms. Rather than being as concise as possible, our aim is to make the discussion flow in a natural way."
讀起來真的非常流暢和自然。
與此相反,Boyd的cvxopt真是要了我的老命了,簡直是怎麼難讀怎麼寫,迄今為止我才看了四章(當然也可能是因為我太廢柴)……不過必須承認Boyd的書里關於Dual Form的那一部分講解得非常好,相當細緻和深入。在該點有支撐超平面
原來 hessian 矩陣是這個意思啊!!
不是學數學的,查了好多資料都不知道這小小的一個矩陣是用來幹嗎的。。。真是太坑了。。
不帶正則性的話,我只知道凸函數本身是lipchitz的,但是這不夠刻畫二階導,所以接下來我們都只討論二階可導的凸函數,那麼顧名思義,這個函數任意方向的二階導大於等於0,而這恰好就是henssian矩陣半正定定義。
看到這個題目,我想起了本科數學系的時光。當年對教材里的每句話都要求能理解到位,不理解的畫出來,課程後的問題也必須題題都會做。題主的問題相當於到時的課本定理證明題,算送分題吧。然現在已無力證明,證明部分基本遺忘,想想好悲劇。。就像高中當年我們地史物化生,樣樣都會,然現在。。
上面都是感(扯)慨(淡),題主想了解嚴格證明,就找本數學系《數學分析》和《常微分方程》教材翻翻。先理解泰勒展開咯
推薦閱讀:
※矩陣乘以矩陣的轉置為什麼秩不變?(從向量空間的角度能否分析一下)?
※矩陣相似除了用定義和傳遞性還有什麼方法證明相似?
※線性代數中講多項式的意義何在?
※如何評價之江學院計算機專業不學線代和概率論?
※怎麼理解外代數是張量積的商空間?