9

A Continuous-time Markov Chain can be represented as a directed graph with constant non-negative edge weights. An equivalent representation of the constant edge-weights of a directed graph with $N$ nodes is as an $N \times N$ matrix. The Markov property (that the future states depend only on the current state) is implicit in the constant edge weights (or ...


8

On that subject I recommend you to read a very good paper by James Baker and others who were actually responsible for introduction of HMM in speech: A Historical Perspective of Speech Recognition http://cacm.acm.org/magazines/2014/1/170863-a-historical-perspective-of-speech-recognition/abstract Using Markov models to represent language knowledge was ...


7

Markov Chains come in two flavors: continuous time and discrete time. Both continuous time markov chains (CTMC) and discrete time markov chains (DTMC) are represented as directed weighted graphs. For DTMC's the transitions always take one unit of "time." As a result, there is no choice for what your weight on an arc should be-- you put the probability of ...


5

No, needing training has nothing to do with unsupervised/supervised. Supervised learners need labels, unsupervised learners do not (they do things like clustering, density estimation, dimensionality reduction). In fact you can use all of them for supervised and unsupervised learning, except maybe CRFs, since an unsupervised CRF would more likely be referred ...


5

Markov Chain Monte-Carlo is a technique for efficiently sampling from a complicated probability distribution. No matter what your (discrete) probability distribution, you can set up a markov chain so that the steady-state distribution of a random walk is the distribution you wish to sample from. You can then approximate this distribution by simulating the ...


4

An important application are Hidden Markov Models which essentially assume the underlying random distribution follows a Markov chain. One exiting application of HMMs is gene prediction in bioinformatics. The task is to consume a long (as in millions of symbols) DNA sequence and predict where important parts (genes) are located. One approach is using a Hidden ...


4

Elements of $A\times U\times A$ are triples $(a_1,u,a_2)$, where $a_1$ and $ a_2$ are elements of $A$ and $u$ is an element of $U$. The $\times$ gives the Cartesian product of its arguments.


4

The notation $T\colon A\times U\times A\to[0,\infty)$ means a function with three parameters, the first from $A$, the second from $U$, and the third from $A$, which outputs a non-negative real. It is somewhat strange that the range is stated as $[0,\infty)$ rather than $[0,1]$. In fact, a perhaps better way of thinking of $T$ is as a function from $A \times ...


3

A Hidden Markov Model could be useful here. Basically you have a Markov Chain of internal states (e.g. "i just jumped", "i'm running", "i'm ready to jump again") and for each transition of the internal state it generates an action (e.g. "f" or "j") according to a distribution that is different for each internal state. You will need to figure out how many ...


3

The approach you described sounds like the common algorithms for sampling. If by reasonable distribution, you mean a smallish finite discrete distribution, then see the following references for how to do that. You would be right that Gibbs sampling would be a worse choice, probably, when these methods apply. https://stats.stackexchange.com/questions/26858/...


3

It's not "essentially $O(1)$" to draw objects from a set with non-uniform probability: your bucketing scheme takes more than constant time. Further, sampling from a Markov chain allows you to sample without having to construct the probability distribution explicitly or even the state space, explicitly. For example, how do you propose to randomly sample ...


3

Having recently worked on this topic, I can say that the answer to both of your questions is yes. The belief states may be partially ordered for example applying the monotone likelihood ratio, or other appropriate stochastic orderings that tell when a probability mass function (pmf) $f$ -- here a belief state -- is "greater than" another pmf $g$. Roughly ...


3

Markov chains appear everywhere. Why? Because the model is so general: You are interested in a large set of objects, and you can handle local manipulations on these objects, eg. modifying an object slightly to get a new one. You want to study global properties of this set of objects, such as its approximate size. This very natural problem, which is an ...


3

Hidden Markov Models were used to model phoneme units in words for speech recognition starting in the late 1980s. an early paper cited is [9] in the following. Levinson, Ljolje, Miller, "Large vocabulary speech recognition using a hidden Markov model for acoustic/ phonetic classification" in Proc. IEEE Intl. Conf. Acoust., Speech, SIgnal Processing (New ...


2

In a nutshell, Markov chains are used to model correlated stochastic processes; a broad class of signals. If the value of the signal at any moment can be well approximated by a function of the signal values at a limited number of the the preceding moments, then a Markov model is appropriate.


2

Let $M$ be an ergodic Markov chain with stationary probability $\pi$. For a state $x \in M$, let $p_x^t$ denote the distribution of a point which starts at $x$ and performs $t$ steps according to the transition matrix of $M$. The variation distance between $\pi$ and $p_x^t$, which is a measure of the similarity between the distributions, is given by the ...


2

The availability of action $ a $ can be understood as $P_a(u, v) > 0$ for some $ v $ If an action $ a $ is not available in $ u $ then it will have not effect, this means that $P_a(u, v) = 0 $ for every possible $v$


2

It's because we're not sampling integers. If we were sampling integers, and the distribution were given explicitly, you are right, there would be simpler methods. But instead we often want to sample from a set of objects, where each object is some more complicated thing (it's not just an integer), and there's no clear way to do that.


2

The quantity $\phi(n)$ grows like $\Theta(n)$. For the lower bound, consider the following graph: a clique on $m$ vertices connected to a path of length $k = C\log m$ for an appropriate $C$ (so $n = m + k \approx m$), in which each vertex of the path is also connected to the first vertex of the path (the one incident to the clique). The maximal hitting time ...


2

The invariant states that if at some point of the algorithm, $d_1,d_2$ are in different blocks, then in every croip, $d_1,d_2$ are in different blocks. The contrapositive of the invariant states that if $d_1,d_2$ are in the same block of some croip, then they are always in the same block during the running of the algorithm. Now consider a block $S$ of your ...


2

Looks like you are a bit confused by the notion of MDP policy. There's a detailed discussion with lots of examples in this question. A policy is any possible strategy in a given environment. Example: "go $East$ in any state" is a valid strategy in your MDP (though maybe not optimal), as well as "go $West$ in any state". So there are 3 states and 2 possible ...


2

At temperature 0, simulated annealing degenerates into local search (also known as hill climbing). The problem with local search is that it gets stuck at local optima. Simulated annealing is a way to overcome this difficulty by letting the algorithm sometimes make moves that temporarily deteriorate the value of the current solution.


2

You could use gradient descent. It is possible to compute the gradient of the objective function $\varphi(A)$ in terms of $A$, i.e., the derivative of the objective function with respect to each entry of the matrix $A$. Then you could apply gradient descent. In particular, let $\varphi(A) = \|A-A_0\|_F + \|\pi(A) - \pi_0\|_2$ denote your objective function....


1

The reason that you do not find any results is thta from a scientific point of view, the well-posed questions for PTAs and MDPs are quite different: MDPs typically have a reward function assigned, while PTAs do not necessarily have to have them. It is a bit imprecise to state that the "objectives is to solve the non-determinism of a MDP" -- it depends on ...


1

One correct way is to repeat the following 10 times: pick a random starting state, and apply the Markov chain for $T$ steps. I don't know whether your first proposal gives the correct distribution in all cases. You can consider the Markov chain $A \leftarrow B \rightarrow C$ with self-loops $A \to A$ and $C \to C$ and more complicated examples in that vein....


1

Here's one approach, where we prune the set of candidates we examine based on the best combination seen so far. I don't know how well it will work; you'll probably have to implement and try it to find out. Suppose we have two sets $S_1,S_2$ of matrices, and we want to find $M_1 \in S_1, M_2 \in S_2$ that maximizes $\|M_1 \times M_2\|_1$. Here's a ...


1

There are several possible techniques. Let $P^t$ denote the matrix $P$ raised to the $t$th power. Then $(P^t)_{i,j}$ (the $i,j$-th entry of that matrix) represents the probability that if you start in state $i$, you'll end in state $j$ after $t$ steps. If $t$ is sufficiently large, this is a good approximation to the limiting value as $t \to \infty$. So, ...


1

This isn't a hidden Markov model; this is an ordinary Markov model. Take a look at Wikipedia's article on Markov chains and specifically the notion of a steady-state distribution (or stationary distribution), or read about the subject in your favorite textbook -- there are many that cover Markov chains.


1

As it happens, recalculating the event time is exactly the right thing to do. This follows from the fact that the exponential distribution is memoryless; or from the fact that exponential distribution is the time until the next event in a Poisson process. I realize this might sound miraculous and unbelievable, so let me explain why, in detail. Let's ...


1

No, there's no standard name for a process where the transpose of the transition matrix is stochastic (at least, to my knowledge). However, this process is the time-reversal of a Markov process. That's a remarkable and descriptive property that just about completely characterizes this process. In particular, it seems likely that many things we'd want to ...


Only top voted, non community-wiki answers of a minimum length are eligible