0

I am working with a Java Library used for identifying the language of a given text. It relies on an n-gram analysis of the text to return a set of languages it might be and the "confidence" that it is that language.

I wrote a wrapper class to run it, however, it is non-deterministic (results are generally incorrect with <200 chars input, don't worry about that):

C:\wamp\www\langdetect [master]> java Detect viking rowboat
af:0.8571411945873898 lt:0.1428569473433962
C:\wamp\www\langdetect [master]> java Detect viking rowboat
af:0.5714268373011915 sw:0.2857137271014559 lt:0.14285898741269984
C:\wamp\www\langdetect [master]> java Detect viking rowboat
af:0.9999958253321346

The analysis is non-deterministic by default (can be made deterministic like so: https://code.google.com/p/language-detection/issues/detail?id=64) but my question is this:

Is there any advantage to this analysis being non-deterministic?

The only upside I can think of is that a deterministic algorithm will, statistically, be incorrect a percentage of the time (even with valid input), while non-deterministic removes this guarantee (but still is incorrect sometimes). Does this even make sense?

migrated from stackoverflow.com Jun 15 '15 at 22:22

This question came from our site for professional and enthusiast programmers.

  • I absolutely agree with not returning such high confidence with short strings. I'm not developing this library, just using it. I was thinking my wrapper class could add functionality to adjust certainty based on how long the input is. – Will Jun 3 '15 at 20:13
  • I was about to make a (slightly) rude comment and sending you to Google, but luckily tried to search myself first :) So, judging by this you actually have a randomized or probabilistic algorithm, not a non deterministic one. And with that it becomes googlable – Ordous Jul 16 '15 at 12:12
  • Ah, that is an important distinction.I don't think I would have figured that out ever.thanks for the links! – Will Jul 16 '15 at 17:31
1

Usually the benefit from using non-deterministic algorithms is simple: Runtime.

It is often used in Monte-Carlo algorithms, which basically try a predefined number of possibilities (i.e. "Is this text German?" - "No", "Is this text spanish?" - "No", "Well, no idea then".). While the deterministic solution would be to try every single possibility, which is sometimes unfeasable.

However, this is not the case in your example. In your library a set of random numbers is generated from a seed. If this seed is computed randomly, you ralgorithm is non-deterministic and will produce different results for different runs.

If your seed is constant (in this example it would be zero) however, it will produce the same result every run. This does not only not improve the result, but it also removes one important advantage: The more often you run the non-deterministic program, the better your results will become. This does not apply to the deterministic approach.

So, why should you use the deterministic approach then? One example I can think of is testing. Unit tests on random results are pretty much the biggest pain you can experience. Imagine you make a change in one part of the program and for some reason your unit-test fails. You run it again and it fails again. So you start digging, where there is nothing to find.

TL;DR:

If you want good results: Run your non-deterministic program (possibly multiple times).

If you want reproducable results (e.g. Testing): Use the deterministic approach.

  • For testing non deterministic algorithms, an injectable, explicit seed is invaluable. You can always reproduce/debug a result (pass or fail) by providing the seed, but you still get a chance to explore corner cases by running many times with different seeds. – ptyx Jul 16 '15 at 21:34
0

It sounds like it is returning results before the results have really converged. I'd find the varying results troubling and untrustworthy. The fix should be to run more samples, not use a "deterministic" algorithm that consistently returns the same misleading result. Also, if the results are unreliable with short input strings, you should not trust highly confident percentages like 0.99999: I would discount the confidence numbers, or assume error bars like 0.99999 ± 0.9.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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