Algorithm Suggestion for Scoring System - weighted solution

Question

I'm trying to validate a series of words that are provided by users. I'm trying to come up with a scoring system that will determine the likelihood that the series of words are indeed valid words.

Assume the following input:

xxx yyy zzz

The first thing I do is check each word individually against a database of words that I have. So, let's say that xxx was in the database, so we are 100% sure it's a valid word. Then let's say that yyy doesn't exist in the database, but a possible variation of its spelling exist (say yyyy). We don't give yyy a score of 100%, but maybe something lower (let's say 90%). Then zzz just doesn't exist at all in the database. So, zzz gets a score of 0%.

So we have something like this:

xxx = 100%
yyy = 90%
zzz = 0%

Assume further that the users are either going to either:

1. Provide a list of all valid words (most likely)
2. Provide a list of all invalid words (likely)
3. Provide a list of a mix of valid and invalid words (not likely)

As a whole, what is a good scoring system to determine a confidence score that xxx yyy zzz is a series of valid words? I'm not looking for anything too complex, but getting the average of the scores doesn't seem right. If some words in the list of words are valid, I think it increases the likelihood that the word not found in the database is an actual word also (it's just a limitation of the database that it doesn't contain that particular word).

NOTE: The input will generally be a minimum of 2 words (and mostly 2 words), but can be 3, 4, 5 (and maybe even more in some rare cases).

Answer 1

I don't think this question is related at all with approximation algorithms, or theoretical CS.

Please take the following as some free, non-exhaustive, thoughts on your question.

It seems to me that what you want is just the probability that a given sequence of words contains only valid words.

Let me assume that each word is chosen independently (which it isn't true). Suppose we have $k$ words, call $\sigma_i$ the i-th of such words. Call $A_i$ the event "$\sigma_i$ is a valid word" and $A$ the event "all words are valid".

Under this assumptions you have: $$ P(A) = \prod_{i=1}^{k}P(A_i) $$

so you only need to assign a probability to each word (and you've already given such a distribution in you question). However you may want to apply some smoothing: if you set $P(A_i)=0$ for some $A_i$ then also $P(A)$ will be $0$ (if you are sure that a word is not valid, then then the whole phrase cannot be valid).

A bayesian approach only requires conditional independency. For example you can compare the following two quantities (and choose the highest):

$$ P(A | \sigma_1, \dots, \sigma_k) \propto P(\sigma_1, \dots, \sigma_k | A) P(A) = \prod_{i=1}^{k}P(\sigma_i|A) P(A) $$ $$ P(A^C | \sigma_1, \dots, \sigma_k) \propto P(\sigma_1, \dots, \sigma_k | A^C) P(A^C) = \prod_{i=1}^{k}P(\sigma_i|A^C) (1 - P(A)) $$

where $P(\sigma_i|A)$ is the probability that the word $\sigma_i$ appears in a valid phrase, $P(\sigma_i|A^C)$ is the probability that $\sigma_i$ appears in an invalid phrase and and P(A) is the probability that a valid phrase shows up.

In the above we are just differentiating "valid" from "invalid" phrases. If you want to account for "completely valid", "completely invalid" and "mixed up" phrases you can do something similar.

You'll need to assign three probabilities to each word $\sigma_i$: $P(\sigma_i|valid)$, $P(\sigma_i|invalid)$, $P(\sigma_i|mixed)$ and three "a priori" probabilities, for example:

• $P(valid) = 0.55$ (most likely)
• $P(invalid) = 0.40$ (likely)
• $P(mixed) = 0.05$ (not likely)

Answer 2

This is by no mean an absolute answer but a few ideas that might or might not light up something in your head.

The first thing you should have (you do) is an extensive word DB for scoring 1 for every existing word. The next stage could be create a model with as much features as you like (want).

A feature could be the Levenshtein distance between this word and any other in the DB. If the word ends or begins with a known suffix/preffix. If the word is a composition of two known words, etc. A feature could also be the user feed back. Besides everytime you score a word you might want to keep it (from a certain score) and modify it's score everytime you see it.

Your score system could then consider an smooth version of the direct apply of your features to the word in question.

s(word) = sum(li*fi(word))

where li is a fixed parameter: 0<= li <= 1; sum(li) = 1; and fi(word) is the result of apply the i-th feature to the word.

Note that this is a quite rough aproximation advise for the Ratnaparkhi's approach to Part of Speech Tagging. You might want to look at it.

Answer 3

As you are coming from SOF you are looking for a pragmatic solution which may not be theoretically complete and yet such a solution is hard to be found in SOF. Although the information is incomplete by the nature of your question, so the trade-offs cannot figured precisely, according to your example:

• It is clear what to do with xxx
• Scoring yyy is highly based on missing data of your question. For now, I guess there would be more than just one yyyy with 90% correlation i.g. yyyyy with 80% correlation... What I go for, if possible, based on the problem, is checking which option user will pick up at that point (get a user feedback, i.g. Google suggestions) so if the word still is not in main table, spelling error is less common since user has not made a choice from provided list. Word correlation algorithm would be the heart of your solution and I have no suggestion for it with given amount of data in your question. Personally I prefer to adhere to a standard one based on my purpose rather than creating a new one. If the correlation is one-to-one it would be easy, but if the context matters i.e. yyyy is surrounded by with words and whats their position, it would become a nightmare. That case the scoring should be based on domain's Ontology.
• I would not score zzz to zero without consequences. Store them in a temporary table and every-time a new instance shows up, after checking main table, I'll check temp table and if the word is there, will score it up (not just +1, preferably a fraction of user reputation which could be considered as a mutation in compare to biological systems), but yet score it zero. After the word gets enough reputation (one of your constants which is affected by you policies; you need a bunch of these parameters in your design), I'll move it to main table and update the previous interpretations according to new fact (New Fact is:zzz is now a valid word like xxx, mutation is selected by nature)
• After all, a reputation system for users is inevitable i.e. what Wikipedia does under the hood. I say inevitable because from System Thinking perspective, you need feed-backs to keep your system alive. For example ratio of matching or non-matching words could be counted as part of this score. You can add up new ideas i.e. if a word from temp table get enough score to move to main table, the first user who suggested the word (word owner in temp table) could get a bonus for his creativity and courage, and also subsequent confirming guys, by a fraction. This is up to your policy and what you are going to motivate. Latter example will motivate users in such a way which results in fast dbase growth if it is intended. Precise of this growing dbase is dependent on how fast you move words from temp table to main table (a trade-off between growth rate and precision).
• When implementing a reputation system, consider storing real data (not information, which is processed data), your parameters and some cache tables which would be updated by triggers. New valid word, invalid words and user reputations could be calculated based on new rules as like as these rules have been used from the first day of system existence. That way upon policy changes, you will lose noting important, just interpretations will change. From here, you should analyze stored system's data periodically and update policies/rules according to new recognized patterns which could be considered as the system's knowledge. So your system's knowledge iteratively increases over the time.