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

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-ന്റെ ഒരു നല്ല മേൽപ്പറ്റ പരിധിയാണ്!

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

അവലംബങ്ങൾ

Alon Orlitsky’s ECE 255A ലെക്ചറുകൾ, UCSD
Cover, T. M., & Thomas, J. A. (2006). ഇൻഫർമേഷൻ തിയറിയുടെ ഘടകങ്ങൾ. Wiley-Interscience.

←

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