6

I'd like to be able to identify duplicate jokes posted on a website. I can build up a reasonably large database of previously-posted jokes, and then I'd like to look at each new joke as it comes in and pick out the most "similar" jokes from the database and spit them out, in order, if my confidence that the new joke is a duplicate is above some threshold.

I could look for exact character-by-character matches but that's not very interesting, and it would fail to catch "near duplicates." For example, I'd like the following two jokes to be considered the same:

Three men walk into a bar. The first one says "ouch!", the second one says "ouch!" The third one ducks.

Three men go to the bar. The first one says "ow!!!!", the second one says "OWW!!!!!", the third one ducks.

I imagine that many duplicate jokes involve names of characters being swapped out (i.e. a story about "Little Suzy" rather than "Little Johnny", or a joke about the president with "Barack Obama" swapped for "George Bush"), and I'd like those to be counted as the same joke, too.

I've been reading about plagiarism detection algorithms and none of them seem to quite fit, since they're geared towards much larger texts (the average joke is probably only a few dozen words), or they rely on some special property of academic work (i.e. citation analysis).

I found a paper at one point that I haven't been able to find again that I thought was an interesting that went something like this: collapse each text into a vector v such that if the ith word of your vocabulary appears n times, then the value of v_i is n. Then when you get a new joke, compute the distance between it and all of the other vectors you've built; the closest vector is the most likely source text. It explored a few different variations on the idea and compared their effectiveness.

This seems like a sensible idea to me, but I wonder if it won't be too sensitive to things like swapping out names, and I can't find the paper again to check the exact details of how they handled it.

I'm not sure how I could apply other machine learning techniques to this, like an SVM or neural net, since it's basically a classification problem over a few thousand different classes with no more than a handful of examples for each class. And there's no nicely-labeled dataset out there of duplicate jokes, as far as I know.

What's a reasonable strategy for this? Can anyone point me in the direction of useful literature?

(This project is purely for fun, and I'm just looking for some semi-reasonable approximation. I know that NLP in general is very hard to do and that a real, accurate answer to this would be virtually impossible.)

EDIT (in response to the dupe flag): as I've sketched out in some comments, I don't think that string edit distance is a great approach to this because:

  • it places inappropriate weight on swapping out things consisting of multiple characters that shouldn't change the meaning (names, for example)
  • it requires me manually figuring out a good threshold for a positive match; there's no dataset for me to test it on
  • it cares about order: I'd rather have something like a bag-of-word approach because a joke can be substantively the same while flipping around sentences
  • it's potentially expensive: whenever I see a new entry, I need to recompute its string edit distance against every single joke I've seen
  • it's not very interesting (I'm doing this for fun, after all) and I'm not convinced that there isn't an algorithm that better captures the notion of "joke similarity" than straight character-by-character comparison; if someone has evidence that string edit distance is the best tool for this job, I'm open to hearing that --- but that's not an argument provided by the answer linked in the dupe flag
Improve this question
7
  • 1
    Possible duplicate of Match two strings but allow for a degree of error
    – user40980
    Commented Dec 6, 2015 at 3:41
  • Incidentally, the Levenshtein distance of the two strings you provide is 22. On the other hand, comparing the edit distance of the first string to "I wondered why the frisbee was getting bigger, and then it hit me." is 76. Folding to lower case, the difference between the two you provide is 20.
    – user40980
    Commented Dec 6, 2015 at 3:53
  • 2
    @MichaelT: I'm aware of string edit distance but I'd think the best solution here would be word-level rather than character-level, since swapping names may lead to large string edit distances (e.g. "New York City" for "LA") that we'd prefer to call a small number of word-level swaps rather than a large number of character-level swaps.
    – Patrick Collins
    Commented Dec 6, 2015 at 6:01
  • @CorbinMarch as you can see, it didn't get closed as a duplicate. However, the question as described here (even kind of with the edits) is solvable with edit distance. To get to the point where "use edit distance" isn't the answer, we need a better corpus of material to work from. However, I must agree with Brian and Ixrec in this point that once you start going down that path, you get into deep NLP problems that are not answerable within the space provided here.
    – user40980
    Commented Dec 7, 2015 at 0:04
  • As an aside, the "it's potentially expensive" - you are going to have to check each new submission against all the others no mater what the approach that is used. It will be expensive no matter what algorithm you use. This can be mitigated somewhat by using a Levenshtein Automata and serializing that so that the calculation of the calculation of this structure is done only once.
    – user40980
    Commented Dec 7, 2015 at 0:06

1 Answer 1

Reset to default
3

The simplest, naive algorithm to account for name changes skewing your edit-distance results would be to filter out proper names.

English is relatively easy to identify proper names and there are probably established algorithms and libraries out there for it. We used something similar using a Part Of Speech tagger a few years ago, but we were using (expensive) commercial packages. Again, there are probably other alternatives out there. Then, just identify proper names like Johnny or Suzy or Barack Obama, strip them out, and run an edit distance between what's left.

There are many ways to improve results based on that basic idea - try to identify common variations in duplicates and remove them as noise from your edit distance. For example, you can match and replace known synonyms with canonical representations so that "bar/pub" or "enter/go in/walk into" would be collapsed to one representation. Assuming typos and spelling mistakes are an option, a "Did you mean..." tagger could also help.

Improve this answer
1
  • Hmmm, the synonyms thing is a good idea. I suppose I'd need to run a stemmer over it all, first, to make sure the synonym lookup succeeded, after spell-checking. String edit distance is an option I suppose but it leaves me with the task of figuring out what an acceptable edit distance is to flag a positive (which is hard with no labeled data set). Another reason I was thinking of using an established document similarity measure was that it might come with a suggested threshold for a positive match. Stripping out noise like this is a very good idea, though.
    – Patrick Collins
    Commented Dec 6, 2015 at 11:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.