From: Axel Etzold Date: 2007-08-01T17:43:10+09:00 Subject: Re: Optimizing large-scale Markov chain handler Dear Giuseppe, > > > And, something else: > > What is the probability of an n-chain of words that wasn't actually > > encountered in the training set ? It's not zero, even though the > > Hash created from the training data says so ..... > > If you think of the incidence matrix A=(a_ij) representing the > > probabilities of finding a 2-chain of words i-j, all entries with > > no such Markov chain are zero. Now, in a technique called "Latent > Semantic > > Analysis" > > > > http://en.wikipedia.org/wiki/Latent_semantic_indexing > > > > this matrix is reconstructed from a product of matrices of lower > > rank, introducing non-zero entries in the previously zero entries. > > Thus all of a sudden, there is a small probability of finding that > > particular chain now. > > Aha, excellent link, thanks. This is really interesting. I wonder if > it's > possible to take it to higher orders and write the n-th level tensor > as a product of lower level tensors ... wonder what kind of speed hit > it would take. > What you would need in order to generalize LSA to higher orders is a generalization of the singular value decomposition (SVD) to tensors. There are plenty of links, such as this one: http://www.cs.cornell.edu/cv/OtherPdf/William.pdf to do that. If you'd consider doing statistical tests to find longer chains that occur significantly more often than they should given the product of shorter chains, you can make use of the following: 1.) For the chi-square test, always, if at all, the hypothesis of independence for an entire sample of chains (of different length) gets rejected, if it contains chains whose occurrence probabilities is much different from the product of shorter chains which make it up. But it's tiresome to consider all the subsets of some set of cardinality (20000)^n -- and none of the number-crunching languages is fast enough to do that for you anyway ;-) You see which ones are the tricky candidates when you look at how much they contribute to the test statistic - the big contributors make the test fail for the whole sample. 2.) As a product of big numbers is always bigger than a product of small numbers, you can find long chains with deviant probability iteratively: they will always contain subchains with deviant probability. So, with 20000 words, I'd start looking at the probabilities of 2-chains, filter out possible candidates, then consider 3-chains etc ... > > I join Ed Borasky in suggesting some number-crunching computer language > > + Ruby interface for dealing with big amounts of data, but maybe > > you can reduce it all a bit ? > > Well, going out of Ruby would sort-of defeat some of the (learning) > purposes of this project, but for serious application it's something > I should really look into, especially to do matrix manipulations > as suggested in your last points. Mmmh, it is often argued that Ruby is slow in comparison to other languages, when you consider the execution time of some pre-defined task. Entire webpages are dedicated to this claim. But rarely ever do these comparisons take into account how much time you need to THINK and code. I've often found the execution time of some task infinite with other languages, because they don't leave you enough time to think about the problem, as you always bother about a million implementation details that obscure the real memory and computing needs. I now think that it is perfectly feasible to do a 6 or longer Markov chain handler entirely in Ruby, and fast enough, whereas many brute-force approaches with some "fast" language will take an infinite amount of both space and time. > Thanks a lot for the suggestions, Glad to be of help :) Best regards, Axel -- GMX FreeMail: 1 GB Postfach, 5 E-Mail-Adressen, 10 Free SMS. Alle Infos und kostenlose Anmeldung: http://www.gmx.net/de/go/freemail