Fano inequality
E624508
Fano inequality is a fundamental result in information theory that provides a lower bound on the probability of classification or decoding error in terms of conditional entropy.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
bound on error probability
ⓘ
information-theoretic inequality ⓘ result in information theory ⓘ |
| appliesTo |
channel decoding problems
ⓘ
discrete random variables ⓘ finite hypothesis classes ⓘ multi-class classification ⓘ |
| assumes | finite alphabet for the hidden variable ⓘ |
| category |
entropy inequalities
ⓘ
probabilistic inequalities ⓘ |
| context | discrete memoryless channels ⓘ |
| expressesRelationBetween | alphabet size of X ⓘ |
| expressesRelationBetween |
conditional entropy H(X|Y)
ⓘ
error probability P_e ⓘ |
| field | information theory ⓘ |
| generalizationOf | bounds on binary hypothesis testing error ⓘ |
| givesLowerBoundOn |
probability of decoding error
ⓘ
probability of misclassification ⓘ |
| hasComponent | binary entropy function h(·) ⓘ |
| implies |
if conditional entropy is large then error probability is bounded away from zero
ⓘ
perfect reconstruction requires vanishing conditional entropy ⓘ |
| mathematicalDomain |
information theory
ⓘ
probability theory ⓘ |
| namedAfter | Robert Mario Fano NERFINISHED ⓘ |
| relatedTo |
Pinsker inequality
NERFINISHED
ⓘ
Shannon’s channel coding theorem NERFINISHED ⓘ data processing inequality NERFINISHED ⓘ mutual information bounds on error ⓘ |
| relatesConcept |
Bayes error probability
ⓘ
channel coding ⓘ classification error ⓘ conditional entropy ⓘ decoding error ⓘ estimation theory ⓘ hypothesis testing ⓘ mutual information ⓘ probability of error ⓘ |
| typicalForm | H(X|Y) ≤ h(P_e) + P_e log(|X|-1) ⓘ |
| usedFor |
information-theoretic limits of communication
ⓘ
information-theoretic limits of learning ⓘ lower bounding classification error ⓘ lower bounding decoding error ⓘ minimax lower bounds ⓘ sample complexity lower bounds ⓘ |
| usedIn |
deriving lower bounds on risk
ⓘ
information-theoretic analysis of machine learning ⓘ proofs of converse theorems in coding theory ⓘ proofs of impossibility results in statistics ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.