The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
14 views

What's the relationship of max-flow-min-cut and Markov Random Fields?

I am trying to follow this paper [1]. There is a relationship between Markov Random Fields (MRF) to max-flow-min-cut. An MRF can be represented as an undirected graph, and you can find flow through it,...
2
votes
2answers
105 views

The transition function in a Markov decision process

A Markov decision process is typically described as a tuple $\langle A,U,T,R \rangle $ where $A$ is the state space $U$ is the action space $T: A \times U \times A \mapsto [0,\infty) $ is the state ...
2
votes
1answer
40 views

Orderability of Belief States in a POMDP?

Consider a POMDP with integer states $1,2,\ldots,N$, where $N$ is finite. We thus have a complete order over the states. It seems reasonable to think that belief states for this POMDP may be ...
1
vote
1answer
65 views

Markov Chain Mixing Time of the Complete Graph

I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn). We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically 1/...
5
votes
1answer
51 views

Clarification of the definition of a POMDP

From what I understand, a $MDP=(G, A, P, R)$ (markov decision process) is represented as: A complete directed graph $G=(V, E)$ A set of actions $A_u$ for each vertex $u \in V$ A reward function $R$ ...
3
votes
0answers
31 views

Cheeger constant of a graph versus conductance of a Markov chain

Given some graph $G$ with vertices $V$ and edges $E$, its Cheeger constant $h(G)$ is well defined as $$ h(G) = \min_{S\subset V,0<|S|\leq|V|}\frac{|\partial S|}{|S|}. $$ Given some doubly-...
5
votes
0answers
114 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x \alpha(x)V(x)\\...
3
votes
0answers
65 views

Multicommodity flows with minimum congestion: NP-hard?

I have a question related to a paper of Chen, Lovasz and Pak [1]. The paper concerns the construction of the Markov chain with optimal mixing time on an arbitrary graph. They prove the optimal bound (...
1
vote
1answer
39 views

Simulating continuous time semi-Markov state machine and changing transition probability on the fly

The problem that I'm trying to solve (well, I think that I almost did, but need a review from someone more experienced) is about changing probability of the transition for semi-Markov state machine ...
2
votes
2answers
70 views

How to sample random game input that looks similar to human control?

What I would like to do is improve upon projects like 'RNG plays pokemon'. There, a computer produces a random sequence of inputs that are transmitted to an emulator and played in-game. Though this ...
2
votes
0answers
27 views

Calibrating a Markov Chain with little data

I am trying to calibrate a Markov Chain. Usually you would have the amount that "moves" from one state to the other and then the resulting value, with data at any given time with the following ...
1
vote
0answers
24 views

Mixing time of three particle systems

Is there anything known about mixing time of Markov chains for three particle systems? It is proved here http://www.ams.org/journals/tran/2005-357-08/S0002-9947-05-03610-X/S0002-9947-05-03610-X.pdf ...
4
votes
1answer
51 views

Average vs Worst-Case Hitting Time

Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can $$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to $$ H_{\rm ave} = \...
3
votes
1answer
43 views

Seemingly non sequitur in proof

I'm trying to understand a small proof in an article about computing lumpability on Markov chains. There is a small detail that I cannot understand, i.e. I don't think it follows from the argument. ...
2
votes
0answers
21 views

What is the meaning of the output weights of a Conditional Random Field (CRF) model?

Problem When train my linear chain CRF with annotated observations, I feed it with a number of sequences containing observation values and a "ground-truth" label for each observation. I'm currently ...
0
votes
0answers
29 views

Graph Centrality: spectral techniques

What is the difference between: normalizing the row of an adjacency matrix and taking the right eigenvector normalizing the row of an adjacency matrix and taking the left eigenvector normalizing the ...
8
votes
2answers
2k views

What are Markov chains?

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal state-...
1
vote
1answer
139 views

Markov Chain w/ non-stochastic matrix

I've come across a problem which at first appeared to be a markov process however the transition matrix of the graph is non-stochastic. That is, the probabilities among edges leaving a node do not sum ...
6
votes
2answers
112 views

Why are HMMs appropriate for speech recognition when the problem doesn't seem to satisfy the Markov property

I'm learning about HMMs and their applications and trying to understand their usages. My knowledge is a bit spotty, so please correct any incorrect assumptions I'm making. The specific example I'm ...
0
votes
1answer
544 views

Algorithm for finding best combination of elements

Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C. The types come with expenses: Type A's are the least expensive, and C's are the most ...
1
vote
0answers
161 views

PageRank and EigenTrust: How small should epsilon be?

For probabilistic algorithms such as PageRank and EigenTrust, the stopping case is given as $|R_{t+1} - R_{t}| < \epsilon$ (i.e. convergence is assumed). Neither the papers on EigenTrust or ...
1
vote
1answer
203 views

How are Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets related?

I am having an AI exam in two weeks, and I am still figuring out certain concepts and ideas, related to Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets (yes it is all ...
3
votes
1answer
126 views

Improve Markov Chain results

Apologies for another Markov Chain question but this one is best given its own question to avoid confusion. I am using a Markov Chain to get the 10 best search results from the union of 3 different ...
5
votes
4answers
357 views

What are the uses of Markov Chains in CS? [closed]

We all know that Markov Chains can be used for generating real-looking text (or real-sounding music). I've also heard that Markov Chains has some applications in the image processing, is that true? ...