Algorithm Suggestion for Scoring System - weighted solution 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:


Provide a list of all valid words (most likely)
Provide a list of all invalid words (likely)
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).
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)