Trending News: Palo Alto Firewall URL過濾 以及 Application Block Page群NP-Completeness異常檢測 問題分類異常檢測 方法評估異常檢測簡介 Anomaly Detection高斯消去法Vectors時間複雜度不同的Turing MachineTuring Machine熵 Entropy資訊測量符號Mutual InformationPalo Alto Firewall 防火牆 Policy 政策 設定Palo Alto 防火牆 NAT (Network Address Translation) 設定《研究生完全求生手冊》讀後心得：研究生必須學會的方法、秘訣與淺規則密碼系統 RSA 攻防中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性Square Multiply 演算法尤拉函數 Euler’s totient function整數複雜度量測如何 安裝 Palo Alto VM《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週五. 5 月 3rd, 2024
Trending News: Palo Alto Firewall URL過濾 以及 Application Block Page群NP-Completeness異常檢測 問題分類異常檢測 方法評估異常檢測簡介 Anomaly Detection高斯消去法Vectors時間複雜度不同的Turing MachineTuring Machine熵 Entropy資訊測量符號Mutual InformationPalo Alto Firewall 防火牆 Policy 政策 設定Palo Alto 防火牆 NAT (Network Address Translation) 設定《研究生完全求生手冊》讀後心得：研究生必須學會的方法、秘訣與淺規則密碼系統 RSA 攻防中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性Square Multiply 演算法尤拉函數 Euler’s totient function整數複雜度量測如何 安裝 Palo Alto VM《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週五. 5 月 3rd, 2024

熵 Entropy

目錄

我們在消息理論測量一段資訊所包含的資訊量其中一種會使用Entropy來計算。

定義

讓X作為一個discrete R.V. 並且表示成P(X)可以視作:

    \[ H_{b}(X) = -\sum_{x \in \mathbb{X}} P(x) \cdot log_{b}P(x) = \mathbb{E}[-log_{b}P(X)] = \mathbb{E}{p} [log_{b}\frac{1}{P(x)}] \]

  1. b如果選擇2就表示我們在測量bits，若b是e則表示在測量nats，所以這裡沒有直接寫2是因為可以透過換底公式來換成別的格式。
    換底公式: log_{b}P(x) = log_{b}a \cdot log_{a}P(x)，因此，H_{b}(X) = (log_{b}a) \cdot H_{a}(X)，不過我們在消息理論內幾乎都是在談b=2的情況。
  2. H(X)測量的是X剩餘的不確定性，把x所有的可能性平均起來
  3. H(X)不是一個隨機變數X的function，而是針對PMF隨機變數X分佈function進行量測
  4. 根據lim_{x \rightarrow 0} \> xlogx \rightarrow 0,定義 0log0 = 0,因此如果新增了0的機率並不會讓entropy有任何變化

範例

假設X有Bernoulli(p)的分佈，i.e., x = \begin{cases} H, & \mbox{with probability} & \mbox{P} \\ T, & \mbox{with probability} & \mbox{1-P} \end{cases} 在投擲硬幣的時候呈現這樣的分佈

    \[ H(X) = -P \cdot logP - (1-P)log(1-P) \triangleq H(P) \> binary \> entropy \]

我們觀察這個分佈圖

  1. H(P) \geq 0 在P=0或是1的情況時會發生 (在結果變成deterministic的時候發生代表全部的不確定性已經消失)
  2. H(P) \leq 1 在P = \frac{1}{2}的情況下會發生 (如果是一個公平的擲硬幣0跟1兩者最高機率都會是\frac{1}{2}的最大不確定性)
  3. H(P) = H(1-P) (P要稱為head或是tail都不重要，這裡要表達的是只要結果是0跟1的事件都可以使用這種方法)

另外有一些定理存在

  1. (Non-negativeness): H(X) \geq 0 成立若且唯若X是一個deterministic
  2. (Maximum entropy): 讓X是一個discrete隨機變數屬於有限的alphabet \mathbb{X}，存在H(X) \leq log|\mathbb{X}若且唯若X有uniform distribution的特性在\mathbb{X}之上

證明：

  1. (Non-negativeness):

        \[ 0 \leq P(x) \leq 1 \Rightarrow \frac{1}{P(x)} \geq 1 \Rightarrow log\frac{1}{P(x)} \geq 0, \forall x \in \mathbb{X} \]

  2. (Maximum entropy): 讓\mathbb{X}' = {x \in \mathbb{X}, P(x) > 0} \subseteq \mathbb{X}, 可以得到

        \[ H(X) - log|\mathbb{X}| \leq H(X) - log|\mathbb{X}'| = -\sum_{x \in \mathbb{X}}P(x) \cdot logP(x) - log|\mathbb{X}'| \\ = -\sum_{x \in \mathbb{X}'} P(x) \cdot logP(x) - log|\mathbb{X}'| \cdot\sum_{x \in \mathbb{X}'}P(x) \\ = \sum_{x \in \mathbb{X}'} P(x) \cdot log\frac{1}{P(x)\cdot |\mathbb{X}'|} = log_{2}e \cdot \sum_{x \in \mathbb{X}'}P(x)ln\frac{1}{P(x)\cdot |\mathbb{X}'|} \\ \leq log_{2}e\sum_{x \in \mathbb{X}'}P(x)\cdot(\frac{1}{P(x)\cdot|\mathbb{X}'|}-1) \\ =log_{2}e(\sum_{x \in \mathbb{X}'}\frac{1}{|\mathbb{X}'|} - \sum_{x \in \mathbb{X}'}P(x) = 0 \]

等式成立若且唯若

  1. \mathbb{X}' = \mathbb{X}, i.e., P(x) > 0 \> \forall x \in \mathbb{X}
  2. \frac{1}{P(x)|\mathbb{X}'|} = 1 \Rightarrow P(x) = \frac{1}{|\mathbb{X}'|} \> \forall x \in \mathbb{X}'
    i.e., P(x) = \frac{1}{|\mathbb{X}|} \> \forall \> x \in \mathbb{X}

Scientia

我是Scientia，研究興趣包含Cryptology, Cryptographic Engineering, Security and Privacy, Computational Complexity, Quantum Cryptography, Cybersecurity, Hardware Security以及Anomaly Detection.

Related Posts

NP-Completeness
NP-Completeness

首先需要一個問題叫做布林公式(Boolean formula)會像：

    \[\phi = (\bar{x} \wedge y) \vee (x \wedge \bar{z})\]

裡面的每一個符號稱作variable，每一個variable可以給0或1的值就像在做.

Continue reading
時間複雜度
時間複雜度

通長在測量複雜度的時候會使用兩種分析方法：Worst-case analysisAverage-case analysis定義一個M是Deterministic Turing Machine並且會根據輸入決定停止規範M的執行時間或者時間複雜度可以表示成一個function…

Continue reading

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You Missed

資訊安全 防火牆

Palo Alto Firewall URL過濾 以及 Application Block Page

Palo Alto Firewall URL過濾 以及 Application Block Page
數學 數論

群

群
理論電腦科學 計算理論

NP-Completeness

NP-Completeness
異常檢測

異常檢測 問題分類

異常檢測 問題分類
異常檢測

異常檢測 方法評估

異常檢測 方法評估
異常檢測

異常檢測簡介 Anomaly Detection

異常檢測簡介 Anomaly Detection