എൻട്രോപ്പി: അടിസ്ഥാന തത്വങ്ങളിൽ നിന്ന്

2025, ജനുവരി 1

എൻട്രോപ്പി എന്ന ആശയം എനിക്ക് അത്യന്തം ആകർഷകമായി തോന്നുന്നു. എന്നാൽ, $\sum p_{i} lo g \frac{1}{p _{i}}$ എന്ന സൂത്രവാക്യത്തെ, പ്രിഫിക്സ് ഫ്രീ കോഡുകൾ, വിവരശേഖരണം തുടങ്ങിയ “അന്തർബോധപരമായ” വിശദീകരണങ്ങളുമായി ബന്ധിപ്പിക്കുന്നത് തീർച്ചയായും സ്പഷ്ടമല്ല. ഇവിടെ, ഈ ആശയത്തിലേക്ക് സ്വതന്ത്രമായി എത്തിച്ചേരാനുള്ള രണ്ട് വഴികൾ ഞാൻ പരിശോധിക്കാൻ ആഗ്രഹിക്കുന്നു.

വിവരത്തിന്റെ സവിശേഷതകൾ

നമുക്ക് ഒരു ഫംഗ്ഷൻ $I$ നിർവചിക്കണമെന്ന് കരുതുക, അത് ഒരു സംഭവത്തിന്റെ വിവരശേഷി പ്രതിനിധീകരിക്കുന്നു. സംഭവത്തിന്റെ പ്രത്യേക വിശദാംശങ്ങൾ മാറ്റിനിർത്തി, ഒരു സംഭവത്തെ മറ്റൊന്നുമായി താരതമ്യം ചെയ്യാൻ നമുക്ക് ഉപയോഗിക്കാവുന്ന ഒരു അളവ് അതിന്റെ സംഭാവ്യതയാണ്. അതിനാൽ, $I$ ഒരു പ്രോബബിലിറ്റി $p \in [0, 1]$ ൽ നിന്ന് $R$ ലേക്കുള്ള ഒരു മാപ്പിംഗ് ആകാം. ഈ ചട്ടക്കൂട് കണക്കിലെടുക്കുമ്പോൾ, ഇനിപ്പറയുന്ന ആവശ്യകതകൾ സാമാന്യബുദ്ധിക്ക് അനുയോജ്യമാണ്:

$I (1) = 0$ . ഒരു സംഭവം തീർച്ചയായും സംഭവിക്കുകയാണെങ്കിൽ, അത് വളരെ രസകരമല്ല, നമുക്ക് വളരെ കുറച്ച് വിവരമേ നൽകൂ.
$I$ തുടർച്ചയായതും $[0, 1]$ എന്ന ഇടവേളയിൽ ഏകതാനമായി കുറയുന്നതുമായിരിക്കണം. കൂടുതൽ സാധാരണമായ ഒരു സംഭവം കുറച്ച് വിവരം നൽകുന്നു.
$p$ , $q$ എന്നീ സംഭാവ്യതകളുള്ള രണ്ട് സ്വതന്ത്ര സംഭവങ്ങൾക്ക് $I (p) + I (q)$ വിവരശേഷി ഉണ്ടായിരിക്കണം.

അവസാനത്തെ ആവശ്യകതയാണ് ഏറ്റവും പ്രധാനമായത്. നിർവചനം അനുസരിച്ച്, രണ്ട് സ്വതന്ത്ര സംഭവങ്ങൾ സംഭവിക്കാനുള്ള സംഭാവ്യത $pq$ ആണ്. അതിനാൽ

I (pq) = I (p) + I (q) .

ഫംഗ്ഷൻ തുടർച്ചയായതായിരിക്കണമെന്നതിനാൽ, ഇത് ഇനിപ്പറയുന്നവയ്ക്ക് മാത്രമേ നിലനിൽക്കൂ:

I (p) = c lo g p .

$I$ ഏകതാനമായി കുറയുന്നതായിരിക്കണമെങ്കിൽ,

\frac{d I}{d p} = c / p

നെഗറ്റീവ് ആയിരിക്കണം. $p$ പോസിറ്റീവ് ആയതിനാൽ, $c$ നെഗറ്റീവ് ആയിരിക്കണം. $c^{'} = - c$ എന്ന് കൊടുക്കുക

I (p) = c^{'} lo g \frac{1}{p}

$lo g_{a} b = \frac{l o g b}{l o g a}$ ആയതിനാൽ, ഡിനോമിനേറ്റർ ഒരു സ്ഥിരാങ്കമായതിനാൽ, $c^{'}$ നെ ലോഗരിതത്തിന്റെ അടിസ്ഥാനം എൻകോഡ് ചെയ്യുന്നതായി കണക്കാക്കാം. സൗകര്യത്തിനായി, $c^{'}$ 1 ആയി കൊടുക്കുകയും $lo g$ എന്നത് അടിസ്ഥാന-2 ലോഗരിതം സൂചിപ്പിക്കുകയും ചെയ്യുന്നു.

എൻട്രോപ്പി എന്നത് ഒരു വിതരണം $p = (p_{1}, p_{2}, \dots, p_{n})$ എന്നതിന് മുകളിലുള്ള $I$ യുടെ പ്രതീക്ഷിത മൂല്യം മാത്രമാണ്

H (p) = i = 1 \sum n p_{i} lo g \frac{1}{p _{i}}

തുടർച്ചയുടെ പ്രചോദനത്തോടെ $H (0) = 0 lo g \frac{1}{0} = 0$ എന്നും നമ്മൾ അനുമാനിക്കുന്നു.

ഉദാഹരണത്തിന്, ബെർണൂലി റാൻഡം വേരിയബിൾ $B_{p}$ പരിഗണിക്കുക, അത് $p$ സംഭാവ്യതയോടെ $1$ എന്ന മൂല്യവും $1 - p$ സംഭാവ്യതയോടെ $0$ എന്ന മൂല്യവും എടുക്കുന്നു. അതിന്റെ എൻട്രോപ്പി പ്ലോട്ട് ചെയ്താൽ

പ്ലോട്ടിംഗ് കോഡ്

from pathlib import Path

import numpy as np
import plotly.graph_objects as go

# Function to calculate the entropy of a Bernoulli variable
def bernoulli_entropy(p):
    return -p * np.log2(p) - (1 - p) * np.log2(1 - p)

# Generate values for p from 0 to 1
p_values = np.linspace(0.01, 0.99, 100)
entropy_values = bernoulli_entropy(p_values)

# Shared trace for both themes
trace = go.Scatter(
    x=p_values,
    y=entropy_values,
    mode="lines",
    name="Entropy",
    line=dict(color="red"),
)

# Output directory (repo root/static)
output_dir = Path(__file__).resolve().parents[3] / "static"
output_dir.mkdir(parents=True, exist_ok=True)

themes = [
    {
        "template": "plotly_white",
        "font_color": "#111111",
        "axis": {
            "linecolor": "#111111",
            "tickcolor": "#111111",
            "tickfont": {"color": "#111111"},
            "title_font": {"color": "#111111"},
            "showgrid": True,
            "gridcolor": "rgba(17, 17, 17, 0.2)",
            "gridwidth": 1,
            "zeroline": False,
        },
        "filename": "bernoulli_entropy_plot_light.html",
    },
    {
        "template": "plotly_dark",
        "font_color": "#f5f5f5",
        "axis": {
            "linecolor": "#f5f5f5",
            "tickcolor": "#f5f5f5",
            "tickfont": {"color": "#f5f5f5"},
            "title_font": {"color": "#f5f5f5"},
            "showgrid": True,
            "gridcolor": "rgba(245, 245, 245, 0.2)",
            "gridwidth": 1,
            "zeroline": False,
        },
        "filename": "bernoulli_entropy_plot_dark.html",
    },
]

for theme in themes:
    fig = go.Figure(data=[trace])
    fig.update_layout(
        title="Entropy of a Bernoulli Random Variable",
        xaxis_title="p",
        yaxis_title="Entropy",
        template=theme["template"],
        font=dict(color=theme["font_color"]),
        paper_bgcolor="rgba(0, 0, 0, 0)",
        plot_bgcolor="rgba(0, 0, 0, 0)",
        xaxis=dict(showline=True, **theme["axis"]),
        yaxis=dict(showline=True, **theme["axis"]),
    )
    fig.write_html(output_dir / theme["filename"])

വിതരണം ഏകതാനമാകുമ്പോൾ അത് പരമാവധി ആയും, ഏകദേശം നിർണ്ണായകമാകുമ്പോൾ ഏറ്റവും കുറഞ്ഞതായും കാണാം.

പ്രിഫിക്സ്-ഫ്രീ കോഡുകൾ

നമുക്ക് $X = {X_{1}, \dots, X_{M}}$ എന്ന ചിഹ്നങ്ങളുടെ ഒരു കൂട്ടം ഉണ്ടെന്ന് കരുതുക, അത് ഒരു ബൈനറി ചാനലിലൂടെ അയയ്ക്കാൻ ആഗ്രഹിക്കുന്നു. ഓരോ തവണയും $1$ അല്ലെങ്കിൽ $0$ അയയ്ക്കാൻ കഴിയുന്ന വിധത്തിലാണ് ഞങ്ങൾ ചാനൽ നിർമ്മിക്കുന്നത്. $X$ -നായി ഒരു ഒപ്റ്റിമൽ എൻകോഡിംഗ് സ്കീം കണ്ടെത്താൻ ഞങ്ങൾ ആഗ്രഹിക്കുന്നു, ഒരു ആവശ്യകതയോടെ: അത് പ്രിഫിക്സ്-ഫ്രീ ആയിരിക്കണം.

ഒരു എൻകോഡിംഗ് ഫംഗ്ഷൻ $f : X \to {0, 1}^{+}$ നിർവചിക്കാം, അത് ചിഹ്നങ്ങളെ $\geq 1$ നീളമുള്ള ബൈനറി സ്ട്രിംഗുകളിലേക്ക് മാപ്പ് ചെയ്യുന്നു. ഒരു കോഡ് വാക്ക് മറ്റൊന്നിന്റെ പ്രിഫിക്സ് അല്ലെങ്കിൽ ഒരു എൻകോഡിംഗിനെ പ്രിഫിക്സ്-ഫ്രീ എന്ന് പറയുന്നു. ഉദാഹരണത്തിന്, ${0, 01}$ പ്രിഫിക്സ് ഫ്രീ അല്ല, കാരണം $0$ എന്നത് $01$ ന്റെ ഒരു പ്രിഫിക്സ് ആണ്. എന്നാൽ ${0, 10}$ ആണ്.

ഒരു പ്രിഫിക്സ് ഫ്രീ കോഡ് എന്നാൽ കോഡ് അദ്വിതീയമായി ഡീകോഡ് ചെയ്യാവുന്നതാണ് എന്നാണ്, ചിഹ്നങ്ങൾക്കിടയിൽ അധിക ഡിലിമിറ്ററുകളില്ലാതെ, അത് ഒരു ആവശ്യമായ സ്വഭാവമാണ്.

ഒരു ബൈനറി പ്രിഫിക്സ് കോഡ് ഒരു ബൈനറി ട്രീയാൽ അദ്വിതീയമായി നിർവചിക്കപ്പെടുന്നുവെന്നും ഞങ്ങൾ ശ്രദ്ധിക്കുന്നു:

പ്രിഫിക്സ് കോഡിന്റെ ബൈനറി ട്രീ — ഉറവിടം: https://leimao.github.io/blog/Huffman-Coding

ഇവിടെ റൂട്ട്-ടു-സിംബൽ പാത കോഡ് വാക്ക് നിർണ്ണയിക്കുന്നു, ചിഹ്നങ്ങൾ എല്ലായ്പ്പോഴും ഇലകളാണ്. ഇതുപോലുള്ള ഏത് നിർമ്മാണവും ഒരു പ്രിഫിക്സ് കോഡിലേക്ക് നയിക്കുന്നുവെന്ന് നിങ്ങൾ സ്വയം ബോധ്യപ്പെടുത്തുക.

$X$ എന്നതിന് മുകളിലുള്ള ഏത് പ്രിഫിക്സ് കോഡിന്റെയും പ്രതീക്ഷിക്കപ്പെടുന്ന കോഡ് വാക്ക് നീളം $L$ എന്നത് ഇനിപ്പറയുന്ന രീതിയിൽ പരിമിതപ്പെടുത്തിയിരിക്കുന്നുവെന്ന് ഞങ്ങൾ ഇപ്പോൾ കാണിക്കും:

H (X) \leq L < H (X) + 1.

ഇവിടെ $X$ എന്നത് $(p_{1}, \dots, p_{n})$ എന്ന സാധ്യതകളോടെ $X$ സെറ്റിൽ നിന്നുള്ള മൂല്യങ്ങൾ എടുക്കുന്ന ഒരു റാൻഡം വേരിയബിളാണ്. ഏറ്റവും പ്രധാനമായി, $X$ ന്റെ എൻട്രോപ്പി ഒരു വിതരണം എത്രമാത്രം കംപ്രസ് ചെയ്യാമെന്നതിനുള്ള താഴ്ന്ന പരിധിയാണ്, അല്ലെങ്കിൽ തുല്യമായി, അതിൽ എത്ര വിവരങ്ങൾ അടങ്ങിയിരിക്കുന്നു എന്നതിനുള്ള താഴ്ന്ന പരിധിയാണ്.

ക്രാഫ്റ്റിന്റെ അസമത്വം

ക്രാഫ്റ്റ് അസമത്വ തെളിവിന്റെ ബൈനറി ട്രീ ദൃശ്യവൽക്കരണം — ക്രാഫ്റ്റിന്റെ അസമത്വത്തിനുള്ള ഉദാഹരണ വൃക്ഷം

$l_{i}$ എന്നത് $i$ ആം കോഡ് വാക്കിന്റെ നീളമായിരിക്കട്ടെ. കോഡ് പ്രിഫിക്സ്-ഫ്രീ ആണെങ്കിൽ:

i = 1 \sum M 2^{- l_{i}} \leq 1

തെളിവ്:

$l_{max}$ ഏറ്റവും നീളമുള്ള കോഡ് വാക്കിന്റെ നീളമായിരിക്കട്ടെ. നമുക്ക് ശ്രദ്ധിക്കാം:

$l_{max}$ ലെവലിൽ പരമാവധി $2^{l_{max}}$ നോഡുകൾ ഉണ്ടാകും.
$l_{i}$ നീളമുള്ള ഏതൊരു കോഡ് വാക്കിനും, $l_{max}$ ലെവലിൽ $2^{l_{max} - l_{i}}$ സന്തതികൾ ഉണ്ടാകും.
ഓരോ കോഡ് വാക്കിന്റെയും സന്തതികളുടെ കൂട്ടങ്ങൾ പരസ്പരം വിഭജിക്കുന്നവയാണ് (ഒരു കോഡ് വാക്ക് മറ്റൊന്നിന്റെ സന്തതിയാകില്ല എന്നതിനാൽ).

ഇവയിൽ നിന്ന് ലഭിക്കുന്നത്:

⟹ i \sum 2^{l_{max} - l_{i}} \leq 2^{l_{max}} i \sum 2^{- l_{i}} \leq 1.

എന്തുകൊണ്ട് $=$ എന്നതിനു പകരം $\leq$ ? കാരണം, $l_{max}$ ലെവലിലുള്ള ഒരു നോഡ് ഏതൊരു കോഡ് വാക്കിന്റെയും സന്തതിയാകാതിരിക്കാം (കോഡ് ${10, 11}$ എന്ന വൃക്ഷം പരിഗണിക്കുക)!

L-ന്റെ താഴ്ന്ന പരിധി

ഇനി, പ്രതീക്ഷിക്കുന്ന കോഡ് വാക്ക് നീളം പരിഗണിക്കാം

L = i \sum p_{i} l_{i}

എൻട്രോപ്പി $L$ -ന്റെ താഴ്ന്ന പരിധിയാണെന്ന് കാണിക്കാം, അതായത്

H (X) \leq L ⟺ L - H (X) \geq 0

തെളിവ്:

L - H (X) = i \sum p_{i} l_{i} + i \sum p_{i} lo g p_{i} = - i \sum p_{i} lo g 2^{- l_{i}} + i \sum p_{i} lo g p_{i} = - i \sum p_{i} lo g 2^{- l_{i}} + i \sum p_{i} lo g p_{i} + i \sum p_{i} lo g (j \sum 2^{- l_{j}}) - i \sum p_{i} lo g (j \sum 2^{- l_{j}}) = i \sum p_{i} lo g \frac{p _{i}}{2 ^{- l_{i}} / \sum _{j} 2 ^{- l_{j}}} - i \sum p_{i} lo g (j \sum 2^{- l_{j}}) = D_{K L} [p ∣∣ q] + lo g \frac{1}{c} \geq 0

ഇവിടെ അവസാനത്തെ അസമത്വം രണ്ട് കാരണങ്ങളാൽ: 1) KL ഡൈവർജൻസ് നോൺ-നെഗറ്റീവ് ആയതിനാൽ, 2) ക്രാഫ്റ്റിന്റെ അസമത്വം മൂലം $c \leq 1$ ആയതിനാൽ. ശ്രദ്ധിക്കേണ്ട ഒരു കാര്യം, $l_{i} = - lo g p_{i}$ ആണെങ്കിൽ $L = H (X)$ ആകും, അത് സിദ്ധാന്തപരമായ ഏറ്റവും കുറഞ്ഞ മൂല്യമാണ്. എന്നാൽ ഈ മൂല്യം എല്ലായ്പ്പോഴും കൈവരിക്കാൻ കഴിയാത്തതിന് കാരണം $- lo g p_{i}$ ഒരു പൂർണ്ണസംഖ്യയാകണമെന്നില്ല എന്നതാണ്, അത് വ്യക്തമായും ആവശ്യമാണ്.

L-ന്റെ ഒരു മുകൾ പരിധി

നീളങ്ങൾ

l_{i} = ⌈ - lo g p_{i} ⌉

ഉള്ള ഒരു പ്രിഫിക്സ് കോഡ് നിർമ്മിക്കാൻ സാധിക്കും, കാരണം അവ ക്രാഫ്റ്റിന്റെ അസമത്വം തൃപ്തിപ്പെടുത്തുന്നു:

i \sum 2^{- l_{i}} \leq i \sum 2^{l o g p_{i}} = 1

സീലിംഗ് ഫംഗ്ഷന്റെ നിർവചനം അനുസരിച്ച്

- lo g p_{i} \leq l_{i} < - lo g p_{i} + 1

$p$ -ന്റെ പ്രതീക്ഷ എടുക്കുമ്പോൾ, നമുക്ക് ലഭിക്കുന്നത്

- \sum p_{i} lo g p_{i} \leq \sum p_{i} l_{i} < - \sum p_{i} lo g p_{i} + 1 ⟹ H (X) \leq L < H (X) + 1

ഇത് $H (X) + 1$ എന്നത് L-ന്റെ ഒരു നല്ല മുകൾ പരിധിയാണെന്ന് കാണിക്കുന്നു!

സംഗ്രഹത്തിൽ, എൻട്രോപ്പി ഒരു താഴ്ന്ന പരിധിയും, ഒരു വിതരണം ഒരു പ്രിഫിക്സ് കോഡായി എൻകോഡ് ചെയ്യാൻ ആവശ്യമായ ബിറ്റുകളുടെ ശരാശരി എണ്ണത്തിനുള്ള ഒരു യുക്തിസഹമായ കണക്കാണ്.

അവലംബങ്ങൾ

അലോൺ ഓർലിറ്റ്സ്കി യുടെ ഇസിഇ 255എ പ്രഭാഷണങ്ങൾ, യുസിഎസ്ഡി
കവർ, ടി. എം., & തോമസ്, ജെ. എ. (2006). ഇൻഫർമേഷൻ തിയറിയുടെ ഘടകങ്ങൾ. വൈലി-ഇന്റർസയൻസ്.

✦ ഈ ലേഖനത്തിന്റെ ആശയരൂപീകരണം, ഗവേഷണം, എഴുത്ത്, അല്ലെങ്കിൽ എഡിറ്റിംഗ് എന്നിവയിൽ LLM-കൾ ഉപയോഗിച്ചിട്ടില്ല.