# Tag Info

10

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

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 ...

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 ...

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 ...

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 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 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 What is known about the complexity of finding optimal policies for POMDPs indicates that solution by Linear Programming is not possible in the general case. When the decision horizon is bounded (finite), finding optimal POMDP policies is PSPACE-hard (Papadimitriou and Tsitsiklis, 1987). When the decision horizon is infinite and we are using e.g. the ... 3 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, ... 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 Hidden Markov Models were used to model phoneme units in words for speech recognition starting in the late 1980s. an early paper cited is  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 ... 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 We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let$\ell(a,b)$denote the probability that the extension became$b-a$due to a move to$a$, and let$r(a,b)$denote the probability that the extension became$b-a$due to a ... 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 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 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 answer to your question very much depends on the values of the probabilities$a_{ij}$. If all are non-zero, then the DTMC forms one single strongly connected component and the probability of reaching$x=3$is therefore$1$(it is$1$for any state in such a case in fact). This result comes from the Long-run theorem, which says that any finite DTMC ... 1 One can verify that the following matrix$\Gamma$has the desired properties:$\Gamma = [\pi]Q - Q^{\top}[\pi]$, where$[\pi]$is a diagonal matrix with diagonal elements being the stationary distribution. This construction relates closely to the reversibility of a Markov chain as far as I know. 1 Are there existing algorithms for it? Are there any algorithms related to the problem? Theoretical one: https://en.wikipedia.org/wiki/Sequitur_algorithm Practical one: https://encode.ru/threads/1909-Tree-alpha-v0-1-download 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

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 ...

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