Decoding Uncertainty in Communication: Exploring Prior Distributions and Coding Schemes
The Price of Uncertainty
in Communication
Brendan Juba
(Washington U., St. Louis)
with Mark Braverman (Princeton)
≈
≈
SINCE WE ALL
AGREE
ON A
PROB. DISTRIBUTION OVER
WHAT I MIGHT SAY, I CAN
COMPRESS
IT TO: “THE
9,232,142,124,214,214,123,845
TH
MOST LIKELY MESSAGE.
THANK YOU!”
1.
Encodings and
communication across
different priors
2.
Near-optimal lower
bounds for different priors
coding
3
Coding schemes
4
Bird
Chicken
Cat
Dinner
Pet
Lamb
Duck
Cow
Dog
“MESSAGES”
“ENCODINGS”
Communication model
5
RECALL:
(
, CAT)
E
Ambiguity
6
Bird
Chicken
Cat
Dinner
Pet
Lamb
Duck
Cow
Dog
Prior distributions
7
Bird
Chicken
Cat
Dinner
Pet
Lamb
Duck
Cow
Dog
Decode to a maximum likelihood message
Source coding
(compression)
•
Assume encodings are binary strings
•
Given a prior distribution P, message m,
choose minimum length encoding that
decodes to m.
8
FOR EXAMPLE,
HUFFMAN
CODES
AND
SHANNON-
FANO
(ARITHMETIC)
CODES
NOTE:
THE ABOVE SCHEMES
DEPEND ON THE
PRIOR
.
9
SUPPOSE ALICE AND BOB SHARE
THE SAME
ENCODING SCHEME
, BUT
DON’T
SHARE THE SAME
PRIOR…
P
Q
CAN
THEY COMMUNICATE??
HOW
EFFICIENTLY??
10
THE CAT.
THE
ORANGE
CAT.
THE ORANGE CAT
WITHOUT A HAT
.
Closeness and communication
•
Priors P and Q are
α-close
(
α
≥
1
) if
for every message m,
αP(m) ≥ Q(m) and αQ(m) ≥ P(m)
•
Disambiguation
and
closeness
together
suffice for communication:
If for every m’≠m, P[m|e] > α
2
P[m’|e], then:
Q[m|e] ≥
1
/
α
P[m|e] > αP[m’|e] ≥ Q[m’|e]
11
SO, IF ALICE
SENDS
e THEN
MAXIMUM
LIKELIHOOD DECODING
GIVES BOB m
AND
NOT
m’…
“
α
2
-disambiguated”
Construction of a coding scheme
(J-Kalai-Khanna-Sudan’11, Inspired by B-Rao’11)
Pick an infinite random string R
m
for each m,
Put (m,e)
E
⇔
e is a prefix of R
m
.
Alice encodes m by sending prefix of R
m
s.t.
m is
α
2
-disambiguated under P.
12
Gives an expected encoding length of at most
H(P) + 2log α + 2
Remark
Mimicking the disambiguation
property of
natural language
provided an
efficient
strategy for
communication.
13
1.
Encodings and
communication across
different priors
2.
Near-optimal lower
bounds for different
priors coding
14
Our results
1.
The JKKS’11/BR’11 encoding is near optimal
–
H(P) + 2log α – 3log log α – O(1) bits necessary
(
cf. achieved
H(P) + 2log α + 2
bits
)
2.
Analysis of positive-error setting
[Haramaty-Sudan’14]
:
If incorrect decoding w.p. ε is allowed—
–
Can achieve H(P) + log α + log 1/ε bits
–
H(P) + log α + log 1/ε – (9/2)log log α – O(1) bits
necessary for ε > 1/α
15
An ε-error
coding scheme.
(Inspired by J-Kalai-Khanna-Sudan’11, B-Rao’11)
Pick an infinite random string R
m
for each m,
Put (m,e)
E
⇔
e is a prefix of R
m
.
Alice encodes m by sending the prefix of R
m
of length log 1/P(m) + log α + log 1/ε
16
Analysis
Claim.
m is decoded correctly w.p. 1-ε
Proof.
There are at most 1/Q(m) messages
with Q-probability greater than Q(m) ≥ P(m)/α.
The probability that R
m’
for any one of these m’
agrees with the first log 1/P(m) + log α + log 1/ε ≥
log 1/Q(m)+log 1/ε bits of R
m
is at most εQ(m).
By a union bound, the probability that any of these
agree with R
m
(and hence could be wrongly chosen)
is at most ε.
17
Length lower bound 1—
reduction to
deterministic encodings
•
Min-max Theorem
:
it
suffices to exhibit
a
distribution over priors
for which
deterministic encodings
must be long
18
Length lower bound 2—
hard priors
19
log.
prob.
≈0
-log α
-2log α
m
*
S
Lemma 1:
H(
P
) =
O
(1)
α-
close
α-
close
Lemma 2
α
2
α
Length lower bound 3
—
short encodings have collisions
•
Encodings of expected length
< 2log α – 3log log α
encode
m
1
≠
m
2
identically with nonzero prob.
•
With nonzero probability over choice of
P
&
Q
,
m
1
,
m
2
∈
S
and
m
*
∈
{m
1
,
m
2
}
•
Decoding error with nonzero probability
☞
Errorless encodings have expected length
≥
2log α-3log log α = H(
P
)+2log α-3log log α-
O
(1)
20
Length lower bound 4
—
very
short encodings
often
collide
•
If the encoding has expected length
< log α + log 1/ε – (9/2)log log α
m
* collides with
∼
(ε log α)∙α other messages
•
Probability that our α draws for
S
miss
all
of these messages is < 1-2ε
•
Decoding error with probability >
ε
☞
Error-
ε
encodings have expected length
≥
H(
P
) + log α + log 1/ε – (9/2)log log α –
O
(1)
21
22
Recap.
We saw a variant of source coding
for which
(near-)optimal
solutions resemble
natural languages in interesting ways.
23
The problem.
Design a coding scheme E so that
for any sender and receiver with α-close prior
distributions, the communication length is
minimized.
(In expectation w.r.t. sender’s distribution)
Questions?
Delve into the intricate world of communication under uncertainty, where decoding messages accurately is paramount. Discover how prior distributions, encoding schemes, and closeness metrics influence the efficiency and effectiveness of communication between parties sharing different priors.
Uploaded on Sep 17, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The Price of Uncertainty in Communication Brendan Juba (Washington U., St. Louis) with Mark Braverman (Princeton)
SINCE WE ALL AGREE ON A PROB. DISTRIBUTION OVER WHAT I MIGHT SAY, I CAN COMPRESSIT TO: THE 9,232,142,124,214,214,123,845TH MOST LIKELY MESSAGE. THANK YOU!
1.Encodings and communication across different priors 2.Near-optimal lower bounds for different priors coding 3
Coding schemes MESSAGES Chicken Bird Duck Dinner Pet Lamb Cow Dog Cat ENCODINGS 4
Ambiguity Chicken Bird Duck Dinner Pet Lamb Cow Dog Cat 6
Prior distributions Chicken Bird Duck Dinner Pet Lamb Cow Dog Cat Decode to a maximum likelihood message 7
Source coding (compression) Assume encodings are binary strings Given a prior distribution P, message m, choose minimum length encoding that decodes to m. FOR EXAMPLE, HUFFMAN CODES AND SHANNON- FANO (ARITHMETIC) CODES NOTE: THE ABOVE SCHEMES DEPEND ON THE PRIOR. 8
SUPPOSE ALICE AND BOB SHARE THE SAME ENCODING SCHEME, BUT DON T SHARE THE SAME PRIOR P Q CAN THEY COMMUNICATE?? HOW EFFICIENTLY?? 9
THE ORANGE CAT. THE ORANGE CAT WITHOUT A HAT. THE CAT. 10
Closeness and communication Priors P and Q are -close ( 1) if for every message m, P(m) Q(m) and Q(m) P(m) Disambiguation and closeness together suffice for communication: 2-disambiguated If for every m m, P[m|e] > 2P[m |e], then: Q[m|e] 1/ P[m|e] > P[m |e] Q[m |e] SO, IF ALICE SENDS e THEN MAXIMUM LIKELIHOOD DECODING GIVES BOB m AND NOTm 11
Construction of a coding scheme (J-Kalai-Khanna-Sudan 11, Inspired by B-Rao 11) Pick an infinite random string Rm for each m, Put (m,e) E e is a prefix of Rm. Alice encodes m by sending prefix of Rm s.t. m is 2-disambiguated under P. Gives an expected encoding length of at most H(P) + 2log + 2 12
Remark Mimicking the disambiguation property of natural language provided an efficient strategy for communication. 13
1.Encodings and communication across different priors 2.Near-optimal lower bounds for different priors coding 14
Our results 1. The JKKS 11/BR 11 encoding is near optimal H(P) + 2log 3log log O(1) bits necessary (cf. achievedH(P) + 2log + 2 bits) 2. Analysis of positive-error setting [Haramaty-Sudan 14]: If incorrect decoding w.p. is allowed Can achieve H(P) + log + log 1/ bits H(P) + log + log 1/ (9/2)log log O(1) bits necessary for > 1/ 15
An -errorcoding scheme. (Inspired by J-Kalai-Khanna-Sudan 11, B-Rao 11) Pick an infinite random string Rm for each m, Put (m,e) E e is a prefix of Rm. Alice encodes m by sending the prefix of Rm of length log 1/P(m) + log + log 1/ 16
Analysis Claim. m is decoded correctly w.p. 1- Proof. There are at most 1/Q(m) messages with Q-probability greater than Q(m) P(m)/ . The probability that Rm for any one of these m agrees with the first log 1/P(m) + log + log 1/ log 1/Q(m)+log 1/ bits of Rm is at most Q(m). By a union bound, the probability that any of these agree with Rm (and hence could be wrongly chosen) is at most . 17
Length lower bound 1reduction to deterministic encodings Min-max Theorem: itsuffices to exhibit a distribution over priors for which deterministic encodings must be long 18
Length lower bound 2hard priors Lemma 1: H(P) = O(1) Lemma 2 log. prob. 0 - close -log - close -2log S m* 19 2
Length lower bound 3 short encodings have collisions Encodings of expected length < 2log 3log log encode m1 m2 identically with nonzero prob. With nonzero probability over choice of P & Q, m1,m2 S andm* {m1,m2} Decoding error with nonzero probability Errorless encodings have expected length 2log -3log log = H(P)+2log -3log log -O(1) 20
Length lower bound 4 very short encodings often collide If the encoding has expected length < log + log 1/ (9/2)log log m* collides with ( log ) other messages Probability that our draws for S miss all of these messages is < 1-2 Decoding error with probability > Error- encodings have expected length H(P) + log + log 1/ (9/2)log log O(1) 21
Recap. We saw a variant of source coding for which (near-)optimal solutions resemble natural languages in interesting ways. 22
The problem. Design a coding scheme E so that for any sender and receiver with -close prior distributions, the communication length is minimized. (In expectation w.r.t. sender s distribution) Questions? 23
