318 test 2

Question 1

What is probabilistic modeling? (3)

Answer 1

• It utilizes the effects of random occurrences or actions to forecast future possibilities.
• This method is quantitative, focusing on projecting various possible outcomes.
• It can predict outcomes that may extend beyond recent events.

Question 2

What does nondeterminism in algorithms mean in computer science?

Answer 2

In computer science, nondeterminism refers to an algorithm that can exhibit different behaviors on different runs with the same input, as opposed to a deterministic algorithm.

Question 3

What is the Markov property?

Answer 3

• the conditional probability distribution of
  future states of the process depends only on the present state
• It implies a lack of memory in the process, where past events do not influence future

Question 4

What is a Markov chain?

Answer 4

• A Markov chain is a discrete-time stochastic process.
• It satisfies the Markov property.

Question 5

How does a Markov chain differ from a continuous-time stochastic process?

Answer 5

Unlike continuous-time stochastic processes, a Markov chain specifically operates in discrete time intervals.

Question 6

Time Series

Answer 6

• a series of data points ordered in time (discrete-time data)

Question 7

Univariate

Answer 7

: one variable is varying over time

Question 8

Multivariate

Answer 8

: multiple variables are varying over time

Question 9

examples of Markov chains

Answer 9

• stock market
• Random walk on a grid (see slide)
• Weather forecast

Question 10

How can one characterize real signals in terms of signal models?

Answer 10

• provide a basis for a theoretical description of signal processing systems
• enhance understanding of the signal source even if the source is unavailable
  (through simulation of the real-world process)
• enable building prediction systems, recognition systems, identification systems

Question 11

what are 2 Approaches to signal modeling

Answer 11

. Deterministic models
Statistical models:

Question 12

Deterministic models:

Answer 12

use known specific properties of a signal (amplitude, frequency)

Question 13

2. Statistical models:

Answer 13

characterize only statistical signal properties (Gaussian, Poisson)

Question 14

what are the Three fundamental problems in Hidden Markov model (HMM) design and analysis, and what do they each mean:

Answer 14

likelihood, best sequence, adjust parameters to account for signals

1.Evaluation of the probability (or likelihood) of a sequence of
observations generated by a given HMM
2. Determination of a “best” sequence of model states
3. Adjustment of model parameters so as to best account for the observed signals

Question 15

what is a stochastic model

Answer 15

A stochastic model is a type of mathematical or computational model that incorporates randomness and unpredictability as intrinsic elements.

Question 16

How do simpler Markov models differ from HMMs?

Answer 16

In simpler Markov models, states are directly observable.
In an HMM, the state sequence the model passes through remains hidden.

Question 17

What are some applications of Hidden Markov Models in temporal pattern recognition?

Answer 17

• speech
• handwriting
• gesture recognition
• part-of-speech tagging
• musical score following
• partial discharges
• bioinformatics

Question 18

understand the cointoss example for HMM

Question 19

is a 3 state model for a coin good? how many unknow parameters does a 3 state model have? explain why or why not

Answer 19

• if the actual experiments use only a single coin, the 3-state model would be
  highly inappropriate as the model would not correspond to the actual physical event

Question 20

understand the ball and urn problem

Question 21

HMM state

Answer 21

• These represent the different conditions or configurations that can produce the observations but are not directly visible.
• Example: In weather modeling, the states might represent “sunny”, “cloudy”, and “rainy”. In the urn example, they represent different urns with specific distributions of colored balls.

Question 22

state transition probabilities

Answer 22

• these indicate the probability of transitioning from one state to another.
• Example: In the weather example, aij could represent the probability that a sunny day follows a cloudy day. In the urn example, aij would represent the probability of choosing urn j after urn i.
• This creates a total of N^2 transition probabilities because there are
  N probabilities for each of the
  N states.

Question 23

urn example: initial state probability:

Answer 23

• This is the probability distribution over the initial state, i.e., where the process is likely to start.
• Example: For the weather, it might be the historical likelihood of the weather being sunny, cloudy, or rainy at the start of the observation period. In the urn example, it would be the likelihood of starting from each specific urn.

Question 24

Likelihood of the observed sequence:

Answer 24

Given the model, how likely is the sequence of observations to occur?

Question 25

what is “hidden” in the urn problem

Answer 25

• the process of picking the ball
• The Markov process itself cannot be observed, only the sequence of labeled balls

Question 26

what are the two parameters of HMM

Answer 26

• TRANSITION PROBABILITIES and
  INITIAL STATE PROBABILITIES,
• and (ii) OUTPUT PROBABILITIES

Question 27

TRANSITION PROBABILITIES

Answer 27

The transition probabilities control
the way the hidden state at time T is chosen given the hidden state at time T-1

Question 28

what are the 5 HMM characteristics

Answer 28

• N number of states
• M number of distinct observation symbols
• state transition probability distribution
• observation symbol probability distriution
• initial state distribution

Question 29

what are the 3 things you need to fully define a HMM model

Answer 29

• Two parameters: the number of states (N) and the number of observation symbols (M).
• The observation symbols themselves, which can be either discrete or continuous.
• Three sets of probabilities: the transition probabilities (A), the observation probabilities (B), and the initial state probabilities (π).

compact notation: lambda = (A,B,pi)

Question 30

what are the 3 basic problems in HMM:

Answer 30

Efficiency, state, optimize

1. given observation sequence, how do we efficiently compute the probability of the observation sequence given the model. Aka scoring:
   - how well
   a given model matches a given observation sequence.
2. how to choose optimal state
   - aka: attempting to uncover the
   hidden part of a model.
   - there is no correct state
   - state is chosen based on situation
3. how do we optimize model parameters?
   - train then fit the data

Question 31

what are the ways you can compute the probability of the given model

Answer 31

brute force: is by enumerating each and every possible state sequence of length T. This could take a while though.

Question 32

how does HMM generate a sequence of observations?

Answer 32

first select the first state based on the initial probability, namely Pi

using that state and transition matrix we can get state2.

rinse and repate

Question 33

what is the time complexity for HMM

Answer 33

2T * N^T
- T represents the length of the observation sequence
- N represents the number of possible states