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

<p><strong>Please take the following as some free, non-exhaustive, thoughts on your question.</strong></p>

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

<p>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".</p>

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

<p>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).</p>

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

<p>$$
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))
$$</p>

<p>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.</p>

<p>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.</p>

<p>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>

<ul>
<li>$P(valid) = 0.55$  (most likely)</li>
<li>$P(invalid) = 0.40$ (likely)</li>
<li>$P(mixed) = 0.05$ (not likely)</li>
</ul>

CC BY-SA 3.0
2013-03-27T15:46:47.647Z
2013-03-27T15:46:47.647Z
Steven
<p>This is by no mean an absolute answer but a few ideas that might or might not light up something in your head.</p>

<p>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). </p>

<p>A feature could be the <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">Levenshtein distance</a> 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. </p>

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

<p>s(word) = sum(li*fi(word)) </p>

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

<p>Note that this is a quite rough aproximation advise for the <a href="http://www.inf.ed.ac.uk/resources/nlp/local_doc/mxpost_doc.pdf" rel="nofollow">Ratnaparkhi's approach to Part of Speech Tagging</a>. You might want to look at it.</p>

CC BY-SA 3.0
2013-04-28T19:16:05.723Z
2013-04-28T19:16:05.723Z
Enrique Castaneda
<p>As you are coming from <code>SOF</code> you are looking for a pragmatic solution which may not be theoretically complete and yet such a solution is hard to be found in <code>SOF</code>. Although the information is incomplete by the nature of your question, so the trade-offs cannot figured precisely, according to your example:</p>

<ul>
<li>It is clear what to do with <code>xxx</code></li>
<li>Scoring <code>yyy</code> is highly based on missing data of your question. For  now, I guess there would be more than just one <code>yyyy</code> with 90% correlation i.g. <code>yyyyy</code> 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. <code>Google</code> 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. <code>yyyy</code> 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.</li>
<li>I would not score <code>zzz</code> 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:<code>zzz</code> is now a valid word like <code>xxx</code>, <a href="http://en.wikipedia.org/wiki/Natural_selection" rel="nofollow">mutation is selected by nature</a>)</li>
<li>After all, a reputation system for users is inevitable i.e. what <code>Wikipedia</code> does under the hood. I say inevitable because from <a href="http://en.wikipedia.org/wiki/Systems_thinking" rel="nofollow">System Thinking</a> 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).</li>
<li>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 <code>valid word</code>, <code>invalid words</code> and <code>user reputations</code> 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.</li>
</ul>

CC BY-SA 3.0
2013-03-28T06:13:38.200Z
Given that x-number of words exist in the database, it might suggest that the word that doesn't exist in the database might also be a word. Getting the average scores of each word doesn't seem to really represent the likelihood that all the words together are made of of actual words. I just need some system that could potentially boost (or penalize) the overall score based on how many of the individual words are actual words.
StackOverflowNewbie
CC BY-SA 3.0
2013-03-28T09:52:04.093Z
Approach is highly based on the fact that if your system can leverage users feed-backs (partially non real-time scoring). Method I described, cannot calculate a new word score at real time. As new users provide new combination of words there is a chance for a non existing word in dbase to be repeated by other users. This is easy to implement. If you need real-time scoring i.e. as in an exam application then only a rich database plus context evaluation can help you. Also you can use hacks i.e. using Google suggest at client side which is costly to implement by yourself.
Xaqron
CC BY-SA 3.0
2013-03-28T04:53:47.653Z
2013-03-28T05:33:41.033Z
2013-03-28T05:33:41.033Z
Xaqron
<p>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.</p>

<p>Assume the following input:</p>

<pre><code>xxx yyy zzz
</code></pre>

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

<p>So we have something like this:</p>

<pre><code>xxx = 100%
yyy = 90%
zzz = 0%
</code></pre>

<p>Assume further that the users are either going to either:</p>

<ol>
<li>Provide a list of all valid words (most likely)</li>
<li>Provide a list of all invalid words (likely)</li>
<li>Provide a list of a mix of valid and invalid words (not likely)</li>
</ol>

<p>As a whole, what is a good scoring system to determine a confidence score that <code>xxx yyy zzz</code> 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).</p>

<p>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).</p>

CC BY-SA 3.0
2013-03-28T09:25:48.103Z
I don't think there is a single answer to your question as it is asked: the definition of "valid serie" is highly dependant of the application: In a programming language, a single word not  allowed makes the serie invalid while for instance in an email, the word "sex" alone would not permit alone to identify a spam (and there is a lot of work on designing weighting schemes adaptive to each user behavior and preferences). Maybe you should precise your application?
J.y B.y
CC BY-SA 3.0
2013-03-28T21:56:21.680Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question looks more suitable for [cs.se] or [stats.se].
Kaveh
<ai.artificial-intel><formal-modeling><st.statistics>
Algorithm Suggestion for Scoring System - weighted solution
StackOverflowNewbie
# Algorithm Suggestion for Scoring System - weighted solution

(Asked by: username_0 on 2013-03-27)

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).

**Tags:** ai.artificial-intel, formal-modeling, st.statistics
> **Comments:**
> **username_1**: I don't think there is a single answer to your question as it is asked: the definition of "valid serie" is highly dependant of the application: In a programming language, a single word not  allowed makes the serie invalid while for instance in an email, the word "sex" alone would not permit alone to identify a spam (and there is a lot of work on designing weighting schemes adaptive to each user behavior and preferences). Maybe you should precise your application?  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question looks more suitable for [cs.se] or [stats.se].  

---

## 3 answers

### Answer by username_3 on 2013-03-27. Score: 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 by username_4 on 2013-04-28. Score: 0

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](http://en.wikipedia.org/wiki/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](http://www.inf.ed.ac.uk/resources/nlp/local_doc/mxpost_doc.pdf). You might want to look at it.


---

### Answer by username_5 on 2013-03-28. Score: -1

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](http://en.wikipedia.org/wiki/Natural_selection))
* After all, a reputation system for users is inevitable i.e. what `Wikipedia` does under the hood. I say inevitable because from [System Thinking](http://en.wikipedia.org/wiki/Systems_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.

> **Comments:**
> **username_0**: Given that x-number of words exist in the database, it might suggest that the word that doesn't exist in the database might also be a word. Getting the average scores of each word doesn't seem to really represent the likelihood that all the words together are made of of actual words. I just need some system that could potentially boost (or penalize) the overall score based on how many of the individual words are actual words.  
> **username_5**: Approach is highly based on the fact that if your system can leverage users feed-backs (partially non real-time scoring). Method I described, cannot calculate a new word score at real time. As new users provide new combination of words there is a chance for a non existing word in dbase to be repeated by other users. This is easy to implement. If you need real-time scoring i.e. as in an exam application then only a rich database plus context evaluation can help you. Also you can use hacks i.e. using Google suggest at client side which is costly to implement by yourself.  

---

