ആദ്യ തത്വങ്ങളിൽ നിന്നുള്ള എൻട്രോപ്പി

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 ലോഗരിതം എന്ന് കരുതുക.

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

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$ മൂല്യം എടുക്കുന്നു. ഇതിന്റെ എൻട്രോപ്പി പ്ലോട്ട് ചെയ്താൽ

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

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)

# Create the plot
fig = go.Figure()

# Add the entropy trace
fig.add_trace(go.Scatter(x=p_values, y=entropy_values, mode='lines', name='Entropy', line=dict(color='red')))

# Update layout for dark mode
fig.update_layout(
    title='Entropy of a Bernoulli Random Variable',
    xaxis_title='p',
    yaxis_title='Entropy',
    template='plotly_dark'
)

# Save the plot to an HTML file
fig.write_html("bernoulli_entropy_plot.html")

ഡിസ്ട്രിബ്യൂഷൻ ഏകീകൃതമായിരിക്കുമ്പോൾ ഇത് പരമാവധി ആകുന്നു, ഏകദേശം നിശ്ചിതമായിരിക്കുമ്പോൾ ഇത് ഏറ്റവും കുറവാകുന്നു.

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

നമുക്ക് ഒരു കൂട്ടം ചിഹ്നങ്ങൾ $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$ എന്നത് $X$ സെറ്റിൽ നിന്ന് മൂല്യങ്ങൾ എടുക്കുന്ന ഒരു റാൻഡം വേരിയബിളാണ്, $(p_{1}, \dots, p_{n})$ എന്ന പ്രോബബിലിറ്റികളോടെ. ഏറ്റവും പ്രധാനമായി, $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-ന്റെ ഒരു നല്ല മുകളിലെ പരിധിയാണ്!

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

അവലംബങ്ങൾ

അലോൺ ഓർലിറ്റ്സ്കി ന്റെ ECE 255A ലെക്ചറുകൾ, UCSD
Cover, T. M., & Thomas, J. A. (2006). ഇൻഫർമേഷൻ തിയറിയുടെ ഘടകങ്ങൾ. Wiley-Interscience.

←

ഇന്ററാക്ടീവ് ഗൗസിയൻ മിശ്രണ മോഡലുകൾ