Claude Shannon 於 Information Theory 研究中提出熵(entropy)的概念,可以說是影響後續機器學習(machine learning)發展相當重要的概念。

熵看似難以理解,但其實是 1 個很簡單的概念,只要了解其背後的意義就能夠輕鬆上手。

熵(音同商),簡而言之,用以衡量一組資料的不確定性(uncertainty)。

假設有 1 枚硬幣 2 面都是人頭,那麼不管如何投擲,我們都能夠確定它的結果是人頭,因此毫無不確定性可言,那麼熵值就會是 0 。

假設有 1 枚硬幣 正面人頭,背面為字,那麼我們有 50% 的機率猜中其投擲結果,因此該情況下具有不確定性,其熵值為 1 。

假設有 2 枚硬幣,那麼我們約有 33% 的機率猜中其投擲結果(正正、反反、正反),該情況的不確定性相對於只有 1 枚硬幣而言更高,其熵值約為 1.58 。

可以看到隨著不確定性增加,熵值也會增加。

不確定性也可能會造成混亂的局面,不確定性越高代表越難預測結果,因此結果越混亂,所以我們也能夠透過熵值衡量資料分散、混亂的情況。例如,100 個從 0 到 1000 的隨機整數資料集與 100 個從 0 到 3 的隨機整數資料集相比, 100 個從 0 到 1000 的隨機整數資料集的熵值會相對較高,其原因在於該資料集的每 1 筆資料有 1000 種可能,導致該資料集最多有 100 種不同的值,而另一資料集中最多也只有 3 種不同的值,不論數值的分佈、混亂程度都遠遠不及 100 個從 0 到 1000 的隨機整數資料集(而且審視該 2 個資料集時,也能夠明顯感覺到其中 1 個較為混亂)。

了解熵的意義之後,對於熵的公式就會較有感覺:

公式來源

P(x) 代表 x 出現的機率,例如 1 組數據 [1, 2, 2, 3, 3, 4] ,其中數字 1, 4 只出現 1 次,其機率皆為 1/6 , 而數字 2, 3 都出現 2 次,其機率皆為 2/6

P(1) = 1/6
P(4) = 1/6
P(2) = 2/6
P(3) = 2/6

因此前述數據組的熵值為:

-(1/6 * log2(1/6)) -(2/6 * log2(2/6)) -(2/6 * log2(2/6)) -(1/6 * log2(1/6))
= 1.9182958340544896

而 Entropy 的關鍵部分在於 P(x) * log(P(x)) 的數學意義:某資料出現的機率越低,在 log 的加成下該數值會提高,該數值可以代表人們看到這個資料的驚訝(surprise)程度,例如 1 組數據平常數值都是 1 或 2,但是某一天卻異常出現 99 時,我們就會感到驚訝),當越多令人驚訝的情況出現,整體的不確定性/混亂程度就會提高。

以下為用 Python 實作 Shannon Entropy 的程式碼範例:

import math

from collections import Counter


def shannon_entropy(s):
    counter = Counter()
    for c in s:
        counter[c] +=1
    total = sum(counter.values())

    entropy = 0.0
    for k, v in counter.items():
        entropy -= (v / total) * math.log2(v / total)
    return entropy

當然,也可以用 scipy 所提供的 entropy 函式實作,只是我們必須把每個元素的機率事先計算好:

from collections import Counter
from scipy.stats import entropy


def shannon_entropy(s):
    counter = Counter()
    for c in s:
        counter[c] +=1
    total = sum(counter.values())
    return entropy([v / total for v in counter.values()], base=2)

熵值的應用

熵值可用以監測數據變動的情況,譬如熵值突然變很高或變很低時,多半代表數據有狀況發生(但不一定代表異常),此時就可對該數據組進行查驗。

資訊安全相關研究也會以熵值判斷可執行檔(executable)是否被加密/加殼(Executable compressors 或稱 software packers),其原理在於經過加密或加殼的程式,其熵值通常比一般程式高。

此外,熵值也可用以評估決策樹(decision tree)的建構,其原理在於資料經過分類節點後,分類的結果如果越混亂越不明確,其熵值將會越高,就代表分類效果不好,所以我們可以透過熵值衡量分類節點的效用,效用如果不好,可以進行更換或者移除,如有興趣詳見 Information gain in decision trees

除了上述提到的應用之外,熵也有其他的實際應用,有興趣的人可以透過 Google 大神進行更多深入研究。

以上!

References