Comment by j42 | Hacker News Reader

Comment by j42 | Hacker News Reader

Figured I'd chime in here since I developed an algorithm recently that could be applied to this problem with some basic ML.

Basically the first step would be shingling the text (choosing a sampling domain) and generating a MinHash struct (computationally cheap) which can then be used to find the "similarity" between sets, or, the "Jaccard Index."

If you're clever about this, you can use HyperLogLogs to encode these MinHash structs gaining a great deal of speed with a marginal error rate, all while allowing for arbitrary N-levels of intersection.

If you're looking to build a model to analyze two (or N) text bodies for stylometric similarities, I'd approach the problem in two steps:

1) Minimize the relevant input text.

- Use a bernoulli/categorical distribution to weight words according to uniqueness--NLP and sentiment extraction techniques may also help

- Design a markov process to represent more complex phrasing patterns for the text as a whole

- Filter by a variable threshold to minimize the resulting set of shingles/bins/"interesting nodes" into a computationally-manageable #

2) Use an efficient MinHash intersection to compute a similarity vector (0-1) for the two texts.

I think given the prevalence of training data (I mean, what's more ubiquitous than the written word...) you could probably tune this to a reasonable accuracy and efficient complexity.

Just a 5m thought exercise, but if anyone else has ideas I'd be curious as well :)

Could you describe in a little more detail what you mean by this sentence:

> "... use HyperLogLogs to encode these MinHash structs gaining a great deal of speed with a marginal error rate, all while allowing for arbitrary N-levels of intersection"

Thanks

Sure thing.

Let's say we have two sets, and we're trying to find out how similar they are:

    setOne = ['the','brown','fox','jumped','a','log']
    setTwo = ['the','quick','brown','log','jumped','over','the','fox']

You could use an array intersection when its small, but if you want to do this efficiently at scale you need to take advantage of probabilistic data structures.

Let's say you created a HyperLogLog for each set:

    setOne = (bitfield representing setOne)
    setTwo = (bitfield representing setTwo)

Now HyperLogLogs are cool, because you can merge them together w/o losing anything. You can't retrieve the data, but you can efficiently check if a value exists inside. You can have a false positive, but never a false negative.

You might first try simple combinatorics (a la, similarity ~= |A or B| / |A ∪ B|) however this can get hairy depending upon the representation of the HyperLogLog (sparse/dense) and its respective cardinality.

Eventually you realize you can't accept an exponentially-compounding error rate, but still need the raw efficiency, and thus you sacrifice by doubling your storage cost.

Now instead of just the initial sets, you'd also build a parallel MinHash struct:

    setOne_minhashes = [<int>, <int>, <int>]
    setTwo_minhashes = [<int>, <int>, <int>]

    setOne = (bitfield representing setOne)
    setTwo = (bitfield representing setTwo)
    setOneMinHash = (bitfield representation of setOne minhashes)
    setTwoMinHash = (bitfield representation of setTwo minhashes)

I won't go into excessive detail about the minhash algorithm itself, but essentially it provides a way to sample a large set of values by selecting/retaining the smallest output hashes. What that means is, you can then intersect the minhash bitfields as many times over as you like, and extract a predictably accurate similarity index in linear time with definable confidence bounds.

I don't have a background in ML (I'm still somewhat early in my CS Bachelor's degree, and I'm not focusing on ML anyway), but this is very interesting, regardless that I had to look up nearly every term you used.

I was initially thinking a directed weighted graph might work well here, but I'm assuming that would scale terribly relative to something like this.

Reply on news.ycombinator.com