[發明專利]組合的隨機性邏輯

有效

• 申請號: 200980116076.8
• 申請日: 2009-03-04
• 公開（公告）號: CN102016616A
• 公開（公告）日: 2011-04-13
• 發明（設計）人: 維卡什·庫馬·曼西格卡;艾瑞克·邁克爾·喬納斯
• 申請（專利權）人: 麻省理工學院
• 主分類號: G01R31/28
• 分類號: G01R31/28
• 代理公司: 北京東方億思知識產權代理有限責任公司 11258
• 代理人: 李曉冬;南霆

背景技術

很多計算問題可以被歸類為確定性(deterministic)問題或隨機性(stochastic)問題。一般，在確定性問題中，問題的“答案”或者問題的解答的下一個狀態是可以基于輸入值和問題的當前狀態確定地計算出來的。一般，在隨機性問題中，問題的“答案”或者問題的解答的下一個狀態是不確定的，并且是根據概率分布來定義的。

當多個可能事件中的任意一個事件可能已經生成了所觀察到的場景時，通常在現實世界中發生的一類隨機性問題出現了。可以收集有關存在的場景的數據，并且可以使用該數據來計算所觀察到的場景由可能事件中的每一個事件導致的概率。基于所確定的概率，可以做出判決。例如，可以基于最可能的事件實際導致了場景的出現的假設而做出判決。當然，在更復雜的場景中，判決可以通過其他途徑做出，諸如，基于概率對特定的判決將導致好的還是不好的結果的預期進行評估。

圖像分析是包括隨機性問題的領域的示例。在一個立體視覺問題中，兩個不同的圖像可以由位置相近的兩個數字攝像機生成(諸如，當針對機器人技術問題對人眼進行近似時)。期望基于圖像本身來確定到圖像中的特定物體的距離。每個立體圖像代表了對于從物體傳播到攝像機的光的測量。由于在光從物體反射出來時將在可以預測的路徑中傳播，所以反射光的物體的位置似乎可以被確定地計算出來。然而，實際上，很多因素會影響在攝像機處測量出來的實際的光。物體的形狀、大小和表面性質以及光源的位置、強度和其他性質可以影響測量出的結果。所以，距離攝像機不同距離處的大量不同物體中的任意一個物體可以生成相同或者類似的測量值。

因此，當立體圖像分析被當作隨機性問題時，計算出的是特定位置中的特定物體導致測量的圖像產生的概率。此數據例如可以被用來引導使用立體視覺系統的機器人。如同最可能的物體實際存在一樣，機器人的控制算法可以簡單地對通過圖像的隨機性分析所提供的數據進行反應。更復雜的控制算法可以引導機器人最大化機器人將不受物體的困擾而到達它希望的目的地的預期，或者最小化機器人將由于物體的碰撞而被損壞的預期。

文本分析是隨機性問題的另一個示例：給定文檔的文本中的一組單詞，可能期望識別出文檔的主題。文檔中的該組單詞定義了由大量事件中的任意一個事件創建的場景。具體地，文檔可能是關于大量主題中的任意一個主題的。類似地，如果文檔分析的要點在于確定作者的觀點，則大量觀點中的任意一個觀點將會導致在文檔中被找出的這些單詞。當被當作隨機性問題時，可以確定與諸如文檔描述特定主題或者作者贊成特定觀點之類的這些事件相關聯的概率。這些概率然后可以被用來判斷諸如是否響應于特定的搜索查詢而返回文檔或者如何對文檔編目錄等等。

其他問題類似地遵循這種模式并且可以通過確定可能導致特定觀察到的場景出現的事件的概率來解決。這些問題一般是以條件概率密度函數為特征的。條件概率密度函數定義了一組事件中假設特定場景存在的事件的概率。根據告知什么場景存在的觀察數據以及概率密度函數，該組事件中每個事件導致所觀察的場景出現的概率可以被計算出來。

當期望確定定義場景的變量的值，但是這些變量的值具有隨機成分時，第二種隨機性問題出現。這可能在變量不能被直接觀察出來的很多情況中出現，例如，當它們描述所關注的化學系統的微觀結構時，或者當它們描述生物、文本或者人口統計數據的聚類時。在所有這些設置中，盡管變量不能被確定地指定，但是可以根據概率分布來對它們進行描述。通過根據概率分布來選擇值，典型值可以被獲取用于抽查或者用在解決其他更大的隨機性問題中。

當理論上可以但是實際上很難計算場景中的一些參數值時，第三種隨機性問題出現。如果場景可以根據為實際的參數值分配高概率的概率分布來描述，則根據概率來選擇值將導致實際值的良好近似。廣泛使用的Monte?Carlo近似技術提供了這種隨機性問題的示例的豐富來源。

這些種類的問題中的每種問題的共同點在于它們都涉及到根據概率分布來生成一個或多個樣本。通常，這種處理比較復雜并且不能手工或者靠腦力完成；因此，計算機是解決隨機性問題所必需的。

使用常規計算機來解決隨機性問題的一種傳統方法是確定在概率分布下可能的一組可能事件，然后計算每個潛在的事件的概率。在立體視覺問題的背景下，這可能包括識別到物體的所有潛在的距離，并且計算每個距離是正確距離的概率。

這些概率一般是高度精確地計算出來的，以便保它們緊密地近似實際概率。因此，當隨機性問題被近似為確定性問題時，可以使用64比特的浮點處理來計算，從而使得每個事件發生(或者每個輸出為“正確”輸出的概率)的概率可以被以64比特的精確度計算并存儲。