1
$\begingroup$

Random walks are well known from probability theory. I have the idea for hash walks. If h(x) is a hash function and a,b,c,d,e,f is a boolean sequence then the sort of hash walk I am talking about is h(x+a), h(h(x+a)+b), h(h(h(x+a)+b)+c),....

At each step in the hash walk there are only two possible next states. If the input data is sparse then you will frequently have walks that are the same. I use the idea to construct prediction trees. At the moment I am working on the idea of using Bloom filters to greatly reduce the amount of memory needed to store hash walks.

In information theory terms could you get even better generalization using less than 1 bit of input per walk step? Is there any prior literature on this topic?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Since the output of $h$ is binary, there's no much point in applying it. I mean that the walk is determined by the sequence $a,b,c$ and not by $h$ (which can either be the identity or a NOT gate..). So that's not a question about hash functions, but rather on the random walk $a,b,c,...$. Or am I missing anything? $\endgroup$ – Ran G. Jul 20 '15 at 12:23
  • $\begingroup$ Yes. You need to think about it more. Especially as real world data like images of people are highly sparse. It is a walk from a root. A walk from generality to the more specific. Along the walk you can store classifications or whatever. You already have a hash value that you can use for an auxiliary hash table for example. When I used it on English language text it showed high compression with the ability to context complete words and even sentences. Actually I think there are ways to soften up the hash function to get different effects. For example using a random projection. $\endgroup$ – SeanOCVN Jul 20 '15 at 13:44
  • 2
    $\begingroup$ 1) Do you have a specific question? At the moment this feels a little bit ill-defined and open-ended. This site is intended for specific, narrowly defined technical questions. 2) Please define the problem better. You are asking about "better generalization". Better than what? What's your definition of "generalization"? This is the first time you use the word. Lay out your goals and problem carefully, define all terms. 3) Please define your scheme better. What's the size of the input of h? the size of the output from h? What is +? Concatenation? Modular addition? $\endgroup$ – D.W.♦ Jul 20 '15 at 15:47
  • 1
    $\begingroup$ 4) What are you doing with this "walk"? What do you mean by "sparse" input data? What counts as the input -- x, or a,b,c,d,e? What does the sequence of values have to do with "walk from generality to the more specific"? I'm not following you. You seem to be using phrases that mean something specific to you, but it's hard for me to guess what you might mean. $\endgroup$ – D.W.♦ Jul 20 '15 at 15:48
  • $\begingroup$ The question is prior papers or correct keywords for a search? That seems quite specific to me. The other parts are just bonus material. If you don't really understand why it is of interest wait until someone can answer the question and then go read the listed papers. Anyway I don't think it is too difficult to understand that it could help you identify some previously seen pattern for example. $\endgroup$ – SeanOCVN Jul 20 '15 at 23:32