31:T5f6,md`Now that we understand statistical independence, we can go one level deeper: the **Markov property**. Rather than being defined as a relation between two random variables, the Markov property is defined on stochastic processes, or sequences of random variables. In the language of stochastic processes, each possible value that a random variable can take on is called a **state**. We say a stochastic process satisfies the Markov property if the future states are conditionally independent of the past states given the present state. To break it down, the preceding definition is equivalent to all of the following statements: 1. the future does not depend on the past, *given the present* 2. all information about future states is encapsulated in the current state 3. the stochastic process is *memoryless* Note that this is NOT the same thing as independence – in the context of stochastic processes, independence holds true when the future does not depend on any past state. The Markov assumption relaxes this and says that the future is indeed dependent on the past, but only through the most recent state. Mathematically, we write ${tex`P(X_n | X_{n-1}, X_{n-2},\ \cdots, X_1, X_0) = P(X_n | X_{n-1})`}. To illustrate the difference, consider the example of a coin-flipping game. The below **state diagram** or **state transition diagram** is a weighted, directed graph representation of the model to visualize how the random process moves between states over time. `32:T13da,markov = { // DIAGRAM PARAMETERS const transition_prob = `${prob}`; const speed = `${spd}` // BOX CONSTANTS const width = 900; const height = 300; // ARROWHEAD CONSTANTS const markerBoxWidth = 20; const markerBoxHeight = 20; const refX = markerBoxWidth / 2; const refY = markerBoxHeight / 2; const markerWidth = markerBoxWidth / 2; const markerHeight = markerBoxHeight / 2; const arrowPoints = [[0, 0], [0, 20], [20, 10]]; /////////////////////////////////////////////// DIAGRAM SKELETON ////////////////////////////////////////////////////// const svg = d3.create('svg').attr('viewBox', [0, 0, width, height]); // STATES let states = [ { x: width / 3, y: height / 2, r: 50, text: 'H'}, { x: 2 * width / 3, y: height / 2, r: 50, text: 'T'}, ]; // Add hidden states + text to the svg element let groups = svg .selectAll('g') .data(states) .join('g') .attr('transform', (d, i) => {return `translate(${d.x}, ${d.y})`;}) groups .selectAll('circle') .data(d => [d]) .join('circle') .attr('cx', 0) .attr('cy', 0) .attr('r', d => d.r) .style('fill', 'blue') .style('opacity', 0.3); groups .selectAll('text') .data(d => [d]) .join('text') .attr('x', 0) .attr('y', 0) .attr('font-size', 30) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'white') .text(d => d.text); // LINKS (curvy) const points = [[[300, 100], [280, 60], [230, 50], [190, 80], [190, 130], [210, 150], [240, 150]], // H -> H [[345, 130], [400, 115], [450, 110], [500, 115], [545, 130]], // H -> T [[600, 100], [620, 60], [670, 50], [710, 80], [710, 130], [690, 150], [660, 150]], // T -> T [[555, 170], [500, 185], [450, 190], [400, 185], [355, 170]] // T -> H ]; const curve = d3.line().curve(d3.curveNatural); for (let i = 0; i < points.length; i++) { svg .append('path') .classed('curve', true) .attr('d', curve(points[i])) .attr('stroke', 'gray') .attr('fill', 'none') .attr('marker-end', 'url(#arrow)'); } // Add arrowheads to the svg element -- GRAY svg .append('defs') .append('marker') .attr('id', 'arrow') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX) .attr('refY', refY) .attr('markerWidth', markerBoxWidth) .attr('markerHeight', markerBoxHeight) .attr('orient', 'auto-start-reverse') .attr('markerUnits', "userSpaceOnUse") .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', 'gray') .style("fill", 'gray'); // Add arrowheads to the svg element -- BLACK svg .append('defs') .append('marker') .attr('id', 'arrow2') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX) .attr('refY', refY) .attr('markerWidth', markerBoxWidth) .attr('markerHeight', markerBoxHeight) .attr('orient', 'auto-start-reverse') .attr('markerUnits', "userSpaceOnUse") .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', 'black') .style("fill", 'black'); ///////////////////////////////////////////////// INTERACTIVITY ////////////////////////////////////////////////////// // if num < transition_prob, we TRANSITION (=== switch the value of prev) let prev = Math.random() > 0.5 ? 0 : 1; function blink() { let num = Math.random() let next = svg.selectAll('circle').filter((d, i) => num < transition_prob ? i !== prev : i === prev); let path_select = svg.selectAll('path.curve') .filter((d, i) => { if (points[i][0][0] === 300 && prev === 0 && num > transition_prob) { return true; } else if (points[i][0][0] === 345 && prev === 0 && num < transition_prob) { return true; } else if (points[i][0][0] === 600 && prev === 1 && num > transition_prob) { return true; } else if (points[i][0][0] === 555 && prev === 1 && num < transition_prob) { return true; } else return false; }); path_select.transition() .duration(speed / 2) .attr('stroke-width', 5) .style('stroke', 'black') .transition() .duration(10) .attr('marker-end', 'url(#arrow2)') .transition() .duration(speed / 2) .attr('stroke-width', 1) .style('stroke', 'gray') .transition() .duration(300) .attr('marker-end', 'url(#arrow)') next.transition() .duration(speed) .transition() .duration(speed) .style("opacity", 1) .transition() .duration(speed / 2) .style("opacity", 0.3) .on("end", blink); if (num < transition_prob) { if (prev === 0) { prev = 1; } else if (prev === 1) { prev = 0; } } return svg.node(); } return blink(); }33:T432,md` Let's say you're playing a coin-flipping game with a sneaky friend of yours, who has weighted the coin so that runs are more likely. What does this mean? This means that if you toss a HEADS, it's more likely that you will get a HEADS on the next flip, and if you toss a TAILS, it's more likely that you will get a TAILS on the next flip. Let's call this *transition probability* ${tex`p`}. Note that we recover a fair coin when ${tex`p`} ${tex`= 0.5`}. Runs are actually only more likely if ${tex`p`} ${tex`< 0.5`}, and less likely if ${tex`p`} ${tex`> 0.5`}. The tosses are clearly not independent, since the probability of seeing a TAILS on flip ${tex`n`} is greater if you had also seen a TAILS on flip ${tex`(n-1)`}. However, the sequence of tosses does possess the Markov property – the result of flip ${tex`(n-2)`} tells us nothing about the result of flip ${tex`n`}, but only if we also know the result of flip ${tex`(n-1)`}.

`34:T636,md` We know what the Markov property is – so, what on Earth is a *hidden* Markov model? Consider that sometimes, you can't even observe the actual quantity you are making predictions or inferences about. For example, weather is determined by an underlying atmospheric state – to truly measure this, we'd have to determine the movement of every individual air particle, or something equally difficult. Thus, measuring the quantity of interest is often impossible, or at least intractable. Instead, we can reason about weather based on what are called **proxy variables** – related quantities such as precipitation, temperature, or atmospheric pressure. Therefore, it is helpful to pretend that there are actually *two* stochastic processes at play – the latent or **hidden process** ${tex`\{X_n\}`} of primary interest, and some measurement or **observed process** ${tex`\{Y_n\}`} that is dependent on the hidden process. Thus, a hidden Markov model is called as such: - *hidden*, because there are now two processes we want to reason about: one which we can observe directly, and one which we cannot observe directly - *Markov*, since the hidden process must satisfy the Markov property We enforce an additional condition on the observed process: each observation depends only on the current hidden state, and not on any of the past states or observations. Mathematically, we write ${tex`P(Y_n|X_n, X_{n-1}, \cdots, X_0) = P(Y_n|X_n)`}. Note that this property is not exactly "Markov", since we are conditioning on a different process. `35:T22f8,{ // DIAGRAM PARAMETERS const transition_prob = `${p_switch}`; const speed = 4 * `${spd2}`; const bias = `${p_bias}`; // BOX CONSTANTS const width = 900; const height = 600; // ARROWHEAD CONSTANTS const markerBoxWidth = 20; const markerBoxHeight = 20; const refX = markerBoxWidth / 2; const refY = markerBoxHeight / 2; const markerWidth = markerBoxWidth / 2; const markerHeight = markerBoxHeight / 2; const arrowPoints = [ [0, 0], [0, 20], [20, 10] ]; /////////////////////////////////////////////// DIAGRAM SKELETON ////////////////////////////////////////////////////// const svg = d3.create("svg").attr("viewBox", [0, 0, width, height]); // STATES let states = [ { x: width / 3, y: height / 3, r: 50, fill: "red", class: "hidden", text: "FAIR", size: 20 }, { x: (2 * width) / 3, y: height / 3, r: 50, fill: "red", class: "hidden", text: "BIAS", size: 20 }, { x: width / 3, y: (2 * height) / 3, r: 50, fill: "blue", class: "observed", text: "H", size: 30 }, { x: (2 * width) / 3, y: (2 * height) / 3, r: 50, fill: "blue", class: "observed", text: "T", size: 30 } ]; let groups = svg .selectAll("g") .data(states) .join("g") .attr("transform", (d, i) => { return `translate(${d.x}, ${d.y})`; }); groups .selectAll("circle") .data((d) => [d]) .join("circle") .attr("cx", 0) .attr("cy", 0) .attr("class", (d) => d.class) .attr("r", (d) => d.r) .style("fill", (d) => d.fill) .style("opacity", (d) => (d.class === "hidden" ? 0.15 : 0.3)); groups .selectAll("text") .data((d) => [d]) .join("text") .attr("x", 0) .attr("y", 0) .attr("font-size", (d) => d.size) .attr("font-family", "sans-serif") .attr("text-anchor", "middle") .attr("dominant-baseline", "middle") .attr("fill", "white") .text((d) => d.text); // LINKS - SOURCE (non-curvy) let linkSource = [ { x: 300, y: 250 }, // fair, H { x: 330, y: 240 }, // fair, T { x: 600, y: 250 }, // biased, T { x: 570, y: 240 } // biased, H ]; // LINKS - TARGET (non-curvy) // target node position must account for arrow width let linkTarget = [ { x: 300, y: 350 - markerHeight }, { x: 542, y: 400 - markerHeight }, { x: 600, y: 350 - markerHeight }, { x: 357, y: 400 - markerHeight } ]; const links = []; for (let i = 0; i < linkSource.length; i++) { if (i % 2 === 1) { links.push( d3 .linkHorizontal() .x((d) => d.x) .y((d) => d.y)({ source: linkSource[i], target: linkTarget[i] }) ); } else { links.push( d3 .linkVertical() .x((d) => d.x) .y((d) => d.y)({ source: linkSource[i], target: linkTarget[i] }) ); } } // Add the links with arrowhead at the end svg .selectAll("path.emission") .data(links) .join("path") .attr("d", (d, index) => links[index]) .classed("emission", true) .attr("marker-end", "url(#arrow)") .attr("stroke", "gray") .style("stroke-dasharray", ("7", "7")) .attr("fill", "none"); // LINKS (curvy) const points = [ [ [300, 150], [280, 110], [230, 100], [190, 130], [190, 180], [210, 200], [240, 200] ], [ [345, 180], [400, 165], [450, 160], [500, 165], [545, 180] ], [ [600, 150], [620, 110], [670, 100], [710, 130], [710, 180], [690, 200], [660, 200] ], [ [555, 220], [500, 235], [450, 240], [400, 235], [355, 220] ] ]; const curve = d3.line().curve(d3.curveNatural); for (let i = 0; i < points.length; i++) { svg .append("path") .classed("state", true) .attr("d", curve(points[i])) .attr("stroke", "gray") .attr("fill", "none") .attr("marker-end", "url(#arrow)"); } // Add arrowheads to the svg element -- GRAY svg .append("defs") .append("marker") .attr("id", "arrow") .attr("viewBox", [0, 0, markerBoxWidth, markerBoxHeight]) .attr("refX", refX) .attr("refY", refY) .attr("markerWidth", markerBoxWidth) .attr("markerHeight", markerBoxHeight) .attr("orient", "auto-start-reverse") .attr("markerUnits", "userSpaceOnUse") .append("path") .attr("d", d3.line()(arrowPoints)) .attr("stroke", "gray") .style("fill", "gray"); // Add arrowheads to the svg element -- BLACK svg .append("defs") .append("marker") .attr("id", "arrow2") .attr("viewBox", [0, 0, markerBoxWidth, markerBoxHeight]) .attr("refX", refX) .attr("refY", refY) .attr("markerWidth", markerBoxWidth) .attr("markerHeight", markerBoxHeight) .attr("orient", "auto-start-reverse") .attr("markerUnits", "userSpaceOnUse") .append("path") .attr("d", d3.line()(arrowPoints)) .attr("stroke", "black") .style("fill", "black"); ///////////////////////////////////////////////// INTERACTIVITY ////////////////////////////////////////////////////// // if num1 < transition_prob, we TRANSITION (=== switch the value of prev) let prev = Math.random() > 0.5 ? 0 : 1; // you either start with a fair coin or biased coin function blink() { let num1 = Math.random(); let next_state = svg .selectAll("circle.hidden") .filter((d, i) => (num1 < transition_prob ? i !== prev : i === prev)); let state_path = svg.selectAll("path.state").filter((d, i) => { if (points[i][0][0] === 300 && prev === 0 && num1 > transition_prob) { return true; } else if ( points[i][0][0] === 345 && prev === 0 && num1 < transition_prob ) { return true; } else if ( points[i][0][0] === 600 && prev === 1 && num1 > transition_prob ) { return true; } else if ( points[i][0][0] === 555 && prev === 1 && num1 < transition_prob ) { return true; } else return false; }); state_path .transition() .duration(speed / 9) .attr("stroke-width", 5) .style("stroke", "black") .transition() .duration(10) .attr("marker-end", "url(#arrow2)") .transition() .duration(speed / 9) .attr("stroke-width", 1) .style("stroke", "gray") .transition() .duration(speed / 9) .attr("marker-end", "url(#arrow)"); next_state .transition() .delay((2 * speed) / 9) .duration(speed / 3) .style("opacity", 0.6); if (num1 < transition_prob) { if (prev === 0) { prev = 1; } else if (prev === 1) { prev = 0; } } let num2 = Math.random(); // if we just moved to state 0, since prev was just updated above === fair coin if (prev === 0) { var obs = svg .selectAll("circle.observed") .filter((d, i) => (num2 < 0.5 ? i === 0 : i !== 0)); } // if (prev === 1) else { var obs = svg .selectAll("circle.observed") .filter((d, i) => (num2 < bias ? i === 0 : i !== 0)); } // find a corresponding path -> transition from heads to tails or heads to heads ... // select a path first then do the transition // solid line -> red circle -> dotted line -> blue circle -> repeat process according to A_matrix let obs_path = svg.selectAll("path.emission").filter((d, i) => { if (linkSource[i]["x"] === 300 && prev === 0 && num2 < 0.5) { return true; } else if (linkSource[i]["x"] === 330 && prev === 0 && num2 > 0.5) { return true; } else if (linkSource[i]["x"] === 570 && prev === 1 && num2 < bias) { return true; } else if (linkSource[i]["x"] === 600 && prev === 1 && num2 > bias) { return true; } else return false; }); obs_path .transition() .delay((7 * speed) / 9) .duration(speed / 9) .attr("stroke-width", 5) .style("stroke", "black") .transition() .duration(10) .attr("marker-end", "url(#arrow2)") .transition() .duration(speed / 9) .attr("stroke-width", 1) .style("stroke", "gray") .transition() .duration(speed / 9) .attr("marker-end", "url(#arrow)"); obs .transition() .delay(speed) .duration(speed / 3) .style("opacity", 1) .transition() .duration(speed / 3) .style("opacity", 0.3); next_state .transition() .delay((5 * speed) / 3) .duration(speed / 3) .style("opacity", 0.15) .on("end", blink); return svg.node(); } return blink(); }36:T401,md`In statistics and machine learning, *inference* refers to the process of drawing conclusions and making predictions. When dealing with HMMs, there are three main "problems" that we would like to solve: 1. **evaluation**. What is the probability of seeing a specific observation sequence, given a model? 2. **decoding**. What is the most likely sequence of hidden states, given an observation sequence? 3. **learning**. How can we learn the "best" model to explain our observation sequence? ^[\\*] Luckily for us, there are algorithmic methods to answer such questions.

^{[\\*] the third algorithm (Baum-Welch) is a little more complicated, and will not be covered here.
It is a special case of the expectation-maximization algorithm, which is an iterative method
for computing maximum-likelihood estimates in models with latent, or hidden, states.}

`37:T42a,md` The algorithms associated with solving the first two problems will rely on
**dynamic programming**, which is a strategy for efficiently solving certain optimization problems involving recursion. Dynamic programming applies only to problems with the following properties: 1. **overlapping subproblems**. This is when the overall problem can be broken down recursively into simpler subproblems which reoccur several times. 2. **optimal substructure**. This states that combining the optimal solutions to the subproblems always results in an optimal solution to the overall problem. Then, we can store and reuse the solutions to earlier subproblems instead of having to solve the same, reoccurring subproblems over and over again – this is a technique called **memoization**. Instead of trying a recursive approach (😥), we will consider a *bottom-up* approach in which we solve the smaller subproblems first and iteratively build our solution to the overall problem.

`38:T29c0,md` ### 3-B-1. Motivation The *evaluation problem* is concerned with quantifying how well your model fits the data – how can we verify that the model is a good explanation for the observation sequence? To answer this, we will need to compute how probable it is that the model generated such a sequence. ### 3-B-2. Intuition The generative "story" of an HMM is that we have a hidden process that emits observations at each time step. Since the transition matrix ${tex`A`} encodes the probability of each state-to-state transition, and the emission matrix ${tex`B`} encodes the relationship between hidden states and observations, it then stands to reason that if you know the *state* sequence, you might be able to compute the overall probability of your *observation* sequence. We can actually use the Markov property to simplify such a calculation, since the overall probability factors into the product of successive one-step transition and emission probabilities. ### 3-B-3. Naive Approach More specifically, given a state sequence, the conditional independence assumption tells us we can compute the joint observation probability using the following naive algorithm: 1. the probability of starting in some state is given by the initial distribution, ${tex`\pi`}. 2. we can calculate the probability of *emitting* the corresponding observation by multiplying the above by the appropriate value in the emission matrix, ${tex`B`}. 3. we proceed to the next time step by *transitioning* states, the probability of which is given by the appropriate value in ${tex`A`}, the transition matrix. 4. successively multiply results by iterating through steps 2 - 3 until we have reached the end of our observation sequence. Armed with the power of the Markov property, we can simply compute this probability for every possible state sequence and sum them to get the overall probability of seeing the data ... right? Not so fast – if there are ${tex`N`} possible hidden states and ${tex`T`} total observations, we'd have to consider ${tex`N^T`} total state sequences! Computing this would still be intractable, especially if the sequence is long. ### 3-B-4. Improved Approach Never fear – we can apply dynamic programming. Notice that many state sequences can share common *sub*sequences. For example, in the coin flipping scenario, the sequences ${tex`\{`} ${tex`\mathrm{BIAS}`}${tex`,\ `}${tex`\mathrm{FAIR}`}${tex`\mathrm{,FAIR}`}${tex`\}`} and ${tex`\{`} ${tex`\mathrm{BIAS}`}${tex`,\ `}${tex`\mathrm{FAIR}`}${tex`\mathrm{,BIAS}`}${tex`\}`} share the common subsequence ${tex`\{`} ${tex`\mathrm{BIAS}`}${tex`,\ `}${tex`\mathrm{FAIR}`}${tex`\}`}. If we can compute the probability of ${tex`\{`} ${tex`\mathrm{BIAS}`}${tex`,\ `}${tex`\mathrm{FAIR}`}${tex`\}`} first, then we can easily solve for the probabilities of both ${tex`\{`} ${tex`\mathrm{BIAS}`}${tex`,\ `}${tex`\mathrm{FAIR}`}${tex`\mathrm{,FAIR}`}${tex`\}`} and ${tex`\{`} ${tex`\mathrm{BIAS}`}${tex`,\ `}${tex`\mathrm{FAIR}`}${tex`\mathrm{,BIAS}`}${tex`\}`}. Finding the probability of these common subsequences corresponds to our overlapping subproblems. This problem is recursive precisely because the probability of any length–${tex`n`} sequence can be expressed in terms of the probability of a length–${tex`(n-1)`} subsequence, multiplied by the respective transition and emission probabilities, as we did above – all thanks to the Markov property. The **forward algorithm** is the name given to this dynamic programming approach. In essence, instead of considering each state sequence separately, we are iteratively building up our solution from progressively-longer subsequences.

### THE FORWARD ALGORITHM. First, let's define two quantities: 1. let ${tex`\alpha_t(i)`} represent the probability of seeing the data up to time step ${tex`t`},
given that you end up in state ${tex`i`} at time ${tex`t`}. 2. let ${tex`P(O|\Phi)`} be equal to the overall probability of seeing the observation sequence ${tex`O`} given our model ${tex`\Phi`}. Now, we write the algorithm below.

initialization.

${tex`\alpha_1(i) = \pi_i B_{i1}`}.

^{intuitively, this step is "explaining" the first observation, which is equal to the
probability of selecting an initial hidden state multiplied by its corresponding
emission probability.}

^{in the following diagram, we will randomly pick a coin to start with for simplicity,
so the initial distribution ${tex`\pi = (0.5, 0.5)`}.}

^{in addition, we take the FAIR coin to be state 0 and the coin with BIAS to be state 1.}

induction.

${tex`\alpha_{t}(j) = \left[ \sum\limits_{i=1}^{N} \alpha_{t-1}(i) A_{ij} \right]B_{jt}, \ \ \ t \in \{2, 3, \cdots, T\}`}.

^{for each time step, we successively compute ${tex`\bar \alpha_{t}`} using ${tex`\bar \alpha_{t-1}`}. We explain as follows:}

^{1. we must *transition* from the previous state to the next state. To calculate this, we
can simply multiply the ${tex`\alpha_{t-1}(i)`} with the associated transition probability ${tex`A_{ij}`}.}

^{2. since we could have been in any hidden state ${tex`i`} in the preceding time step,
we will have to sum the above product over all possible hidden states. Let's call
each summand a **contribution**.}

^{3. we must *emit* the appropriate observation. We can compute this probability by
multiplying the above result with the corresponding emission probability ${tex`B_{jt}`}.}

termination.

${tex`P(O|\Phi) = \sum\limits_{i=1}^{N} \alpha_T(i)`}.

^{since the ${tex`\alpha_T(i)`} encode the probability of seeing the entire observation sequence given
that you ended up in a particular state ${tex`i`}, we simply need to sum over all hidden states to
get the total probability of seeing the observation at all.}

Let's try and visualize this process. Click anywhere on the **trellis diagram** to start.`39:T390a,{ const transition_prob = `${p_switch_forward}`; const bias = `${p_bias_forward}`; const height = 500; const width = 1200; let svg = base_diagram; let count = 0; let start = false; // ============================================= INTERACTIVITY ================================================= // /////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // GENERATE_SEQ -- generate a observation sequence =============================================================== function generate_seq() { let obs_list = []; // what we see finally let state_list = []; // we don't see this let first_state = Math.random(); if (first_state < 0.5) { state_list.push('FAIR'); let first_obs = Math.random() < 0.5 ? "H" : "T"; obs_list.push(first_obs); } else { state_list.push('BIAS'); let first_obs = Math.random() < bias ? "H" : "T"; obs_list.push(first_obs); } for (let i = 1; i < 5; i++) { let transition = Math.random() < transition_prob ? true : false; if (transition) { state_list.push(state_list[i - 1] === "FAIR" ? "BIASED" : "FAIR"); } else { state_list.push(state_list[i - 1]); } if (state_list[i] === "FAIR") { obs_list.push(Math.random() > 0.5 ? "H" : "T") } else { obs_list.push(Math.random() < bias ? "H" : "T") } } let obs_text = svg.selectAll('text.obs') .data(obs_list) .join('text') .attr('x', (d, i) => (i + 1) * width / 6 - 50) .attr('y', 3 * height / 4 + 45) .classed("obs", true) .attr('font-size', 40) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'blue') .attr('font-weight', 600) .text(d => d) .style('opacity', 0); obs_text .transition() .delay((d, i) => i * 500) .duration(500) .style('opacity', 1) obs_text .transition() .delay(3500) .duration(300) .style('opacity', 0.2); svg.selectAll('text.time') .transition() .delay((d, i) => i * 500) .duration(500) .style('opacity', 1) .attr('font-weight', 'bold') .transition() .duration(300) .style('opacity', 0.3) .attr('font-weight', 'normal'); return obs_list; } // =============================================================================================================== // STEP_FORWARD -- induction step =============================================================================== async function step_forward(obs_list, alpha_list, iter){ let delay = iter === 0 ? `${spd3}` / 1.5 : `${spd3}` // calculate values ===================================================== // INITIALIZATION ========================== if (iter === 0) { let alpha_fair = Math.round(0.5 * 0.5 * 100000) / 100000; let alpha_bias = Math.round(0.5 * (obs_list[0] === 'H' ? bias : 1 - bias) * 100000) / 100000; alpha_list.push(alpha_fair); alpha_list.push(alpha_bias); let values = [{'formula': '0.5 * 0.5', 'num': alpha_fair}, {'formula': `0.5 * ${Math.round((obs_list[0] === 'H' ? bias : 1 - bias) * 100000) / 100000}`, 'num': alpha_bias}] // display alpha values =================== svg.selectAll(`text.alpha_${iter + 1}_values`) .data(values) .join('text') .attr('x', width / 6 - 50) .attr('y', (d, i) => i === 0 ? height / 4 - 70 : 2 * height / 4 + 75) .classed(`alpha_${iter + 1}_values`, true) .attr('font-size', 20) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', '#996666') .attr('font-weight', 600) .text(d => d.formula) .style('opacity', 0) .transition() .delay((d, i) => (2 * i * delay) + (i * 500)) .style('opacity', 1) .transition() .delay(2 * delay / 3) .attr('fill', 'black') .text(d => d.num); svg.selectAll('text.obs').filter((d, i) => i === 0) .transition() .style('opacity', 1) .transition() .delay(2 * delay / 3) .duration(300) .style('opacity', 0.2) svg.selectAll('text.obs').filter((d, i) => i === 0) .transition() .delay(2 * delay + 500) .style('opacity', 1) .transition() .delay(2 * delay / 3) .duration(300) .style('opacity', 0.2) } // INDUCTION =============================== else { let alpha_prev_fair = alpha_list.filter((d, i) => i === alpha_list.length - 2) let alpha_prev_bias = alpha_list.filter((d, i) => i === alpha_list.length - 1) let alpha_fair = Math.round(((1 - transition_prob) * parseFloat(alpha_prev_fair) + transition_prob * parseFloat(alpha_prev_bias)) * 0.5 * 10000) / 10000; let alpha_bias = Math.round((transition_prob * parseFloat(alpha_prev_fair) + (1 - transition_prob) * parseFloat(alpha_prev_bias)) * (obs_list[iter] === 'H' ? bias : 1 - bias) * 10000) / 10000; alpha_list.push(alpha_fair); alpha_list.push(alpha_bias); let values = [{'formula1': `[${Math.round((1 - transition_prob) * 10) / 10}(${alpha_prev_fair})]`, 'formula2': `[${Math.round((1 - transition_prob) * 10) / 10}(${alpha_prev_fair}) + ${Math.round(transition_prob * 10) / 10}(${alpha_prev_bias})]`, 'formula3': `[${Math.round((1 - transition_prob) * 10) / 10}(${alpha_prev_fair}) + ${Math.round(transition_prob * 10) / 10}(${alpha_prev_bias})] * 0.5`, 'num': alpha_fair}, {'formula1': `[${Math.round(transition_prob * 10) / 10}(${alpha_prev_fair})]`, 'formula2': `[${Math.round(transition_prob * 10) / 10}(${alpha_prev_fair}) + ${Math.round((1 - transition_prob) * 10) / 10}(${alpha_prev_bias})]`, 'formula3': `[${Math.round(transition_prob * 10) / 10}(${alpha_prev_fair}) + ${Math.round((1 - transition_prob) * 10) / 10}(${alpha_prev_bias})] * ${Math.round((obs_list[iter] === 'H' ? bias : 1 - bias) * 10) / 10}`, 'num': alpha_bias}]; let values_text = svg.selectAll(`text.alpha_${iter + 1}_values`) .data(values) .join('text') .attr('x', (iter + 1) * width / 6 - 50) .attr('y', (d, i) => i === 0 ? height / 4 - 70 : 2 * height / 4 + 75) .classed(`alpha_${iter + 1}_values`, true) .attr('font-size', 20) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', '#996666') .text(d => d.formula1) .style('opacity', 0) .attr('font-weight', 600) values_text .transition() .delay((d, i) => 2 * i * delay) .style('opacity', 1) .transition() .delay(delay / 3) .text(d => d.formula2) .transition() .delay(delay / 3) .text(d => d.formula3) .transition() .delay(delay / 3) .attr('fill', 'black') .text(d => d.num); } // display text ========================================================== let alpha_text = [['\u03b1', `${iter+1}`, '(0)'], ['\u03b1', `${iter+1}`, '(1)']]; let text = svg.selectAll(`text.alpha_${iter+1}_text`) .data(alpha_text) .join('text') .attr('x', (iter + 1) * width / 6 - 50) .attr('y', (d, i) => i === 0 ? height / 4 - 100 : 2 * height / 4 + 100) .classed(`alpha_${iter+1}_text`, true) .attr('font-size', 15) .attr('font-family', 'serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'black') .style('opacity', 0) text .append('tspan') .text(d => d[0]) text .append('tspan') .text(d => d[1]) .style('baseline-shift', "sub") text .append('tspan') .text(d => d[2]) text .transition() .delay((d, i) => (2 * i * delay) + (iter === 0 ? (500 * i) : 0)) .style('opacity', 1) .transition() .delay(5 * delay / 3) .style('opacity', 0.5); // highlight corresponding state (FAIR, BIAS) svg.selectAll('circle').filter((d, i) => i < (iter + 1) * 2 && i >= iter * 2) .transition() .delay((d, i) => (2 * i * delay) + (iter === 0 ? (500 * i) : 0)) .duration(300) .style("opacity", 1) .transition() .delay(4 * delay / 3) .duration(300) .style('opacity', 0.3); // highlight corresponding arrows if (iter !== 0) { let arrows = svg.selectAll('path.link').filter((d, i) => i === iter * 2 - 2 || i === iter * 2 - 1 + 8); arrows.transition() .delay((d, i) => i * delay / 3 + 100) .duration(100) .attr('stroke-width', 5) .style('stroke', 'black') .transition() .duration(10) .attr('marker-end', 'url(#arrow-forward-2)') .transition() .delay(delay / 3) .duration(100) .attr('stroke-width', 1) .style('stroke', '#BBBBBB') .transition() .duration(10) .attr('marker-end', 'url(#arrow-forward)'); let arrows_2 = svg.selectAll('path.link').filter((d, i) => i === iter * 2 - 1 || i === iter * 2 - 2 + 8); arrows_2.transition() .delay((d, i) => delay * 2 + ((1 - i) * delay / 3) + 100) .duration(100) .attr('stroke-width', 5) .style('stroke', 'black') .transition() .duration(10) .attr('marker-end', 'url(#arrow-forward-2)') .transition() .delay(delay / 3) .attr('stroke-width', 1) .style('stroke', '#BBBBBB') .transition() .duration(10) .attr('marker-end', 'url(#arrow-forward)'); svg.selectAll('text.obs').filter((d, i) => i === iter) .transition() .delay(2 * delay / 3 + 300) .style('opacity', 1) .transition() .delay(delay / 3) .duration(300) .style('opacity', 0.2) svg.selectAll('text.obs').filter((d, i) => i === iter) .transition() .delay(8 * delay / 3 + 300) .style('opacity', 1) .transition() .delay(delay / 3) .duration(300) .style('opacity', 0.2); } return new Promise((resolve) => { setTimeout(() => { resolve(alpha_list); }, 4 * delay); }); } // =============================================================================================================== // FINISH -- termination step ==================================================================================== function finish(alpha_list) { let delay = `${spd3}`; let curly = svg.append('text') .attr('x', 5 * width / 6 + 25) .attr('y', height / 2 - 75) .classed('curly', true) .attr('font-size', 55) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .text('}') .style('opacity', 0); let final = svg.append('text') .attr('x', width - 80) .attr('y', height / 2 - 75) .classed('final', true) .attr('font-size', 20) .attr('font-weight', 500) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('font-weight', 'bold') .attr('fill', '#996666') .text(`${alpha_list[alpha_list.length - 1]} + ${alpha_list[alpha_list.length - 2]}`) .style('opacity', 0); curly .transition() .duration(500) .style('opacity', 1) final .transition() .duration(500) .style('opacity', 1) .transition() .delay(delay / 2) .duration(300) .attr('font-size', 30) .text(Math.round((alpha_list[alpha_list.length - 1] + alpha_list[alpha_list.length - 2]) * 100000) / 100000) .attr('fill', 'green') .attr('x', 5 * width / 6 + 115); svg.selectAll('text.obs') .transition() .delay(delay) .duration(300) .style('opacity', 1) } // =============================================================================================================== // RUN_ALGO -- run the full algorithm visualization (outside wrapper) ============================================ function run_algo() { let obs_list = generate_seq(); let alpha_list = []; d3.select('#advance').on('click', async function() { if (!start) { return; } if (start && count < 5) { document.getElementById("advance").disabled = true; document.getElementById("reset").disabled = true; alpha_list = await step_forward(obs_list, alpha_list, count); document.getElementById("advance").disabled = false; document.getElementById("reset").disabled = false; } if (count == 5) { document.getElementById("advance").disabled = true; finish(alpha_list); } count++; }); start = true; } d3.select('#reset').on('click', async function() { svg.selectAll('text.obs').transition().style('opacity', 0); for (let i = 1; i < 6; i++) { svg.selectAll(`text.alpha_${i}_text`).remove(); svg.selectAll(`text.alpha_${i}_values`).remove(); } svg.selectAll('circle') .transition() .style('opacity', 0.3); svg.selectAll('text.time') .transition() .style('opacity', 0.3) .attr('font-weight', 400); svg.selectAll('path') .transition() .attr('stroke-width', 1) .style('stroke', '#BBBBBB') .attr('marker-end', 'url(#arrow-forward)'); svg.select('text.final').remove(); svg.select('text.curly').remove(); svg.selectAll('text.obs') .transition() .style('opacity', 0) svg = base_diagram; count = 0; start = false; document.getElementById("advance").disabled = false; }); svg.on('click', function(d) { if (!start) { run_algo(); } start = true; }); return svg.node(); }3a:T2a98,md`### 3-C-1. Motivation Solving the *decoding problem* is the primary goal of HMM inference. Since it involves reasoning about the underlying hidden process, it is fundamentally a question of causality. The big question is: what can we conclude about the hidden process, given only the evidence from our observations? In other words, what is the most likely explanation for the data? To answer this, we will have to compute the most probable state sequence. ### 3-C-2. Intuition First, we define some notation. Let ${tex`O=(o_1, \cdots, o_T)`} be our observation
sequence, and let ${tex`S=(s_1, \cdots, s_T)`} be some state sequence of interest. In Section 3-B, we described how knowing the hidden states can yield insight into the observation sequence – specifically, its probability of occurrence. The decoding problem flips the roles of the two, and asks what knowing the observation sequence can tell us about the underlying hidden states. Mathematically, we denote these probabilities as ${tex`P(O|S)`} and ${tex`P(S|O)`}, respectively. Then, we can relate the quantities using **Bayes' Theorem**: ${tex`P(S|O) = \frac{P(O|S)P(S)}{P(O)}`} . This is a famous ^[\\*] result that relates opposite, or inverse, conditional probabilities. Note that the probabilities ${tex`P(S|O)`} and ${tex`P(O|S)`} are directly related – increasing one will lead to a corresponding increase in the other, all other quantities being equal. Thus, we see that maximizing the observation probability given a state sequence is equivalent to maximizing the probability of the state sequence itself! Then, we can use the same approach as in Section 3-B, and compute observation probabilities. ^{[\\*] understatement of the year. Bayes' Theorem is a much deeper statement, and it is a fascinating
      (and deep!) rabbit hole to go down. In many situations, computing one of these conditional
     probabilities is easy, but computing the other is difficult. Then, the theorem gives us a way to
     calculate or even maximize the hard-to-compute quantity from the easy-to-compute quantity.}

### 3-C-3. Naive Approach *Method 1*. An initial approach might be to compute the probability of the observation sequence over all possible state sequences, and choose the state sequence that maximizes this probability. However, as before, this is computationally intractable. Then, you might ask – didn't the forward algorithm handle this exact problem by using dynamic programming? Why not just use the forward algorithm? *Method 2*. Another less naive, but still naive, approach would be to run the forward algorithm and simply pick the state with highest ${tex`\alpha`} values at each time step. Intuitively, this corresponds to choosing the state that maximizes the probability of that subsequence occurring. However, this just gives us the *locally* optimal decision, since we are looking at each time step separately. It's entirely possible that the resulting sequence includes a transition between two states whose transition probability is 0. Thus, there is no guarantee that the optimal state sequence is even valid. ### 3-C-4. Improved Approach Luckily, we can modify the forward algorithm to return valid state sequences. Instead of *summing* the contribution from each preceding state, we choose the *maximum* contribution, *and* make note of which state it came from by storing a **backpointer**. Since the corresponding transition probability is already factored
into each contribution, we do not have to worry about invalid state sequences! Mathematically, each contribution gives us the maximum probability of any subsequence ending in that particular state; we want the maximum contribution, or maximum subsequence probability over *all* ending states. We call this modified approach the **Viterbi algorithm**. At the end, we choose the state with the highest final probability and backtrack through our backpointer array to give us our final, optimal hidden state sequence.

### THE VITERBI ALGORITHM. First, let's define three more quantities: 1. let ${tex`\psi_t(i)`} represent the *maximum* probability of seeing the data up to time ${tex`t`}, given that you end up in state ${tex`i`} at time ${tex`t`}. (AKA, the maximum contribution.) 2. let ${tex`\xi_t(i)`} be the state whose contribution maximizes ${tex`\psi_t(i)`}, as above. This will be the backpointer array that allows us to compute the optimal state sequence. 3. let ${tex`S^* = (S_1^*, S_2^*, \cdots, S_T^*)`} represent the optimal state sequence. Now, we write the algorithm below.

initialization.

${tex`\psi_1(i) = \pi_i B_{i1}`}.
${tex`\xi_1(i) = -1`}.

^{like the forward algorithm, this step is "explaining" the first observation. There
                         is only one possible state sequence associated with the first observation and
                         ending in a given state, so its associated probability is by default the maximum.
                         Note that ${tex`\psi_1(i)`} is equivalent to ${tex`\alpha_1(i)`} as defined in the forward algorithm.}

^{we set the initial backpointers to ${tex`-1`} to signify that there is no preceding state.}

induction.

${tex`\psi_t(j) = \max\limits_{i}\big\{ \psi_{t-1}(i) A_{ij} \big\} B_{jt}, \ \ \ t \in \{2, 3, \cdots, T\}`}.
${tex`\xi_t(j) = \argmax\limits_{i}\big\{ \psi_{t-1}(i) A_{ij} \big\}, \ \ \ t \in \{2, 3, \cdots, T\}`}.

^{for each time step, we recursively compute ${tex`\psi_{t}`} and ${tex`\xi_{t}`} using ${tex`\psi_{t-1}`} and ${tex`\xi_{t-1}`}:}

^{1. compute the max probability of a subsequence ending in each state.}

^{1-A. we account for *transitions* by taking the maximum over ${tex`\alpha_{t-1}(i)`} multiplied by ${tex`A_{ij}`}.}

^{1-B.
we account for *emissions* by multiplying the above result by ${tex`B_{jt}`}. This term can be
taken outside of the max operation since it does not depend on the previous state.}

^{2. store the correct backpointer. We simply take the ${tex`\argmax`} of the above quantity.}

termination.

${tex`S_T^* = \argmax\limits_{i}\big\{ \psi_{T}(i) \big\} `}.

^{compute the most likely final state.}

backtracking.

${tex`S_{t-1}^* = \xi_{t}(S_{t}^*), \ \ \ t \in \{T, T-1, \cdots, 2\}`}.

^{since ${tex`\xi_t`} stores the previous states in each maximal-probability path, we can
calculate the optimal state sequence by starting from the *maximum*-probability
path, and working backwards.}

`3b:T57bd,{ const transition_prob = `${p_switch_viterbi}`; const bias = `${p_bias_viterbi}`; const height = 500; const width = 1200; let svg = base_diagram2; let count = 0; let start = false; // GENERATE_SEQ -- generate a observation sequence =============================================================== function generate_seq() { let obs_list = []; let state_list = []; let first_state = Math.random(); if (first_state < 0.5) { state_list.push('FAIR'); let first_obs = Math.random() < 0.5 ? "H" : "T"; obs_list.push(first_obs); } else { state_list.push('BIAS'); let first_obs = Math.random() < bias ? "H" : "T"; obs_list.push(first_obs); } for (let i = 1; i < 5; i++) { let transition = Math.random() < transition_prob ? true : false; if (transition) { state_list.push(state_list[i - 1] === "FAIR" ? "BIASED" : "FAIR"); } else { state_list.push(state_list[i - 1]); } if (state_list[i] === "FAIR") { obs_list.push(Math.random() > 0.5 ? "H" : "T") } else { obs_list.push(Math.random() < bias ? "H" : "T") } } let obs_text = svg.selectAll('text.obs-viterbi') .data(obs_list) .join('text') .attr('x', (d, i) => (i + 1) * width / 6 - 50) .attr('y', 3 * height / 4 + 45) .classed("obs-viterbi", true) .attr('font-size', 40) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'blue') .attr('font-weight', 600) .text(d => d) .style('opacity', 0); obs_text .transition() .delay((d, i) => i * 500) .duration(500) .style('opacity', 1) obs_text .transition() .delay(3500) .duration(300) .style('opacity', 0.2); svg.selectAll('text.time') .transition() .delay((d, i) => i * 500) .duration(500) .style('opacity', 1) .attr('font-weight', 'bold') .transition() .duration(300) .style('opacity', 0.3) .attr('font-weight', 'normal'); return obs_list; } //=============================================================================== // STEP_FORWARD -- induction step =============================================================================== async function step_forward(obs_list, psi_list, backpointers, iter){ let delay = iter === 0 ? `${spd4}` / 3 : `${spd4}` // calculate values ===================================================== // INITIALIZATION ========================== if (iter === 0) { let psi_fair = Math.round(0.5 * 0.5 * 100000) / 100000; let psi_bias = Math.round(0.5 * (obs_list[0] === 'H' ? bias : 1 - bias) * 100000) / 100000; psi_list.push(psi_fair); psi_list.push(psi_bias); let values = [{'formula': '0.5 * 0.5', 'num': psi_fair}, {'formula': `0.5 * ${Math.round((obs_list[0] === 'H' ? bias : 1 - bias) * 100000) / 100000}`, 'num': psi_bias}] // display alpha values =================== svg.selectAll(`text.psi_${iter + 1}_values`) .data(values) .join('text') .attr('x', width / 6 - 50) .attr('y', (d, i) => i === 0 ? height / 4 - 70 : 2 * height / 4 + 75) .classed(`psi_${iter + 1}_values`, true) .attr('font-size', 20) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', '#777777') .attr('font-weight', 600) .text(d => d.formula) .style('opacity', 0) .transition() .delay((d, i) => ((10 / 3) * i * delay)) .style('opacity', 1) .transition() .delay(delay) .attr('fill', 'black') .text(d => d.num); svg.selectAll('text.obs-viterbi').filter((d, i) => i === 0) .transition() .style('opacity', 1) .transition() .delay(delay) .duration(300) .style('opacity', 0.2) svg.selectAll('text.obs-viterbi').filter((d, i) => i === 0) .transition() .delay((10 / 3) * delay) .style('opacity', 1) .transition() .delay(delay) .duration(300) .style('opacity', 0.2) } // INDUCTION =============================== else { var psi_prev_fair = psi_list.filter((d, i) => i === psi_list.length - 2) var psi_prev_bias = psi_list.filter((d, i) => i === psi_list.length - 1) let psi_fair = Math.round(Math.max((1 - transition_prob) * parseFloat(psi_prev_fair), transition_prob * parseFloat(psi_prev_bias)) * 0.5 * 100000) / 100000; let psi_bias = Math.round(Math.max(transition_prob * parseFloat(psi_prev_fair), (1 - transition_prob) * parseFloat(psi_prev_bias)) * (obs_list[iter] === 'H' ? bias : 1 - bias) * 100000) / 100000; psi_list.push(psi_fair); psi_list.push(psi_bias); let prev_state_fair = Math.max((1 - transition_prob) * parseFloat(psi_prev_fair), transition_prob * parseFloat(psi_prev_bias)) == (1 - transition_prob) * parseFloat(psi_prev_fair) ? 0 : 1 let prev_state_bias = Math.max(transition_prob * parseFloat(psi_prev_fair), (1 - transition_prob) * parseFloat(psi_prev_bias)) == (1 - transition_prob) * parseFloat(psi_prev_bias) ? 1 : 0 backpointers[0].push(prev_state_fair); backpointers[1].push(prev_state_bias); let values = [{'formula1': `${psi_prev_fair}(${Math.round((1 - transition_prob) * 10) / 10}) * 0.5`, 'formula2': `${Math.round(psi_prev_fair * (1 - transition_prob) * 0.5 * 100000) / 100000}`, 'formula3': `${psi_prev_bias}(${Math.round(transition_prob * 10) / 10}) * 0.5`, 'formula4': `${Math.round(psi_prev_bias * transition_prob * 0.5 * 100000) / 100000}`, 'num': psi_fair}, {'formula1': `${psi_prev_fair}(${Math.round(transition_prob * 10) / 10}) * ${Math.round((obs_list[iter] === 'H' ? bias : 1 - bias) * 10) / 10}`, 'formula2': `${Math.round(psi_prev_fair * transition_prob * (obs_list[iter] === 'H' ? bias : 1 - bias) * 100000) / 100000}`, 'formula3': `${psi_prev_bias}(${Math.round((1 - transition_prob) * 10) / 10}) * ${Math.round((obs_list[iter] === 'H' ? bias : 1 - bias) * 10) / 10}`, 'formula4': `${Math.round(psi_prev_bias * (1 - transition_prob) * (obs_list[iter] === 'H' ? bias : 1 - bias) * 100000) / 100000}`, 'num': psi_bias}]; let max_text = [['max {', `${Math.round(psi_prev_fair * (1 - transition_prob) * 0.5 * 100000) / 100000}`, ', ', `${Math.round(psi_prev_bias * transition_prob * 0.5 * 100000) / 100000}`, '}'], ['max {', `${Math.round(psi_prev_fair * transition_prob * (obs_list[iter] === 'H' ? bias : 1 - bias) * 100000) / 100000}`, ', ', `${Math.round(psi_prev_bias * (1 - transition_prob) * (obs_list[iter] === 'H' ? bias : 1 - bias) * 100000) / 100000}`, '}']]; let max_val = svg.selectAll(`text.psi_${iter+1}_text_max`) .data(max_text) .join('text') .attr('x', (iter + 1) * width / 6 - 50) .attr('y', (d, i) => i === 0 ? height / 4 - 70 : 2 * height / 4 + 75) .classed(`psi_${iter+1}_text_max`, true) .attr('font-size', 20) .attr('font-family', 'sans-serif') .attr('font-weight', 'bold') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .style('opacity', 0) max_val .append('tspan') .text(d => d[0]) .attr('fill', 'black') max_val .append('tspan') .text(d => d[1]) .attr('fill', '#3ab245') max_val .append('tspan') .text(d => d[2]) .attr('fill', 'black') max_val .append('tspan') .text(d => d[3]) .attr('fill', '#CD00CD') max_val .append('tspan') .text(d => d[4]) .attr('fill', 'black') max_val .transition() .delay((d, i) => ((10 / 3) * i * delay + 5 * delay / 3 + 100)) .style('opacity', 1) .transition() .delay(delay / 3) .style('opacity', 0); let values_text = svg.selectAll(`text.psi_${iter + 1}_values`) .data(values) .join('text') .attr('x', (iter + 1) * width / 6 - 50) .attr('y', (d, i) => i === 0 ? height / 4 - 70 : 2 * height / 4 + 75) .classed(`psi_${iter + 1}_values`, true) .attr('font-size', 20) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .text(d => d.formula1) .style('opacity', 0) .attr('font-weight', 600) values_text .transition() .delay((d, i) => (10 / 3) * i * delay) .style('fill', '#3ab245') .style('opacity', 1) .transition() .delay(delay / 3) .text(d => d.formula2) .transition() .delay(delay / 3) .duration(10) .style('fill', '#CD00CD') .text(d => d.formula3) .transition() .delay(delay / 3) .text(d => d.formula4) .transition() .delay(delay / 3) .style('opacity', 0) .transition() .delay(3 * delay / 3) .style('fill', 'black') .style('opacity', 1) .text(d => d.num); } // display text ========================================================== let psi_text = [['\u03a8', `${iter+1}`, '(0)'], ['\u03a8', `${iter+1}`, '(1)']]; let text = svg.selectAll(`text.psi_${iter+1}_text`) .data(psi_text) .join('text') .attr('x', (iter + 1) * width / 6 - 50) .attr('y', (d, i) => i === 0 ? height / 4 - 100 : 2 * height / 4 + 100) .classed(`psi_${iter+1}_text`, true) .attr('font-size', 15) .attr('font-family', 'serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'black') .style('opacity', 0) text .append('tspan') .text(d => d[0]) text .append('tspan') .text(d => d[1]) .style('baseline-shift', "sub") text .append('tspan') .text(d => d[2]) text .transition() .delay((d, i) => ((10 / 3) * i * delay)) .style('opacity', 1) .transition() .delay(7 * delay / 3) .style('opacity', 0.5); // highlight corresponding state (FAIR, BIAS) svg.selectAll('circle').filter((d, i) => i < (iter + 1) * 2 && i >= iter * 2) .transition() .delay((d, i) => (10 / 3) * i * delay) .duration(300) .style("opacity", 1) .transition() .delay(iter === 0 ? 6 * delay / 3 : 8 * delay / 3) .duration(300) .style('opacity', (d, i) => i % 2 === 0 ? 0.4 : 0.3); if (iter !== 0) { // highlight corresponding arrows let arrows = svg.selectAll('path.link-viterbi').filter((d, i) => i === iter * 2 - 2 || i === iter * 2 - 1 + 8); arrows.transition() .delay((d, i) => (2 / 3) * i * delay + (i * delay / 10)) .attr('stroke-width', 5) .style('stroke', 'black') .transition() .duration(10) .attr('marker-end', 'url(#arrow-viterbi-2)') .transition() .delay(2 * delay / 3) .attr('stroke-width', 1) .style('stroke', '#BBBBBB') .transition() .duration(10) .attr('marker-end', 'url(#arrow-viterbi)') arrows.transition() // light up both arrows when taking max .delay(5 * delay / 3) .attr('stroke-width', 5) .style('stroke', 'black') .attr('marker-end', 'url(#arrow-viterbi-2)') .transition() .delay(delay / 3) .attr('stroke-width', 1) .style('stroke', '#BBBBBB') .attr('marker-end', 'url(#arrow-viterbi)') let arrow_selected = svg .selectAll('path.link-viterbi') .filter((d, i) => (1 - transition_prob) * parseFloat(psi_prev_fair) > transition_prob * parseFloat(psi_prev_bias) ? i === iter * 2 - 2 : i === iter * 2 - 1 + 8); arrow_selected.transition() .delay(8 * delay / 3 - delay / 5) .attr('stroke-width', 4) .style('stroke', '#876543') .attr('marker-end', 'url(#arrow-viterbi-3)') let arrows_2 = svg.selectAll('path.link-viterbi').filter((d, i) => i === iter * 2 - 1 || i === iter * 2 - 2 + 8); arrows_2.transition() .delay((d, i) => (10 * delay / 3) + (1 - i) *(2 * delay / 3) + ((1 - i) * delay / 10)) .attr('stroke-width', 5) .style('stroke', 'black') .transition() .duration(10) .attr('marker-end', 'url(#arrow-viterbi-2)') .transition() .delay(2 * delay / 3) .attr('stroke-width', 1) .style('stroke', '#BBBBBB') .transition() .duration(10) .attr('marker-end', 'url(#arrow-viterbi)'); arrows_2.transition() // light up both arrows when taking max .delay(15 * delay / 3) .attr('stroke-width', 5) .style('stroke', 'black') .attr('marker-end', 'url(#arrow-viterbi-2)') .transition() .delay(delay / 3) .attr('stroke-width', 1) .style('stroke', '#BBBBBB') .attr('marker-end', 'url(#arrow-viterbi)') let arrow_selected2 = svg .selectAll('path.link-viterbi') .filter((d, i) => transition_prob * parseFloat(psi_prev_fair) < (1 - transition_prob) * parseFloat(psi_prev_bias) ? i === iter * 2 - 1 : i === iter * 2 - 2 + 8); arrow_selected2.transition() .delay(18 * delay / 3 - delay / 5) .attr('stroke-width', 4) .style('stroke', '#876543') .attr('marker-end', 'url(#arrow-viterbi-3)') } return new Promise((resolve) => { setTimeout(() => { resolve([psi_list, backpointers]); }, 6 * delay); }); } // =============================================================================================================== // FINISH -- termination step ==================================================================================== function finish(psi_list, backpointers) { let delay = `${spd4}`; let curly = svg.append('text') .attr('x', 5 * width / 6 + 25) .attr('y', height / 2 - 75) .classed('curly', true) .attr('font-size', 55) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .text('}') .style('opacity', 0); curly .transition() .duration(500) .style('opacity', 1) let final_text1 = svg .append('text') .attr('x', 5 * width / 6 + 112) .attr('y', height / 2 - 88) .classed('final', true) .attr('font-size', 20) .attr('font-family', 'sans-serif') .attr('font-weight', 'bold') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .style('opacity', 0) final_text1 .append('tspan') .text('max {') final_text1 .append('tspan') .text(`${Math.round(psi_list[psi_list.length - 2] * 100000) / 100000}`) .attr('fill', '#3ab245') final_text1 .append('tspan') .text(', ') final_text1 .transition() .delay(delay / 2) .style('opacity', 1) .transition() .delay(delay / 2) .style('opacity', 0) let final_text2 = svg .append('text') .attr('x', 5 * width / 6 + 140) .attr('y', height / 2 - 60) .classed('final', true) .attr('font-size', 20) .attr('font-family', 'sans-serif') .attr('font-weight', 'bold') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .style('opacity', 0) final_text2 .append('tspan') .text(`${Math.round(psi_list[psi_list.length - 1] * 100000) / 100000}`) .attr('fill', '#CD00CD') final_text2 .append('tspan') .text('}') final_text2 .transition() .delay(delay / 2) .style('opacity', 1) .transition() .delay(delay / 2) .style('opacity', 0) let final_text_3 = svg .append('text') .attr('x', 5 * width / 6 + 100) .attr('y', height / 2 - 75) .classed('final', true) .attr('font-size', 25) .attr('font-family', 'sans-serif') .attr('font-weight', 'bold') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .style('opacity', 0) .attr('fill', Math.max(psi_list[psi_list.length - 1], psi_list[psi_list.length - 2]) === psi_list[psi_list.length - 2] ? '#3ab245' : '#CD00CD') .text(`${Math.round(Math.max(psi_list[psi_list.length - 1], psi_list[psi_list.length - 2]) * 100000) / 100000}`) final_text_3 .transition() .duration(500) .delay(6 * delay / 5) .style('opacity', 1) let state = Math.max(psi_list[psi_list.length - 1], psi_list[psi_list.length - 2]) === psi_list[psi_list.length - 2] ? 0 : 1; svg.selectAll('circle').filter((d, i) => state === 0 ? i === 8 : i === 9) .transition() .delay(8 * delay / 5) .style('opacity', 1) let selected = []; for (let i = 3; i >= 0; --i) { // do backpointer stuff here! //backpointers[0].push(prev_state_fair); //backpointers[1].push(prev_state_bias); if (state === 0) { if (backpointers[state][i] === 0) { svg.selectAll('path.link-viterbi').filter((d, idx) => idx === (i + 1) * 2 - 2) // fair -> fair .transition() .delay((9 * delay / 5) + ((3 - i) * (2 * delay / 5))) .attr('stroke-width', 5) .style('stroke', 'black') .attr('marker-end', 'url(#arrow-viterbi-2)') selected.push((i + 1) * 2 - 2); } else { svg.selectAll('path.link-viterbi').filter((d, idx) => idx === (i + 1) * 2 - 1 + 8) // bias -> fair .transition() .delay((9 * delay / 5) + ((3 - i) * (2 * delay / 5))) .attr('stroke-width', 5) .style('stroke', 'black') .attr('marker-end', 'url(#arrow-viterbi-2)') selected.push((i + 1) * 2 - 1 + 8); } } else { if (backpointers[state][i] === 0) { svg.selectAll('path.link-viterbi').filter((d, idx) => idx === (i + 1) * 2 - 2 + 8) // fair -> bias .transition() .delay((9 * delay / 5) + ((3 - i) * (2 * delay / 5))) .attr('stroke-width', 5) .style('stroke', 'black') .attr('marker-end', 'url(#arrow-viterbi-2)') selected.push((i + 1) * 2 - 2 + 8); } else { svg.selectAll('path.link-viterbi').filter((d, idx) => idx === (i + 1) * 2 - 1) // bias -> bias .transition() .delay((9 * delay / 5) + ((3 - i) * (2 * delay / 5))) .attr('stroke-width', 5) .style('stroke', 'black') .attr('marker-end', 'url(#arrow-viterbi-2)') selected.push((i + 1) * 2 - 1); } } state = backpointers[state][i]; svg.selectAll('circle').filter((d, idx) => state === 0 ? idx === i * 2 : idx === i * 2 + 1) .transition() .delay((10 * delay / 5) + ((3 - i) * (2 * delay / 5))) .duration(300) .style("opacity", 1) } // unhighlight unneeded arrows svg.selectAll('path.link-viterbi').filter((d, i) => !selected.includes(i)) .transition() .delay(19 * delay / 5) .attr('stroke-width', 1) .style('stroke', '#BBBBBB') .attr('marker-end', 'url(#arrow-viterbi)') } // =============================================================================================================== // RUN_ALGO -- run the full algorithm visualization (outside wrapper) ============================================ function run_algo() { let obs_list = generate_seq(); let psi_list = []; let backpointers = [[], []]; d3.select('#advance2').on('click', async function() { if (!start) { return; } if (start && count < 5) { document.getElementById("advance2").disabled = true; document.getElementById("reset2").disabled = true; [psi_list, backpointers] = await step_forward(obs_list, psi_list, backpointers, count); document.getElementById("advance2").disabled = false; document.getElementById("reset2").disabled = false; } if (count == 5) { document.getElementById("advance2").disabled = true; finish(psi_list, backpointers); } count++; }); start = true; } d3.select('#reset2').on('click', async function() { svg.selectAll('text.obs-viterbi').transition().style('opacity', 0); for (let i = 1; i < 6; i++) { svg.selectAll(`text.psi_${i}_text`).remove(); svg.selectAll(`text.psi_${i}_text_max`).remove(); svg.selectAll(`text.psi_${i}_values`).remove(); svg.select('text.final').remove(); } svg.selectAll('circle') .transition() .style('opacity', (d, i) => i % 2 === 0 ? 0.4 : 0.3); svg.selectAll('text.time') .transition() .style('opacity', 0.3) .attr('font-weight', 400); svg.selectAll('path') .transition() .attr('stroke-width', 1) .style('stroke', '#BBBBBB') .attr('marker-end', 'url(#arrow-viterbi)'); svg.select('text.curly').remove(); svg = base_diagram2; count = 0; start = false; document.getElementById("advance2").disabled = false; }); svg.on('click', function(d) { if (!start) { run_algo(); } start = true; }); return svg.node(); }3c:T1613,base_diagram = { document.getElementById("advance").disabled = false; // DIAGRAM PARAMETERS const transition_prob = `${p_switch_forward}`; const speed = `${spd3}`; const bias = `${p_bias_forward}`; // BOX CONSTANTS const width = 1200; const height = 500; // ARROWHEAD CONSTANTS const markerBoxWidth = 20; const markerBoxHeight = 20; const refX = markerBoxWidth / 2; const refY = markerBoxHeight / 2; const markerWidth = markerBoxWidth / 2; const markerHeight = markerBoxHeight / 2; const arrowPoints = [[0, 0], [0, 20], [20, 10]]; /////////////////////////////////////////////// DIAGRAM SKELETON ////////////////////////////////////////////////////// const svg = d3.create('svg').attr('viewBox', [0, 0, width, height]); // STATES let states = [ { x: width / 6 - 50, y: height / 4, r: 50, fill: 'red', text: 'FAIR', size: 20}, { x: width / 6 - 50, y: 2 * height / 4, r: 50, fill: 'red', text: 'BIAS', size: 20}, { x: 2 * width / 6 - 50, y: height / 4, r: 50, fill: 'red', text: 'FAIR', size: 20}, { x: 2 * width / 6 - 50, y: 2 * height / 4, r: 50, fill: 'red', text: 'BIAS', size: 20}, { x: 3 * width / 6 - 50, y: height / 4, r: 50, fill: 'red', text: 'FAIR', size: 20}, { x: 3 * width / 6 - 50, y: 2 * height / 4, r: 50, fill: 'red', text: 'BIAS', size: 20}, { x: 4 * width / 6 - 50, y: height / 4, r: 50, fill: 'red', text: 'FAIR', size: 20}, { x: 4 * width / 6 - 50, y: 2 * height / 4, r: 50, fill: 'red', text: 'BIAS', size: 20}, { x: 5 * width / 6 - 50, y: height / 4, r: 50, fill: 'red', text: 'FAIR', size: 20}, { x: 5 * width / 6 - 50, y: 2 * height / 4, r: 50, fill: 'red', text: 'BIAS', size: 20}, ]; let groups = svg .selectAll('g') .data(states) .join('g') .attr('transform', (d, i) => {return `translate(${d.x}, ${d.y})`;}); //Adding Circles to Diagram groups .selectAll('circle') .data(d => [d]) .join('circle') .attr('cx', 0) .attr('cy', 0) .attr('class', d => d.class) .attr('r', d => d.r) .style('fill', d => d.fill) .style('opacity', 0.3); //Adding Text for Circles groups .selectAll('text.state') .data(d => [d]) .join('text') .classed('state', true) .attr('x', 0) .attr('y', 0) .attr('font-size', d => d.size) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'white') .text(d => d.text); // LINKS - SOURCE (non-curvy) let linkSource = states.map(d => {return {'x': d.x + 50, 'y': d.y};}); linkSource.pop(); linkSource.pop(); let len = linkSource.length; for (let i = 0; i < len; i++) { if (i % 2 === 0) // source is FAIR coin -> go to BIASED { linkSource.push({'x': linkSource[i]['x'] - 5, 'y': linkSource[i]['y'] + 20}) } else // source is BIASED coin -> go to FAIR { linkSource.push({'x': linkSource[i]['x'] - 5, 'y': linkSource[i]['y'] - 20}) } } // LINKS - TARGET (non-curvy) // target node position must account for arrow width let linkTarget = states.map(d => {return {'x': d.x + width / 6 - 45 - markerWidth, 'y': d.y};}) linkTarget.pop(); linkTarget.pop(); for (let i = 0; i < len; i++) { if (i % 2 === 0) // source is FAIR coin -> go to BIASED { linkTarget.push({'x': (Math.floor(i / 2) + 2) * width / 6 - 95, 'y': linkSource[i]['y'] + height / 4 - 30}) } else // source is BIASED coin -> go to FAIR { linkTarget.push({'x': (Math.floor(i / 2) + 2) * width / 6 - 95, 'y': linkSource[i]['y'] - height / 4 + 30}) } } const links = []; for (let i = 0; i < linkSource.length; i++) { links.push(d3.line()([[linkSource[i]['x'], linkSource[i]['y']], [linkTarget[i]['x'], linkTarget[i]['y']]])); } // Add arrowheads to the svg element -- GRAY svg .append('defs') .append('marker') .attr('id', 'arrow-forward') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX) .attr('refY', refY) .attr('markerWidth', markerWidth) .attr('markerHeight', markerHeight) .attr('orient', 'auto-start-reverse') .attr('markerUnits', "userSpaceOnUse") .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', '#BBBBBB') .attr('fill', '#BBBBBB'); svg .append('defs') .append('marker') .attr('id', 'arrow-forward-2') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX) .attr('refY', refY) .attr('markerWidth', markerWidth * 1.5) .attr('markerHeight', markerHeight * 1.5) .attr('orient', 'auto-start-reverse') .attr('markerUnits', "userSpaceOnUse") .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', 'black') .attr('fill', 'black'); svg .selectAll('path.link') .data(links) .join('path') .attr('d', (d, i) => links[i]) .classed("link", true) .attr('marker-end', 'url(#arrow-forward)') .attr('stroke', '#BBBBBB') .attr('fill', 'none'); // add time step labels let time_list = [1, 2, 3, 4, 5]; svg .selectAll('text.time') .data(time_list) .join('text') .classed('time', true) .attr('x', d => d * width / 6 - 50) .attr('y', 3 * height / 4 + 100) .attr('font-size', 40) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'black') .style('opacity', 0.3) .text(d => d); return svg; }3d:T1865,base_diagram2 = { document.getElementById("advance2").disabled = false; // DIAGRAM PARAMETERS const transition_prob = `${p_switch_viterbi}`; const speed = `${spd4}`; const bias = `${p_bias_viterbi}`; // BOX CONSTANTS const width = 1200; const height = 500; // ARROWHEAD CONSTANTS const markerBoxWidth = 20; const markerBoxHeight = 20; const refX = markerBoxWidth / 2; const refY = markerBoxHeight / 2; const markerWidth = markerBoxWidth / 2; const markerHeight = markerBoxHeight / 2; const arrowPoints = [[0, 0], [0, 20], [20, 10]]; /////////////////////////////////////////////// DIAGRAM SKELETON ////////////////////////////////////////////////////// const svg = d3.create('svg').attr('viewBox', [0, 0, width, height]); // STATES let states = [ { x: width / 6 - 50, y: height / 4, r: 50, fill: '#3ab245', text: 'FAIR', size: 20}, { x: width / 6 - 50, y: 2 * height / 4, r: 50, fill: '#CD00CD', text: 'BIAS', size: 20}, { x: 2 * width / 6 - 50, y: height / 4, r: 50, fill: '#3ab245', text: 'FAIR', size: 20}, { x: 2 * width / 6 - 50, y: 2 * height / 4, r: 50, fill: '#CD00CD', text: 'BIAS', size: 20}, { x: 3 * width / 6 - 50, y: height / 4, r: 50, fill: '#3ab245', text: 'FAIR', size: 20}, { x: 3 * width / 6 - 50, y: 2 * height / 4, r: 50, fill: '#CD00CD', text: 'BIAS', size: 20}, { x: 4 * width / 6 - 50, y: height / 4, r: 50, fill: '#3ab245', text: 'FAIR', size: 20}, { x: 4 * width / 6 - 50, y: 2 * height / 4, r: 50, fill: '#CD00CD', text: 'BIAS', size: 20}, { x: 5 * width / 6 - 50, y: height / 4, r: 50, fill: '#3ab245', text: 'FAIR', size: 20}, { x: 5 * width / 6 - 50, y: 2 * height / 4, r: 50, fill: '#CD00CD', text: 'BIAS', size: 20}, ]; let groups = svg .selectAll('g') .data(states) .join('g') .attr('transform', (d, i) => {return `translate(${d.x}, ${d.y})`;}); //Adding Circles to Diagram groups .selectAll('circle') .data(d => [d]) .join('circle') .attr('cx', 0) .attr('cy', 0) .attr('class', d => d.class) .attr('r', d => d.r) .style('fill', d => d.fill) .style('opacity', d => d.fill === '#3ab245' ? 0.4 : 0.3); //Adding Text for Circles groups .selectAll('text.state-viterbi') .data(d => [d]) .join('text') .classed('state-viterbi', true) .attr('x', 0) .attr('y', 0) .attr('font-size', d => d.size) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'white') .text(d => d.text); // LINKS - SOURCE (non-curvy) let linkSource = states.map(d => {return {'x': d.x + 50, 'y': d.y};}); linkSource.pop(); linkSource.pop(); let len = linkSource.length; for (let i = 0; i < len; i++) { if (i % 2 === 0) // source is FAIR coin -> go to BIASED { linkSource.push({'x': linkSource[i]['x'] - 5, 'y': linkSource[i]['y'] + 20}) } else // source is BIASED coin -> go to FAIR { linkSource.push({'x': linkSource[i]['x'] - 5, 'y': linkSource[i]['y'] - 20}) } } // LINKS - TARGET (non-curvy) // target node position must account for arrow width let linkTarget = states.map(d => {return {'x': d.x + width / 6 - 45 - markerWidth, 'y': d.y};}) linkTarget.pop(); linkTarget.pop(); for (let i = 0; i < len; i++) { if (i % 2 === 0) // source is FAIR coin -> go to BIASED { linkTarget.push({'x': (Math.floor(i / 2) + 2) * width / 6 - 95, 'y': linkSource[i]['y'] + height / 4 - 30}) } else // source is BIASED coin -> go to FAIR { linkTarget.push({'x': (Math.floor(i / 2) + 2) * width / 6 - 95, 'y': linkSource[i]['y'] - height / 4 + 30}) } } const links = []; for (let i = 0; i < linkSource.length; i++) { links.push(d3.line()([[linkSource[i]['x'], linkSource[i]['y']], [linkTarget[i]['x'], linkTarget[i]['y']]])); } // Add arrowheads to the svg element -- GRAY svg .append('defs') .append('marker') .attr('id', 'arrow-viterbi') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX) .attr('refY', refY) .attr('markerWidth', markerWidth) .attr('markerHeight', markerHeight) .attr('orient', 'auto-start-reverse') .attr('markerUnits', "userSpaceOnUse") .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', '#BBBBBB') .attr('fill', '#BBBBBB'); svg .append('defs') .append('marker') .attr('id', 'arrow-viterbi-2') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX) .attr('refY', refY) .attr('markerWidth', markerWidth * 1.5) .attr('markerHeight', markerHeight * 1.5) .attr('orient', 'auto-start-reverse') .attr('markerUnits', "userSpaceOnUse") .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', 'black') .attr('fill', 'black'); svg .append('defs') .append('marker') .attr('id', 'arrow-viterbi-3') .attr('viewBox', [0, 0, markerBoxWidth, markerBoxHeight]) .attr('refX', refX) .attr('refY', refY) .attr('markerWidth', markerWidth * 1.5) .attr('markerHeight', markerHeight * 1.5) .attr('orient', 'auto-start-reverse') .attr('markerUnits', "userSpaceOnUse") .append('path') .attr('d', d3.line()(arrowPoints)) .attr('stroke', '#876543') .attr('fill', '#876543'); svg .selectAll('path.link-viterbi') .data(links) .join('path') .attr('d', (d, i) => links[i]) .classed("link-viterbi", true) .attr('marker-end', 'url(#arrow-viterbi)') .attr('stroke', '#BBBBBB') .attr('fill', 'none'); // add time step labels let time_list = [1, 2, 3, 4, 5]; svg .selectAll('text.time') .data(time_list) .join('text') .classed('time', true) .attr('x', d => d * width / 6 - 50) .attr('y', 3 * height / 4 + 100) .attr('font-size', 40) .attr('font-family', 'sans-serif') .attr('text-anchor', 'middle') .attr('dominant-baseline', "middle") .attr('fill', 'black') .style('opacity', 0.3) .text(d => d); return svg; }3e:[{"id":"fdd5e6441decaf969a163219d4600cb3c7178b4b7de3ac3bccaaf31c48706efe7a1be0928bacf8fe7b92027092dea04c5f29d422beb9e92276031c050ee19549","href":"https://static.observableusercontent.com/files/fdd5e6441decaf969a163219d4600cb3c7178b4b7de3ac3bccaaf31c48706efe7a1be0928bacf8fe7b92027092dea04c5f29d422beb9e92276031c050ee19549","name":"obs.csv","type":"text/csv","lastModified":1616026663881.541,"size":524086},{"id":"69b3230be0697d332801c66a244d6715778cb73e956c5a954d7b755d904a84f7238c5c7d31415e75e75359ba82fb5045a82ec79830528cf83a54e7089a7c3a41","href":"https://static.observableusercontent.com/files/69b3230be0697d332801c66a244d6715778cb73e956c5a954d7b755d904a84f7238c5c7d31415e75e75359ba82fb5045a82ec79830528cf83a54e7089a7c3a41","name":"states.csv","type":"text/csv","lastModified":1616026793336.157,"size":524086}] 2f:{"title":"Visualizing the Invisible","cells":[{"id":0,"value":"md`\n# Visualizing the Invisible\n## An Introduction to Hidden Markov Models\n\n*Eric Chen, Shashank Chandrasekaran, William Mathias*
\n**Michigan Data Science Team**, DataViz, Winter 2021\n\n\nThis notebook is a visual introduction to *hidden Markov models* (HMMs), as well as a great way for Michigan Data Science Team members to flex their dataviz skills. \n\nWe will only use as much math as is necessary to build intuition, so this should be relatively accessible to anyone with a high-school-level knowledge of probability. We hope it'll be helpful for anyone interested in learning about state-space models!\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":60,"value":"md`# 1. Background`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2017,"value":"md`Before we start, let's introduce the concept of a **stochastic process**. A stochastic or random process ^[\\\\*] is simply a sequence of random variables ${tex`\\{X_n\\} = \\{X_0, X_1, \\cdots\\}`}. Such models are often used to model phenomena that fluctuate across time – some examples include the stock market, weather, epidemics, and even human speech. \n\nA **hidden Markov model** is a type of stochastic model. In this tutorial, we'll build up to HMMs by exploring progressively more-advanced stochastic models, using visuals to build up your intuition along the way.\n\n^{[\\\\*] we will only consider *discrete-time*, *discrete-state* stochastic processes, here.}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2084,"value":"md`\n

\n## 1-A. Statistical Independence`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2069,"value":"md`Intuitively, random variables ${tex`X`} and ${tex`Y`} are **independent** if knowing the value of one tells you nothing about the value of the other. Mathematically, ${tex`P(X|Y) = P(X)`}. \n\nFor example, if the temperature was 80 degrees today, it is unlikely ^[\\\\*] that it'll drop to -20 degrees tomorrow. In this way, the weather on a given day is *not* independent from the weather on the previous day, since knowing that today was hot at least informs you about what the temperature might be like tomorrow. \n\nHowever, consider two separate (ideal, fair) coin flips, where each coin flip is its own random variable. These random variables are independent, since the value of one flip tells you nothing about the next – it's still equally likely to be HEADS or TAILS. \n\n^{[*] unless you live in the Midwest. Then that is possible.}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2023,"value":"md`\n

\n## 1-B. The Markov Property`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2089,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1484,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":2925,"value":"viewof prob = slider({min:0, \n max:1, \n step:0.1,\n description: md`transition probability, ${tex`p`}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2904,"value":"viewof spd = slider({max:1000,\n min:200,\n step:100,\n value: 600,\n description: html`animation delay`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2075,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":2041,"value":"md`# 2. Foundations`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2515,"value":"md`## 2-A. Hidden States`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2045,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":3312,"value":"md`\n

\n## 2-B. Model Specification`","pinned":false,"hidden":false,"mode":"ojs"},{"id":3850,"value":"md`To set up an HMM ^[*], we will need to specify the following three quantities:\n1. **transition probabilities**. This will be a matrix ${tex`A`} where the ${tex`(i,j)`}-th entry encodes the probability of moving to state ${tex`j`} from state ${tex`i`} in consecutive steps.\n\n2. **emission probabilities**. This will be another matrix ${tex`B`} where the ${tex`(i,j)`}-th entry encodes the probability of seeing observation ${tex`j`} when you are really in state ${tex`i`}.\n\n3. we also specify an **initial distribution** ${tex`\\pi`} across states for the first time step.\n\n^{[\\\\*] we will assume that our model is *homogeneous*, or time-invariant – AKA, probabilities are constant.}\n\n`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":3159,"value":"md`\n

\n## 2-C. *Example*: Two Coins`","pinned":false,"hidden":false,"mode":"ojs"},{"id":3872,"value":"md`Your (math-loving, not annoying) friend has challenged you to yet another coin-flipping game! This time, they have a fair coin and a biased coin, which flips HEADS with probability ${tex`p_{\\mathrm{bias}}`} and TAILS with probability ${tex`1 - `} ${tex`p_{\\mathrm{bias}}`}. To add some difficulty, your friend will switch between coins with another probability ${tex`p_{\\mathrm{switch}}`}. ^[\\\\*]\n\nThe goal is to *try and determine which coin they are using at each flip*, or alternatively, when they are cheating by using the biased coin. Remember, you can only see the results of each toss, but not which coin is being tossed. \n\nLook at the state diagram below and play around with some parameters to get a sense for how the HMM works.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":3928,"value":"html`

^{[*] we'll make a couple of simplifying assumptions:}

^{1. we let the transition probability ${tex`p_{\\mathrm{switch}}`} be the same for both coins – mathematically, ${tex`A_{12} = A_{21}`}.}

\n\n

^{2. as a consequence, it is necessary that ${tex`A_{11} = A_{22} = 1 - p_{\\mathrm{switch}}`}.}

\n\n

^{3. the fair coin is exactly that — fair — so we have ${tex`B_{11} = B_{12} = 0.5`}.}

\n\n

^{4. we will randomly pick a coin to start with, so the initial distribution ${tex`\\pi = (0.5, 0.5)`}.}

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":164,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":3530,"value":"viewof p_switch = slider({max:1,\n min:0,\n step:0.1, \n value: 0.2,\n description:md`probability of switching coins, ${tex`p_{\\mathrm{switch}}`}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":3566,"value":"viewof p_bias = slider({max:1,\n min:0,\n step:0.1,\n value: 0.8,\n description:md`probability of HEADS on biased coin, ${tex`p_{\\mathrm{bias}}`}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":3267,"value":"viewof spd2 = slider({max:700,\n min:100,\n step:50,\n value: 400,\n description: html`animation delay`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":4433,"value":"md`\nThis raises the question: *how* are we supposed to determine which coin our friend is using at each flip, from only one flip? This does not seem like enough information!\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":3226,"value":"md`# 3. Inference`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4429,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":5385,"value":"md`\n

\n## 3-A. Dynamic Programming`","pinned":false,"hidden":false,"mode":"ojs"},{"id":5371,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":3231,"value":"md`## 3-B. Forward Algorithm`","pinned":false,"hidden":false,"mode":"ojs"},{"id":5046,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":6524,"value":"html`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4704,"value":"$39","pinned":false,"hidden":false,"mode":"ojs"},{"id":6427,"value":"viewof p_switch_forward = slider({max:1,\n min:0,\n step:0.1, \n value: 0.2, \n description:md`probability of switching coins, ${tex`p_{\\mathrm{switch}}`}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":6429,"value":"viewof p_bias_forward = slider({max:1,\n min:0,\n value: 0.8,\n step:0.1, description:md`probability of HEADS on biased coin, ${tex`p_{\\mathrm{bias}}`}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":7104,"value":"viewof spd3 = slider({max:3000,\n min:1000,\n step:500,\n value: 2000,\n description: html`animation delay`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":7013,"value":"md`\n

\n\n### 3-B-5. Time Complexity\nIf we have ${tex`T`} observations and a model with ${tex`N`} hidden states, the forward algorithm has time complexity ${tex`O(N^2T)`}. \n\nThis is because we must calculate the contribution of each of the ${tex`N`} preceding states to each of the ${tex`N`} current states, repeating this process for each of the ${tex`T`} time steps. By using dynamic programming to solve this problem, we've gone from an exponential ${tex`O(N^T)`} algorithm to a polynomial-time ${tex`O(N^2T)`} algorithm – not bad!\n\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":3234,"value":"md`## 3-C. Viterbi Algorithm`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7934,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs"},{"id":9044,"value":"md`

^{(You might have noticed that we've been using red to represent *hidden states* and blue to represent *observations*. Here, we'll switch up the color scheme so you can better compare the two hidden states.)}

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7736,"value":"html`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7682,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs"},{"id":7723,"value":"viewof p_switch_viterbi = slider({max:1,\n min:0,\n step:0.1, \n value: 0.6,\n description:md`probability of switching coins, ${tex`p_{\\mathrm{switch}}`}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":7726,"value":"viewof p_bias_viterbi = slider({max:1,\n min:0,\n value: 0.8,\n step:0.1, description:md`probability of HEADS on biased coin, ${tex`p_{\\mathrm{bias}}`}`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":7733,"value":"viewof spd4 = slider({max:4000,\n min:1500,\n step:500,\n value: 2000,\n description: html`animation delay`})","pinned":false,"hidden":false,"mode":"ojs"},{"id":7956,"value":"md`\n

\n\n### 3-C-5. Time Complexity\nRecall that the Viterbi algorithm is just a modified version of the forward algorithm. Therefore, if we have ${tex`T`} observations and a model with ${tex`N`} hidden states, the Viterbi algorithm will also have time complexity ${tex`O(N^2T)`}. \n\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":9174,"value":"md`# 4. Extensions`","pinned":false,"hidden":false,"mode":"ojs"},{"id":9177,"value":"md`\nHere are some advanced topics (really, keywords) you may want to read up on.\n\n### Parameter Estimation.\n* forward-backward algorithm\n* Baum-Welch algorithm\n* expectation-maximization algorithm\n* maximum likelihood estimation\n\n### Markov Chains.\n* [stationary distributions](https://observablehq.com/@ericch99/stationary-distribution)\n* ergodicity\n* reversibility\n* continuous-time Markov chains\n* continuous-state Markov chains\n\n### Model Generalizations.\n* time-varying HMMs\n* higher-order Markov processes\n* factorial HMMs\n* Kalman filtering / linear quadratic estimation\n* particle filtering / sequential Monte Carlo\n\n\n### Related Models.\n* conditional random fields\n* dynamic Bayesian networks\n* Markov decision processes (MDPs) \n* partially observed MDPs\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":6759,"value":"md`\n\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":6562,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs"},{"id":7716,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs"},{"id":917,"value":"d3 = require('d3')","pinned":false,"hidden":false,"mode":"ojs"},{"id":2910,"value":"import {slider} from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W3e","stdlib":"1","titling":"auto"}