摘要

針對(duì)在具有重疊結(jié)構(gòu)的透明矩形中尋找木偶這一問題，Hinton大神想到使用松弛算法，通過從沖突局部解釋網(wǎng)絡(luò)中提取全局最佳圖形的方式找木偶。

介紹

該程序的輸入是透明矩陣的四個(gè)角坐標(biāo)，見圖1。要找到木偶模型的最佳實(shí)例化的難點(diǎn)在于，如果我們只考慮一個(gè)矩形及其重疊的矩形，那么每個(gè)矩形可以是幾個(gè)不同的子木偶組成或者根本不存在子木偶，所以必須通過找到全局最優(yōu)解釋，來解決局部模糊性的問題。

本文作者介紹了如何使用松弛方法，而不是將所有局部可解釋的空間組合進(jìn)行顯式搜索。松弛方法有以下幾個(gè)優(yōu)點(diǎn)：

1.利用并行計(jì)算可以快速地找到全局最優(yōu)解釋。在計(jì)算局部可能的數(shù)量上，需要的時(shí)間不是指數(shù)級(jí)的，因?yàn)榻M合沒有被顯式處理。

2.所需的計(jì)算空間只隨著可移植性的數(shù)量線性增加，這使得該方法優(yōu)于全局搜索和寬度優(yōu)先并行搜索方法，并且寬度優(yōu)先并行搜索方法存在組合爆炸的問題。

3.該方法提供了全局最優(yōu)解釋，而不僅僅是像啟發(fā)式搜索那樣只是得到一個(gè)可用的解釋。

圖1a 有一些額外矩形的木偶

圖1b 使用松弛方法之前和之后的矩形的局部假設(shè)。第二列表示圖片的方向，直接相關(guān)的感知在下一列顯示。

木偶模型

該木偶由 15 個(gè)矩形部件組成，具有如下性質(zhì)和關(guān)系：

1.每一部分都有近端和遠(yuǎn)端。其中近端是指最接近頭頂?shù)囊欢恕?duì)于每個(gè)部件，沿近-遠(yuǎn)軸的長度必須大于其寬度。

2.軀干必須比所有的上肢部件都要寬，而每一個(gè)上肢部件又必須比與其相連的下肢部件寬。此外，頭部必須比頸部寬。

3.頭部的面積必須大于頸部，下肢面積必須大于雙手或雙腳。

4.相連的部件必須以正確的方式重疊。每個(gè)部件只能指定一個(gè)區(qū)域是否重疊，而不能指定多個(gè)區(qū)域。大腿和小腿之間連接的規(guī)范如圖2所示，圖2c展示了一些正確重疊的例子和存在近似誤差的例子。

圖2a 四個(gè)區(qū)域的感知

表2b 展示膝蓋區(qū)域關(guān)系的定義

圖2c 兩個(gè)令人滿意的膝關(guān)節(jié)例子(上)和三個(gè)有近似誤差的例子（下）。箭頭表示遠(yuǎn)端+近端方向。大腿總是這兩條腿中較寬的那條。

木偶模型是非常隨意的，但是必須使用比簡單連接更復(fù)雜的規(guī)則來避免出現(xiàn)如圖3所示的情況。一種比較靈活的方式是只要其余部件仍是合理的，允許擴(kuò)展一些連接或比例。這方面的影響將會(huì)在后面進(jìn)行討論。

圖3 一種矩形的配置，具有與木偶相同的連通性圖，但具有不同的關(guān)系和比例

不完全木偶

感知器是一種數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)可以表示木偶部件的矩形解釋，并且有插槽，該插槽被其他相關(guān)聯(lián)的感知器所填充。關(guān)聯(lián)關(guān)系也由數(shù)據(jù)結(jié)構(gòu)顯式地表示，數(shù)據(jù)結(jié)構(gòu)有兩個(gè)點(diǎn)，每個(gè)點(diǎn)對(duì)應(yīng)一個(gè)相關(guān)的感知器。

當(dāng)圖中沒有完整的木偶時(shí)，會(huì)發(fā)現(xiàn)存在不完整的木偶，即一些感知器中有空插槽的木偶。如果給程序一些評(píng)估不完整木偶的方法，那么它可以做同樣的事情，這樣當(dāng)有更好的選擇時(shí)，它就可以避免糟糕的全局解釋。目前，滿足以下約束條件，并且擁有最多關(guān)聯(lián)關(guān)系則被定義為最好的木偶：

1.一個(gè)矩形只能表示一個(gè)部件。

2.除了大腿和上臂可以有兩個(gè)插槽外，沒有一個(gè)插槽可以由多個(gè)關(guān)系填充。

3. 任何類型的部件被實(shí)例化的次數(shù)都不能超過它在模型中出現(xiàn)的次數(shù)，例如，不能有兩條以上的大腿。

4.除非感知器存在，否則關(guān)系不存在。

改善局部網(wǎng)絡(luò)結(jié)構(gòu)

由于木偶的潛在不完整性導(dǎo)致很難排除局部的任何感知，因此采用替代方法，從強(qiáng)烈暗示特定感知器的局部配置開始管理它們。在這些核心元素中，通過嘗試填充與已存在的感知相關(guān)的空閑時(shí)隙來增長網(wǎng)絡(luò)。

如果這樣做失敗了，并且有合適的重疊矩形，則使用與新創(chuàng)建的感知器的關(guān)系，而這些新感知器的其他槽作為進(jìn)一步的生長點(diǎn)。如果模型的最佳實(shí)例化至少包含一個(gè)核心元素，則生成的網(wǎng)絡(luò)將包含所有必需的感知器。它還將包含許多其他的槽，一些槽將由幾個(gè)競(jìng)爭關(guān)系來填充，見圖1b。然而，一般來說，以這種方式發(fā)展起來的網(wǎng)絡(luò)要比由所有局部可能性組成的網(wǎng)絡(luò)小得多。

感知器之間的相互作用

并行處理必須生成非常多的局部可能性結(jié)果以確保生成正確的可能性結(jié)果，因此除非有快速排除不正確結(jié)果的方法，否則將不具有并行計(jì)算的時(shí)間優(yōu)勢(shì)。簡單的本地競(jìng)爭是行不通的，因?yàn)檎_的感知有時(shí)會(huì)有一個(gè)更好的局部選擇。但是如果感知器也被允許通過他們的關(guān)系互相幫助，那么可能會(huì)通過網(wǎng)絡(luò)傳播來幫助一個(gè)全局一致但局部較差的感知，見圖4。

這種類型的系統(tǒng)，其中全局模式從局部相互作用中產(chǎn)生，作為格式塔現(xiàn)象的基礎(chǔ)是有吸引力的，但如果系統(tǒng)快速達(dá)到穩(wěn)定狀態(tài)并且有一些最佳模式出現(xiàn)，那么這種系統(tǒng)很有意義。

圖4 松弛法是將A解釋為大腿，而局部最優(yōu)選擇的結(jié)果是小腿。

偏好約束網(wǎng)絡(luò)

找到最好的木偶，相當(dāng)于要從節(jié)點(diǎn)是感知器的網(wǎng)絡(luò)中提取，并且關(guān)要滿足某些約束的最佳子網(wǎng)。如果子網(wǎng)的值可以表示為其各個(gè)節(jié)點(diǎn)的首選項(xiàng)的和，并且如果約束等于可能狀態(tài)空間中的超平面，則可以使用松弛方法。每個(gè)節(jié)點(diǎn)都有一個(gè)介于0和1之間的實(shí)數(shù)，也即可信度。

該值不應(yīng)與偏好相混淆，可以解釋為節(jié)點(diǎn)正確的概率，即最佳一致子網(wǎng)的一部分。約束條件是可信度之間的不等式。例如，n或m表示為，其中c(n)是節(jié)點(diǎn)n的可信度。

節(jié)點(diǎn)的可信度可以表示為多維空間的軸。可信度分布是空間中的一個(gè)點(diǎn)，是對(duì)每個(gè)平面的響應(yīng)。為了滿足不等式約束條件，一個(gè)點(diǎn)必須位于相關(guān)的超平面或其一側(cè)。滿足所有約束條件的狀態(tài)稱為合法狀態(tài)，超出空間區(qū)域就是凸多面體，因?yàn)樗浅矫婧桶肟臻g的交集。

應(yīng)用關(guān)系到木偶圖片

對(duì)于木偶中不完整的部分，給出了對(duì)該木偶最佳實(shí)例化的定義。關(guān)于可信度的約束條件表達(dá)式如下：

1.矩形的感知關(guān)系式：

2.競(jìng)爭關(guān)系表達(dá)式：

3.模型中出現(xiàn)n次部件的感知關(guān)系式：

4.兩個(gè)感知器p,q之間的關(guān)系式：

討論

用來揭示松弛法原理的任務(wù)，在許多方面都得到了簡化。一個(gè)容易改進(jìn)的點(diǎn)是缺乏對(duì)膝關(guān)節(jié)和肘關(guān)節(jié)連接角度的關(guān)注。一個(gè)好的木偶模型需要肘部向一個(gè)方向彎曲，膝蓋能向另一個(gè)方向彎曲，從而利用這些知識(shí)，制造出更好的木偶。這種類型的約束的理論意義在于它是非局部的，就像對(duì)于上下文無關(guān)語句來說數(shù)字一致性規(guī)范是存在問題的(Lyons 1968)。

針對(duì)上述問題，解決方法是引入全局節(jié)點(diǎn)來表示木偶的邊。這些邊節(jié)點(diǎn)之間通過排他或約束進(jìn)行相互關(guān)聯(lián)，每個(gè)關(guān)聯(lián)通過物體隱含約束條件關(guān)聯(lián)到其他全局邊節(jié)點(diǎn)。現(xiàn)在最好的實(shí)例是有兼容的膝部和肘部。

某情況下，這是一個(gè)太過苛刻的約束條件，因?yàn)樵诂F(xiàn)實(shí)中有折斷的胳膊肘總比沒有的好。因此，作者引入了沒有額外限制的可選弱關(guān)聯(lián)，這樣會(huì)和有較強(qiáng)關(guān)聯(lián)的相互沖突。所以，如果有更好的偏好設(shè)置，好的手肘要優(yōu)于差的手肘，但是差的手肘不會(huì)優(yōu)于任何其他手肘。