I believe a Markov chain is a sequence of events where each subsequent event depends probabilistically on the current event. What are examples of the application of a Markov chain and can it be used to create artificial intelligence? Would a genetic algorithm be an example of a Markov chain since each generation depends upon the state of the prior generation?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
A Markov model includes the probability of transitioning to each state considering the current state. "Each state" may be just one point - whether it rained on specific day, for instance - or it might look like multiple things - like a pair of words. You've probably seen automatically generated weird text that almost makes sense, like Garkov (the output of a Markov model based on the Garfield comic strips). That Coding Horror article also mentions the applications of Markov techniques to Google's PageRank.
Markov models are really only powerful when they have a lot of input to work with. If a machine looked through a lot of English text, it would get a pretty good idea of what words generally come after other words. Or after looking through someone's location history, it could figure out where that person is likely to go next from a certain place. Constantly updating the "input corpus" as more data is received would let the machine tune the probabilities of all the state transitions.
Genetic algorithms are fairly different things. They create functions by shuffling around parts of functions and seeing how good each function is at a certain task. A child algorithm will depend on its parents, but Markov models are interested mostly in predicting what thing will come next in a sequence, not creating a new chunk of code. You might be able to use a Markov model to spit out a candidate function, though, depending on how simple the "alphabet" is. You could even then give more weight to the transitions in successful algorithms.
$\begingroup$
$\endgroup$
(this was intended as a comment, but turned out long and longer)
A couple of points to elaborate on Ben's answer:
- It is possible to generate different models (out of existing data!) and then look for the model that best fit new data (e.g. with knn). Example:
- States = {sleep, eat, walk, work}
- Model 1: Most probable sequence on weekdays, say: sleep → sleep → eat → walk → work → work → eat → walk → sleep → sleep
- Model 2: Most probable sequence on weekends, some: sleep → sleep → eat → walk → eat → walk → sleep → sleep
- New data arrives: Which sequence is more probable that it came from? Check model 1, check model 2. Which fits better? → Assign
- Note that the previous example is oversimplified. Also note that a unit time is needed there (other than letters / words, for instance).
- You can nest Markov models. That means that you generate a model (a set of probabilities for all the states) in a "lower scale" and then use it in a more abstract model. For example, you can nest your day-scale model to a month or year (to include holidays, for instance).
Also see this link for a nice introduction and some posts in crossvalidated.
As for the question if artificial intelligence can be created by using this kind of methods, my personal (easy) answer would be no, because they only relate data and probabilities and thus belong more to the statistics and machine learning branch.
A longer answer needs to take into account the weak vs. strong AI question.
