摘要

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

介紹

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

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

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

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

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

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

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

木偶模型

該木偶由 15 個矩形部件組成，具有如下性質和關系：

1.每一部分都有近端和遠端。其中近端是指最接近頭頂的一端。對于每個部件，沿近-遠軸的長度必須大于其寬度。

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

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

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

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

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

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

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

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

不完全木偶

感知器是一種數據結構，該數據結構可以表示木偶部件的矩形解釋，并且有插槽，該插槽被其他相關聯的感知器所填充。關聯關系也由數據結構顯式地表示，數據結構有兩個點，每個點對應一個相關的感知器。

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

1.一個矩形只能表示一個部件。

2.除了大腿和上臂可以有兩個插槽外，沒有一個插槽可以由多個關系填充。

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

4.除非感知器存在，否則關系不存在。

改善局部網絡結構

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

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

感知器之間的相互作用

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

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

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

偏好約束網絡

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

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

節(jié)點的可信度可以表示為多維空間的軸?？尚哦确植际强臻g中的一個點，是對每個平面的響應。為了滿足不等式約束條件，一個點必須位于相關的超平面或其一側。滿足所有約束條件的狀態(tài)稱為合法狀態(tài)，超出空間區(qū)域就是凸多面體，因為它是超平面和半空間的交集。

應用關系到木偶圖片

對于木偶中不完整的部分，給出了對該木偶最佳實例化的定義。關于可信度的約束條件表達式如下：

1.矩形的感知關系式：

2.競爭關系表達式：

3.模型中出現n次部件的感知關系式：

4.兩個感知器p,q之間的關系式：

討論

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

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

某情況下，這是一個太過苛刻的約束條件，因為在現實中有折斷的胳膊肘總比沒有的好。因此，作者引入了沒有額外限制的可選弱關聯，這樣會和有較強關聯的相互沖突。所以，如果有更好的偏好設置，好的手肘要優(yōu)于差的手肘，但是差的手肘不會優(yōu)于任何其他手肘。