我們之前講了三個問題,那再來我們就是要想辦法解這三個問題。那我們的問題就是,哪一個問題你覺得最難呢?

第一個正確的答案我們來做一下免疫調查。你覺得第一個problem最難的同學舉手一下。沒有人覺得他最難嗎?有人覺得他最難嗎?謝謝,手放下。你覺得第二個problem最難的同學舉手一下。謝謝,手放下。你覺得第三個problem最難的同學舉手一下。謝謝,手放下。

我覺得其實好像差不多。如果你覺得第三個problem最難的話,你這個運氣不錯。因為我們現在知道說,假如第一個problem他有某種specific的form,等一下我會定義說這個。

這個就假設F of X Y他長某個樣子,等一下我會講說這個樣子是什麼樣子。假如他長這個樣子的話,那第三個problem就不是個問題。

所以我們就要先來講講看我們剛才說的specific的form應該要長的是什麼樣子。那這個specific的form要長什麼樣子呢?我們說這個specific的form必須是linear的。

也就是說給我一個X Y的pair。首先我用一組特徵來描述這個X Y的pair。那這邊的每一個Phi代表,這邊每一個Phi 1, Phi 2, Phi 3代表一個value,代表一個scatter。

也就是說這個X Y跟Y Y他們具有characteristic 1的強度是這個值,具有特徵2的強度是這個值,具有特徵3的強度是這個值。

然後我們說這個F of X Y他長的什麼樣子呢?他長的是W 1,他就被定義成W 1乘上Phi 1,W 2乘上Phi 2,W 3乘上Phi 3。

這沒有問題嘛,這個還是一個F of X Y的function。你就把X Y代替這個function,找出這些feature,然後把它們乘上一組,你事先定好的位,W 1,W 2,W 3,你就可以得到F of X Y的值了。

然後W 1,W 2,W 3,我們是要從training data裡面得到的。你可以把它整理一下,你可以把W 1,W 2,W 3串成一個vector,你可以把這些特徵值Phi 1, Phi 2, Phi 3也串成一個vector。

這個W 1,W 2,W 3所形成的vector,我們就稱之為W,然後這個Phi所形成的vector,我們就稱之為Phi of X Y,所以這個W是一個vector,這個Phi是一個vector。

我們的F of X Y,我們就可以寫成W跟Phi的inner product,你把X跟Y代替這個function,然後抽出Phi這個vector,然後跟W做inner product的scale,就是這個F of X Y的output。

假如你的F of X Y寫成這樣,那Problem 3就不是一個問題。這樣講可能很抽象,所以我們還是用剛才舉的例子來說明一下這個F of X Y是長什麼樣子。

比如說假設我們要做object detection,那我們的X是image,而Y是一個founding box,那我們要定義一個feature的vector Phi,那這個Phi把這個X image跟Y這個founding box代進Phi這個function裡面,那我們要得到一個vector。

那這個vector怎麼定呢?其實就是隨便你定,你就胡亂定,比如說紅色的pixel在框框裡面出現的百分比當作一個維度,綠色的pixel在框框裡面出現的百分比是一個維度,藍色的是一個維度,或者是紅色在框框外的百分比是一個維度等等,你就胡亂定。

框框的大小是個維度,不過這些feature都很弱,你用這些feature可能沒辦法做一個良工春日的detector。

那在image裡面比較state-of-the-art的方法可能是用一個是用visual word,那visual word不知道大家知不知道是什麼?今天在這個圖上,我不知道大家看不看得清楚,你看到很多小小的方塊對不對?每一個方塊就代表了某種pattern,而不同顏色的方塊代表了不同的pattern,就像是文章裡面的詞彙一樣,所以他們叫做visual word。

那你就可以說,在這個框框裡面編號是100號的visual word出現幾個,那他們也是一個維度的feature。

這邊順便說明一下,這個visual word其實都是真的,我是真正用visual word的toolkit去抽這張image的,然後本來想要順便做一個良工春日的detector,但後來沒有成功就是了。

那這些feature一定要用人來定出來嗎?還是有人在做說這是自動的找feature?

對啊,這個問題問得非常非常好。就是這些feature要由人來找出來嗎?還是我們直接用model來抽呢?就是說,因為我們現在定義的這個function f of x,y,它是個linear function,它是兩個vector的inner product,那它其實沒有辦法做太厲害的事情。

所以你要讓它最後的performance好的話,你要抽出很好的feature。那要怎麼抽出很好的feature?當然你可以說我用人工的方法定,但是這樣子你不見得能夠找出好的feature。

所以如果是在object detection這個task上面,state of the art的方法就是,比如說你去train一個CNN,我們還沒有講過CNN是什麼,之後會請Winston來講。

沒關係,你就知道這是個很潮的東西。它就是一個很潮的network,你可以把這個image丟進這個CNN裡面,它也會output出一個vector,而這個vector可以很好的去代表這一個bounding box裡面的東西。

其實現在像Google他們在做object detection的時候,都是用類似的方法做。你知道那個object detection不是就是一個image,然後它會框起來,然後說這個框框裡面是什麼嗎?

那你有沒有想過說,這個東西能用一般的deep neural network做嗎?其實不行嘛,對不對?deep neural network怎麼可以告訴你那個框框在哪裡?

所以他們其實是用deep neural network加上structure learning的方法做的,只是他們在講的時候不知道為什麼,然後忽略structure learning這個部分,聽的時候有的就會一頭霧水,其實就是這麼回事。

所以抽feature,我們是可以用deep learning來抽feature。這個是用object detection當作例子,或者是如果你做summarization的話,那你的x是一個document,y是一個summary。

那你就可以定一些feature,比如說我可以說,這個y裡面有沒有包含important,如果y裡面有包含important這個word的話,這個feature可能是1,反之就是0。

你可以想像這個feature它可能對的weight是比較大的,因為如果y裡面有包含important這個word的話,那y可能是一個合理的summary。

或者是y裡面有沒有包含definition這個word,或者是y的長度是多少,你可以做定各式各樣的feature,或者是你可以定一個evaluation說y的summary必須要是很精簡的,定一個evaluation measure說y的精簡程度是多少等等。

那當然你也可以想辦法用deep learning抽一些比較有用的feature。好,那比如說如果是retrieval的話,其實也是一樣,x是keyword,y是搜尋的結果。

你就胡亂定,比如說你定說y的第一筆搜尋結果跟x的相關程度,當然你要想辦法定義什麼叫做相關程度,或者是說y的第一筆搜尋結果,它的相關程度有沒有比第二筆搜尋結果高,那這個也是一個feature等等,你就胡亂定。

或者是你可以定說y的diversity的程度是多少,那我們知道說每個人想要找的東西都不一樣,比如說你輸入java,你可能是要去java吧,或者是你想要學這個語言,那搜尋引擎不知道說你一定要找的到底是什麼,那個好的方法就是把各種information都搜尋出來。

所以可以說我們定一個measure叫做diversity,看看說我們的搜尋結果是不是有包含足夠不同的豐富的資訊,這個是第一個問題,反正你就是要想個辦法定義一下這個feature就對了。

那如果第一個問題定義好了以後呢?那第二個問題怎麼辦呢?我們本來的f of x,y就可以寫成兩個vector的inner product,但是我們一樣是要去窮取錯的y,看哪一個y可以讓這個值最大。

這個怎麼辦呢?我們先不要管它,我們就假設這個問題已經被solved了,假裝已經被solved了。

假裝這個問題已經被solved了以後呢,我們就進入第三個問題。

第三個問題呢,我們剛才已經講過了,就是我今天找了一大堆training data,x跟y hat,那我希望找到一個function f,那我現在所謂的希望找到一個function大f,其實是希望找到一個位w,因為我們知道這個function大f其實就是由w定義的啊。

我們要找到這個w,使得以下的條件被滿足。對所有的training data而言,我們希望正確的,如果我們用xr跟正確的y hat抽出來的feature跟w做inner product,它的值應該大過於任何y hat以外的y跟xr抽出來的feature跟w做inner product。

如果這個大過於它的話,我們就可以讓正確的y它的function f大過於錯誤的function f,大過於錯誤的y所帶進去這個f以後所得到的值了,這個是我們想要的。

或者是呢,如果我們用比較具體的例子來說明一下,我們現在要達到的目標是什麼?

我們現在達到的目標是這樣,假設我現在要做的是object detection,那我收集了一張image x1,然後我知道說x1所對應的y1 hat應該是這個框框。

那我收集了另外一筆data x2,另外一張image x2,那我知道它對應的框框應該在這個位置。然後我們假設x1跟y1 hat所形成的feature是紅色的這個點。

我們現在假設feature是只有兩維,所以它可以畫在圖上,但是實作上你可能會抽個千維、百維、萬維這樣子。那我們假設x1跟y1 hat所形成的feature是紅色的點,其他的y跟x1所形成的feature是藍色的點。

那我們把它畫在圖上,這個紅色的點,就是如果你的框框在這個地方,它是紅色的點,在其他地方是藍色的點。那你可以想像說紅色的點只有一個,而藍色的點有好多好多好多個,這邊只是隨便舉三個意思意思以下。

好,那我們說這個x2跟y2 hat所形成的feature是紅色的星星,那x2跟其他的y所形成的是藍色的星星。

那如果我們把紅色的星星跟藍色的星星畫在圖上的話,假設它們是在這些個位置,那這個正確的框框所形成的feature是在這個地方,然後錯誤的框框所形成的feature在這些個地方。

那你可以想像說紅色的星星只有一個,但藍色的星星也是有千百萬個。

那我們再來要達到的任務就是,我們希望找到一個w。那這個w可以做到什麼事呢?這個w可以做到的事情是,我們把這上面的每一個點,紅色的星星、紅色的圈圈、成千上萬的藍色的圈圈跟成千上萬的藍色的星星,通通拿去跟w做inner product以後,

我得到的結果是,紅色的星星所得到的值大過於所有藍色的星星所得到的值,而紅色的圈圈所得到的值大過所有藍色的圈圈所得到的值。

當然不同的形狀間我們就不比較,藍色圈圈自己跟圈圈比,只要紅圈圈大過藍圈圈就好,那星星自己跟星星比,只要紅星星大過藍星星就好。那我們要做的事情就是這個樣子。

也就是說,我們希望正確的答案所形成的feature跟w做inner product以後,大過於其他的y跟w所形成的inner product,這是我們要完成的事情。

講到這邊,大家有問題嗎?

會有什麼情況是圈圈要跟星星比是什麼?

其實沒有,圈圈就跟圈圈比,星星就跟星星比,他們不需要一起比。

韓文同學有問題了。

接下來,你可能會覺得說,這個問題會不會很難呢?我們要找到一個w完成這件事情,但是這個藍色的東西可是有成千上萬個喔,我們有辦法找到這樣子的w嗎?

接下來要講的就是,這個問題沒有我們想像中的那麼難。

所以我們底下就是提供一個演算法,這個演算法它可以做到的事情就是,假設我剛才說的那個要讓紅色大於藍色的這個factor只要它存在。

只要它不存在就沒辦法,那如果存在的話,用下面這個演算法,我們可以找到答案。

好,那這個演算法它是長什麼樣子呢?我們來說明一下。

我們現在這個演算法的它的input就是我們的training data,x1,y1 head,x2,y2 head,等等。

那它output就是要找到一個vector w,這個vector w要滿足我們之前所說的那個我們要找到的特性。

然後呢,這個怎麼做呢?一開始我們先initialize這個w是0,然後呢,我們呢,開始跑一個這個quail回圈。

那在這個回圈裡面呢,每次呢,我們都取出一筆training data,xr,yr head,然後呢,我們去找一個yr tilde,它可以讓w跟y、xr、y的值最大。

就是我今天找到一個yr tilde,它可以讓這個function的值最大。

那你可能會問說,這個事情怎麼做呢?那你想想看,我們剛才這個問題其實就是problem2啊,那我們剛才已經假設說problem2已經解決了,所以這個東西反正就是有解的就對了。

好,那如果我今天找出來的y tilde,它不是正確答案y head的話,那代表我今天這個w不是我要的,

因為如果這個w是我要的,它最大的,它可以讓這個值最大的那個y就是y head,這才是我要的w。

那如果今天得出來的是y tilde,那這個w不是我要,那我把這個w改一下。

怎麼改呢?我把這個xr跟yr head的feature算出來,我把xr跟yr tilde的feature也算出來,我把這兩個feature相減,再加到w裡面,再update w。

然後我用新的w以後,我再去取一個sample,然後再重新算一次max,如果算出來不對再update,然後這個步驟就一直一直下去。

那如果今天我們要找的w是存在的話,它最終就會停止。

這個演算法你有沒有覺得很熟悉呢?有嗎?有沒有修過這個宣田的機器學習?這不就是percentron的algorithm嗎?

你可以回去想想看這個algorithm的那個,你知道percentron它做的就是binary classification,那我們今天要做的不是binary classification,我們今天要做的是structure learning。

但是你可以想想看binary classification其實也就是structure learning的一個特例而已,你可以回去想想看我今天講的這個algorithm跟這個percentron learning有什麼樣的關係。

其實以下證明跟percentron的證明幾乎是一樣的。

我們舉個例子來說明一下剛才那個演算法是怎麼運作的,如果你沒有聽得很清楚的話,它是怎麼運作的呢?

我們今天的目標是要找到一個w,它可以讓紅色星星大過藍色星星,紅色圈圈大過藍色圈圈,假設這個w它是存在的。

這個演算法做的事情是這樣,首先我們假設w是0,然後我們隨便pick一個training data,training data現在只有兩筆,

我們就pick這個x1,y1 head,x1,y1 head的那個點的分布長得是這個樣子。

然後我要根據我現在手上的data w,去看說哪一個y它所形成的feature跟w做inner product以後得到的值最大。

那現在因為w是0嘛,所以你這個feature不管是誰所形成的feature算出來了都是0的,所以其實都是一樣的,那沒關係,我們就random的選一個y出來當作y tilde。

那我們假設我們選了這個點當作y tilde。然後因為今天我們選出來這個y tilde跟y head,y head是這個,y tilde跟y head它們不一樣,

所以我要調整一下我的w,怎麼調整呢?我調整的方法就是把y tilde,y head所形成的feature,減掉y tilde所形成的feature,減掉y tilde所形成的feature,再跟w加起來。

所以這一項是這一個,對不對?這一項是這一個。然後因為w是0嘛,0加上這個以後就還是這一個。所以我們現在經過第一個iteration以後,我們找到一個w。

那接下來在第二步呢,我們就再選一個training data,我們現在選的是x2,y2,head。那選了x2,y2,head以後呢,我本來以為說這邊怎麼沒有紅色的星星,是不是我弄錯了?

但我發現說我沒有弄錯,紅色的星星在這裡。跟其他人,跟這個圖例混在一起,好,沒有關係。好,那這個紅色的星星在這邊,藍色的星星在這邊。

那我們要做的事情就是窮舉所有的y,這個y可能有成千上萬個,雖然這邊只畫幾個點,1414以下而已,成千上萬個y。

哪一個跟w形成feature,跟w做inner product以後呢?最大。然後呢,我們現在就真的算一下,假設我們就算一下,算一下,算一下。

然後發現說,誒,這一個y,它跟w,現在我們手上的w算出來的inner product最大。那這一個y呢,我們就說它是y2,它2。然後發現y2,它2,跟y2,head呢,它們是不一樣的。那沒關係,我們就去update一下w。

怎麼update呢?我們要把這一個圈圈的vector,這一個紅色的星星的vector,減掉這一個我們選出來的藍色星星的vector。那這個vector呢,就是綠色的這個vector。

那我們把綠色的這個vector,加上原來的w這個vector,把它加起來以後呢,我們就得到了一個新的w,它是在這個方向,它是在這個方向。好,那我們得到這個新的w以後呢,我們還沒有結束,我們要繼續去算。

我們要繼續再去看一遍這個x1跟y1,那我們發現說呢,這個新的w,如果拿這個新的w去跟所有的這個點呢,通通拿去算inner product的話,這個時候呢,y1 head,y1 tilde其實就等於y1 head,y1 tilde就等於y1 head。

所以這個w呢,對第一筆data來說呢,它是我們要的。接下來呢,我們再選一遍第二筆data,那我們發現說呢,對第二筆data而言呢,我們發現說對第二筆data而言呢,我們選出來的y2 tilde也正好就等於y2 head。

這個呢,w呢,也是我們要的。那我們看過一個iteration以後,我們看過所有的data以後,我們發現現在w呢,不再更新。

那其實現在我們不管再怎麼pick這個data了,w呢,都已經不會再更新了,這個時候呢,我們就停止整個的training,那我們發現說呢,現在我們所找出來的這個w,它可以讓y2 head,讓紅色的星星跟它inner product以後大過藍色的星星,跟紅色的圈圈做inner product以後大過所有藍色的圈圈。

所以呢,我們就結束了,結束了。接下來呢,我其實要講的就是,接下來其實想要做的事情是證明說以上的敘述是會,以上的這個演算法它最後是會結束的。

就算是說今天我們那些藍色的東西呢,它有成千成千上萬個,這個演算法終究是結束的,終究會結束的,而且它跟那些藍色的object的數目呢,是沒有關係的。

接下來就是比較數學的部分了,那我相信大家都很累,所以我想我們今天就先上到這邊好了,謝謝。