<p>If you crawl Wikipedia from this page <a href="http://en.wikipedia.org/wiki/Vector_space_model" rel="nofollow">http://en.wikipedia.org/wiki/Vector_space_model</a> you will learn a lot on similarity measures. Afterwards, you should consider reading the book of Manning, Raghavan and Schutze: <a href="http://nlp.stanford.edu/IR-book/information-retrieval-book.html" rel="nofollow">Introduction to information retrieval</a>.</p>

CC BY-SA 2.5
2010-10-15T11:04:57.240Z
2010-10-15T11:04:57.240Z
Sylvain Peyronnet
<p>(Oh good, this question hasn't been closed yet!)  On a practical level, I agree with the comments by Warren and Suresh that this question isn't answerable given the current state of the art in TCS, and it sounds more like an AI question.  But I have to wonder, does it necessarily have to be that way?  The question of how semantics arises from syntax has to be one of the most foundational questions there is, and I wouldn't want to rule out TCS having a role in answering it.  I tend to think of AI of being more like engineering and TCS like theoretical physics--we ought to be supplying the equivalent of Newton's Laws that provides some overarching principles that the AI engineers can use to go and build their intelligent machines.</p>

<p>Now, so that this answer isn't totally without actual content, here is a paper that maybe touches a little bit on this question: <a href="http://people.csail.mit.edu/madhu/papers/juba-full.pdf" rel="nofollow">Universal Semantic Communication I</a> by Juba and Sudan.  They make an attempt at modeling "meaningful communication" in terms of computational power.  I'm not sure how successful their approach is, but I do think it's important in that they are using techniques from computational complexity to analyze these issues.</p>

CC BY-SA 2.5
2010-10-15T05:36:56.023Z
Kurt: your comment is well taken, and it might indeed be interesting to model semantics, maybe even along the lines of Juba and Sudan. But is this the right forum for that ?
Suresh Venkat
CC BY-SA 2.5
2010-10-15T14:44:23.710Z
Downvoted.  The post contains interesting information, but it is related more to whether the question is in scope or not than to the question itself.  It really belongs to [Meta](http://meta.cstheory.stackexchange.com/).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-15T05:26:48.260Z
2010-10-15T05:26:48.260Z
Kurt
<p>You are looking for "lexical cohesion". Try searching for this term and you will get tons of literature. After constructing the so-called "lexical chains", well-known graph partitioning and information retrieval algorithms can be used to group them into semantic classes. There is in fact a lot of theory and algorithms behind this "post-processing". Dictionary of synonyms and antonyms is often used to construct these chains. I worked on such extraction algorithms during my undergraduate days, about 10 years back. So this field must be more advanced now.</p>

CC BY-SA 2.5
2010-10-15T21:12:23.357Z
This seems helpful, however I'm ultimately hoping to use this for comparing larger text excerpts (several sentences... perhaps paragraphs).  At first glance, this appears to apply most easily to words or short phrases.  Does it extend?
John Berryman
CC BY-SA 2.5
2010-10-16T00:12:12.877Z
Yes. It extends well. These algorithms are often combined with text summarization techniques to compare large text excerpts.
Shiva Kintali
CC BY-SA 2.5
2010-10-15T10:12:05.907Z
2010-10-15T10:12:05.907Z
Shiva Kintali
<p>I'm wondering how far along the natural language processing is in determining the semantic distance between two excerpts of text.</p>

<p>For instance, consider the following phrases</p>

<ol>
<li>Early this morning I got up and washed my car.</li>
<li>I cleaned my truck up this morning.</li>
<li>Bananas are an excellent source of potassium.</li>
</ol>

<p>Clearly (to the human reader) the first two statements are much more similar to one another than they are to the third statement.  Does there exist any theory that would allow a computer to draw the same conclusion?  What about if we allow longer excerpts such as new articles?</p>

<p><em>Meta info: this is my first post here, so feel free to direct me to a better forum for asking such a question if this isn't where I should be.  Also, feel free to retag my question with anything more appropriate.</em></p>

CC BY-SA 2.5
2010-10-14T22:53:19.097Z
This isn't in the scope of theoretical computer science since there's no rigorously specified question, and no plausible likelihood of getting such a question. Try asking an AI or NLP audience instead.
Warren Schudy
CC BY-SA 2.5
2010-10-15T02:09:41.870Z
What Warren said. If you did come up with such a definition, then questions about the best algorithm to compute this distance might be in scope.
Suresh Venkat
CC BY-SA 2.5
2010-10-15T10:30:28.797Z
NLP researchers routinely handle problems like this! The techniques they use (eg, LSA) obviously don't fully capture "meaning", but they are definitely simple and beautiful applications of linear algebra. A description of these algorithms is surely on topic here.
Neel Krishnaswami
CC BY-SA 2.5
2010-10-15T19:21:32.397Z
@Neel Krishnaswami: I would agree with what you said if the problem specified a model, then the question would be about techniques. But this seems to be about how to model an informal problem not about techniques, so this seems to be out of our scope (more suitable for an AI/cognitive science/linguistics site). On the other hand, if OP specifies a model and asks for techniques, then that would be in the scope.
Kaveh
CC BY-SA 2.5
2010-10-15T20:04:12.273Z
I opened a [discussion](http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions) on Meta about the how-to-model-this questions like this.
Tsuyoshi Ito
<ai.artificial-intel><semantics><formal-modeling>
Semantic distance between excerpts of text.
John Berryman
# Semantic distance between excerpts of text.

(Asked by: username_0 on 2010-10-14)

I'm wondering how far along the natural language processing is in determining the semantic distance between two excerpts of text.

For instance, consider the following phrases

1. Early this morning I got up and washed my car.
2. I cleaned my truck up this morning.
3. Bananas are an excellent source of potassium.

Clearly (to the human reader) the first two statements are much more similar to one another than they are to the third statement. Does there exist any theory that would allow a computer to draw the same conclusion? What about if we allow longer excerpts such as new articles?

*Meta info: this is my first post here, so feel free to direct me to a better forum for asking such a question if this isn't where I should be. Also, feel free to retag my question with anything more appropriate.*

**Tags:** ai.artificial-intel, semantics, formal-modeling

> **Comments:**
> **username_1**: This isn't in the scope of theoretical computer science since there's no rigorously specified question, and no plausible likelihood of getting such a question. Try asking an AI or NLP audience instead.  
> **username_2**: What Warren said. If you did come up with such a definition, then questions about the best algorithm to compute this distance might be in scope.  
> **username_3**: NLP researchers routinely handle problems like this! The techniques they use (eg, LSA) obviously don't fully capture "meaning", but they are definitely simple and beautiful applications of linear algebra. A description of these algorithms is surely on topic here.  
> **username_4**: @username_3: I would agree with what you said if the problem specified a model, then the question would be about techniques. But this seems to be about how to model an informal problem not about techniques, so this seems to be out of our scope (more suitable for an AI/cognitive science/linguistics site). On the other hand, if OP specifies a model and asks for techniques, then that would be in the scope.  
> **username_5**: I opened a [discussion](http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions) on Meta about the how-to-model-this questions like this.  

---

## 3 answers

### Answer by username_8 on 2010-10-15. Score: 12 | Accepted answer

You are looking for "lexical cohesion". Try searching for this term and you will get tons of literature. After constructing the so-called "lexical chains", well-known graph partitioning and information retrieval algorithms can be used to group them into semantic classes. There is in fact a lot of theory and algorithms behind this "post-processing". Dictionary of synonyms and antonyms is often used to construct these chains. I worked on such extraction algorithms during my undergraduate days, about 10 years back. So this field must be more advanced now.

> **Comments:**
> **username_0**: This seems helpful, however I'm ultimately hoping to use this for comparing larger text excerpts (several sentences... perhaps paragraphs).  At first glance, this appears to apply most easily to words or short phrases.  Does it extend?  
> **username_8**: Yes. It extends well. These algorithms are often combined with text summarization techniques to compare large text excerpts.  

---

### Answer by username_6 on 2010-10-15. Score: 1

If you crawl Wikipedia from this page <http://en.wikipedia.org/wiki/Vector_space_model> you will learn a lot on similarity measures. Afterwards, you should consider reading the book of Manning, Raghavan and Schutze: [Introduction to information retrieval](http://nlp.stanford.edu/IR-book/information-retrieval-book.html).


---

### Answer by username_7 on 2010-10-15. Score: 0

(Oh good, this question hasn't been closed yet!) On a practical level, I agree with the comments by Warren and Suresh that this question isn't answerable given the current state of the art in TCS, and it sounds more like an AI question. But I have to wonder, does it necessarily have to be that way? The question of how semantics arises from syntax has to be one of the most foundational questions there is, and I wouldn't want to rule out TCS having a role in answering it. I tend to think of AI of being more like engineering and TCS like theoretical physics--we ought to be supplying the equivalent of Newton's Laws that provides some overarching principles that the AI engineers can use to go and build their intelligent machines.

Now, so that this answer isn't totally without actual content, here is a paper that maybe touches a little bit on this question: [Universal Semantic Communication I](http://people.csail.mit.edu/madhu/papers/juba-full.pdf) by Juba and Sudan. They make an attempt at modeling "meaningful communication" in terms of computational power. I'm not sure how successful their approach is, but I do think it's important in that they are using techniques from computational complexity to analyze these issues.

> **Comments:**
> **username_2**: username_7: your comment is well taken, and it might indeed be interesting to model semantics, maybe even along the lines of Juba and Sudan. But is this the right forum for that ?  
> **username_5**: Downvoted.  The post contains interesting information, but it is related more to whether the question is in scope or not than to the question itself.  It really belongs to [Meta](http://meta.cstheory.stackexchange.com/).  

---

