Learning I: Introduction, Parameter Estimation

Entropy of Hidden Markov Processes Or Zuk1 Ido Kanter2 Eytan Domany1 Weizmann Inst.1 Bar-Ilan Univ.2 . Overview Introduction Problem Definition Statistical Mechanics approach Cover&Thomas Upper-Bounds Radius of Convergence Related subjects Future Directions 2

HMP - Definitions Markov Process: X Markov Process M Transition Matrix M = Pr(X ij n+1 = j| Xn = i) Xn Hidden Markov Process : Y Noisy Observation of X N Noise/Emission Matrix N = Pr(Y = j| X = i) ij n n Yn M N

Xn+1 N Yn+1 3 Example: Binary HMP p(1|0) p(0| 0) 0 q(0| 0) p(0| 1) q(0|1) q(1|0) p(1|

1) q(1|1) 1 0 p (0 | 0) p (0 | 1) 1 p (1 | 0) p (1 | 1) Transition q(0 | 0) q (1 | 0) q (0 | 1) q (1 | 1) Emission

4 Example: Binary HMP (Cont.) For simplicity, we will concentrate on Symmetric Binary HMP : p 1 p p 1 p N= 1 1 M=

So all properties of the process depend on two parameters, p and . Assume (w.l.o.g.) p, < 5 HMP Entropy Rate Definition : H is difficult to compute, given as a Lyaponov Exponent (which is hard to compute generally.) [Jacquet et al 04] What to do ? Calculate H in different Regimes. 6 Different Regimes p -> 0 , p -> ( fixed) -> 0 , -> (p fixed) [Ordentlich&Weissman 04] study several regimes. We concentrate on the small noise regime -> 0.

Solution can be given as a power-series in : 7 Statistical Mechanics First, observe the Markovian Property : Perform Change of Variables : 8 Statistical Mechanics (cont.) Ising Model : 1 2 + + + +

J - K + + 1 2 - - J + - +

+ n - K - - n , {-1,1} Spin Glasses 9 Statistical Mechanics (cont.) Summing, we get : 1 Statistical Mechanics (cont.) Computing the Entropy (low-temperature/high-field expansion) :

1 Cover&Thomas Bounds It is known (Cover & Thomas 1991) : We will use the upper-bounds C(n), and derive their orders : Qu : Do the orders saturate ? 1 Cover&Thomas Bounds (cont.) Uppe rbound / Low erbound Average 1 0.09 0.45 0.9

0.45 0.4 0.8 0.4 0.35 0.7 0.35 0.3 0.6 0.3 0.25 0.5 0.25

0.05 0.2 0.4 0.2 0.04 0.15 0.3 0.15 0.03 0.1 0.2 0.1

0.02 0.05 0.1 0.05 0.01 0 0 0.1 0.2 0.3 0.4 0 0.5

n=4 e ps Re lative Error Upperbound Minus Low erbound / Average 0.5 0.4 0.07 0.06 0 0.1 0.2 0.3 0.4 0.5

3 0.45 2.5 0.4 0.1 0.35 0.08 0.25 0.06 0.2 2 0.3 p 0.3

0 eps 0.5 0.35 0.25 1.5 0.2 0.04 0.15 0.1 0.02 0.05 0 0.08

Relative Error Upperbound Minus Low erbound / (1-Average) 0.12 0.45 p Upperbound Minus Low erbound 0.5 p p 0.5 1 0.15 0.1 0.5

0.05 0 0.1 0.2 0.3 e ps 0.4 0.5 0 0 0.1 0.2 0.3

eps 0.4 0.5 0 1 Cover&Thomas Bounds (cont.) Ans : Yes. In fact they saturate sooner than would have been expected ! For n (K+3)/2 they become constant. We therefore have : Conjecture 1 : (proven for k=1)

How do the orders look ? Their expression is simpler when expressed using = 1-2p, which is the 2nd eigenvalue of P. Conjecture 2 : 1 First Few Orders : Note : H0-H2 proven. The rest are conjectures from the upper-bounds. 1 First Few Orders (Cont.) : 1 First Few Orders (Cont.) : 1 Radius of Convergence :

When is our approximation good ? Instructive : Compare to the I.I.D. model For HMP, the limit is unknown. We used the fit : 1 Radius of Convergence (cont.) : 1 Radius of Convergence (cont.) : 2 Relative Entropy Rate Relative entropy rate :

We get : 2 Index of Coincidence Take two realizations Y,Y (of length n) of the same HMP. What is the probability that they are equal ? Exponentially decaying with n. We get : Similarly, we can solve for three and four (but not five) realizations. Can give bounds on the entropy rate. 2 Future Directions

Proving conjectures Generalizations (e.g. any alphabets, continuous case) Other regimes Relative Entropy of two HMPs Thank You 2

Recently Viewed Presentations

  • Research Support Libraries Programme

    Research Support Libraries Programme

    Cooperation on Access The Research Support Libraries Programme Ronald Milne Director, Research Support Libraries Programme
  • Click on the animal containers to reveal the

    Click on the animal containers to reveal the

    I wrote to the zoo to send me a pet. ... He was perfect! I kept him. 'Dear Zoo' story and images ©Rod Campbell, 1982 Book published by Campbell Books Presentation by www.communication4all.co.uk ... Comic Sans MS Arial Calibri Chinacat...
  • Implication of Learning Curve in Physical Education

    Implication of Learning Curve in Physical Education

    IMPLICATION OF LEARNING CURVE IN PHYSICAL EDUCATION. ... Learning curve comes handy to a physical education teacher in his efforts as it is a chart which depicts the various levels of learning from stage to stage. ... Another important implication...
  • A Comparison of Digital Elevation Models for Delineating ...

    A Comparison of Digital Elevation Models for Delineating ...

    A Comparison of Digital Elevation Models for Delineating Depressions That Could Lead to Sinkhole Development. John "Sam" Morter. ... Winona County, MN, Proceedings of the Thirteenth Multidisciplinary Conference, May 6-10, Carlsbad, New Mexico: NCKRI Symposium 2. ... A Comparison of...
  • Redeployment - dcpas.osd.mil

    Redeployment - dcpas.osd.mil

    Redeployment for Term Employees "I'm heading back to the U.S. after being gone for a year—now what?" If you deployed to theater through Camp Atterbury, Indiana, your redeployment will be through Camp Atterbury, Indiana.
  • Critical Lens - inetTeacher.com

    Critical Lens - inetTeacher.com

    Critical Lenses. Objectives: To understand the feminist lens, the historical/cultural lens and the reader's response lens. To understand how to use these three lenses when looking at literature. To understand how to complete the new lit group assignment. Agenda. What...
  • The Pew Oceans Commission - Kenyon College

    The Pew Oceans Commission - Kenyon College

    (median longitudinal ventral ridge) to the body of nektonic fishes (helps to eliminate a conspicuous shadow on the belly of the animal when viewed from below) Cryptic Coloration: a) Countershading-Dark blue or green color on dorsal surfaces to match blueish...
  • Reading Maps - Loudoun County Public Schools

    Reading Maps - Loudoun County Public Schools

    Map Elements Write On In this activity you will: Learn about the elements of a map: latitude, longitude, the hemispheres, directions, time zone, scale, and map legends. Latitude and Longitude The earth is divided into lots of lines called latitude...