Paraphrasing Sentences With Software

prostoalex writes "Cornell University researchers are making progress in paraphrasing and "understanding" complete sentences in a software application. Analyzing sentences on the semantic level allows the software application to treat two sentences, expressing similar thoughts and ideas, but written in a different manner, as a single semantic unit. Significant achievements in this area could revolutionize the information searching field."

The problem is...

That's there's absolutely nothing formulaic about idioms, which comprise 80% or so of english conversation. A human learns it by years of experience, a computer has to be given programming for every idiom there is.

Re:The problem is...

a computer has to be given programming for every idiom there is.

Rubbish - Ever heard of Machine Learning?

There has been much work on resolving coreferance and named-entity recognition problems has been onging for several years, with the aim being to lead onto full NLP. This research seems interesting in that it takes work from another field (genetic sequence matching) and applies it to an NLP problem. What links them all is that in almost every case, the research involves machine learning at some point... it makes no sense to hand-code millions of case-specific rules, when a machine can learn them faster and better...

Read their paper [cornell.edu] and you'll see that indeed it's an unsupervised learning approach - even nicer in that it doesn't require you to label training examples for the algorithm...

~D

Yes.

An American friend of mine was terribly confused by the expression "Crash us a fag, mate".

First use of this technology

I think that the first and best use of this technology would be to help the editors of Slashdot find duplicate articles!

Think about the possiblities...

Of course, the biggest problem with that is that there wouldn't be nearly as many cool articles to read!

This reminds me of the Infocom classics

I always loved the text adventure games by Infocom. They were way ahead of their time, and I have been truly amazed on several occasions by the software's ability to 'understand' what I was asking it to do. Of course I'm sure this is leaps and bounds beyond what was available back then, but it's truly amazing how far ahead of their time they actually were.

There is a mailbox here.

Re:This reminds me of the Infocom classics

I always loved the text adventure games by Infocom. They were way ahead of their time, and I have been truly amazed on several occasions by the software's ability to 'understand' what I was asking it to do. Of course I'm sure this is leaps and bounds beyond what was available back then, but it's truly amazing how far ahead of their time they actually were.

Yes. I can't be the only one that is disappointed that text adventure development essentially died. The great limiting factors always used to be memory (with no disc drives, the whole game had to be stored in a very limited amount of memory) and processing speed. Now that we have both of these in abundance it should be possible to write a real "interactive novel", but I guess that will never happen. Shame, it's a great format for cell phones and pdas.

Re:This reminds me of the Infocom classics

Interactive fiction hasn't died, and you can certainly play it on your PDA. Furthermore, it's generally acknowledged that the quality of modern works has surpassed that of Infocom. Baf's guide [wurb.com] is probably a good place to dip your toes in, but there's resources all over the place and the annual competition [ifcomp.org] has just finished.

An interactive novel, at least the kind you're probably thinking about with deeply implemented characters and so forth, is probably AI-complete. It's not about the disk space and processor speed, it's about the inherent trickiness.

google?

so would this allow something like google to pick up a phrase and relate it to the results instead of just picking up keywords?

Re:google?

Just discovered this [geeklife.com]:

Now when searching Google, you can use a ~ (tilde) to find pages using synonyms of the word you're searching for. For instance, search for:

css ~help [google.com]

and you'll get sites with tutorials, guides, support, etc.

how it can be useful

one of the ways I can think of to use this technology is to improve search engine capabilities, instead of looking for exactly the same words, search engines then can look for similar sentences, giving more accurate results.
However, after reading the article, I wonder whether the research can be applied to Latin languages, as they did the research on semantic languages.

Hrm

I was too lazy to lazy to read the article so I used the Summarize feature in OS X to parse the sentences down since it seems a bit wordy.

Okay, maybe I exaggerate a bit here, I did read the article and while the summarize isn't that far off from what these guys are doing...

Google News?

I'm curious as to whether Google News, since it draws from various news sources and groups articles by topic (similar to paraphrasing, perhaps), uses any of the same techniques.

Re:Google News?

I'm curious as to whether Google News, since it draws from various news sources and groups articles by topic (similar to paraphrasing, perhaps), uses any of the same techniques.

No, but Regina Barzilay, who is the researcher featured in the article, worked (with me) on the Newsblaster [columbia.edu] project at Columbia University, where she indeed applied these techniques to multidocument summarization. Newsblaster gathers and clusters news like Google News, but produces more sophisticated summaries.

Translation software?

I'm sure this would improve translation software too, since a paraphrased sentence should be easier to translate into something sensible.

Re:Fascinating read

I wonder what its' application could be, other than to detect duplicates... Perhaps, a tool to suggest ways of rewriting sentences? Or maybe part of a more advanced grammar check?

My first thought was translation tools. GOOD translation tools that understand the grammar in the source language, and uses the grammar in the destination language to form the resulting sentence.

There has been some work on something to solve this problem, where a phrase in language A was translated to some special "universal" code, and then finally to language B. The developers would then need to make the translator translate all languages to the universal code, and vice versa. The universal code could be whatever necessary to make the software as easily as possible be able to preserve the "meaning" of the sentence.

However, if this is done, the problem could change from this:

Source: I love hot dogs.
Destination: Ich liebe heiBe Hunde. (i.e. a literal translation, from Altavista Babelfish) ... to this:

Source: I love hot dogs.
Destination: Ich liebe Nahrung. ("I love food")

In case the universal language wasn't advanced enough and the english -> universal translator conversion was "lossy". So we might exchange our current problem with mangled grammar with lots information.

Here's a web site [mundo-r.com] about it, and I'm sure there are many more.

Fascinating

Things like this are what makes academic research Really Cool and allows useful things to come about, Go Cornell.

I'd note that this is a novel approach, and, for better or for worse, it goes about doing things much differently than our minds do.

Actually, though, it's closer to how humans understand writing (stringing together atomic words/phrases in an implicit context) than previous statistical methods. ... and I'd relate my 2nd and 3rd paragraph if it wasn't 3am here. Goodnight, slashdot. :)

RD

It's been done

Microsoft Word had AutoSummarize in Word 97, or was it 2000? Anyhow it seems to be absent in Word XP. It was the trashiest thing I'd ever seen. Actually I used to use it all the time to write my abstract. It provided a nice way for me remember everything I talked about in my report, and I think it made an effort to use keywords words which came up a lot in the report. But sometimes it did things which made no sense at all. Too bad Microsoft wasn't Open Source, their AutoSummarize feature might actually be half decent by the year 2003, but instead the abandonned it to work on other projects I guess.

I looked again and whaddayaknow? I asked the paperclip about auto summarize and it is still there in the toold menu afterall! Looks like I don't have that feature installed though.

Someone help me out here

I'm too lazy to read the article.. could someone write some software to paraphrase it for me?

Japanese manuals

Finally, auto-translate, then auto-parse can rid us of these "manuals" :-)

Simon

Goodbye, Cliff Notes...

Hello, automatic paraphrasing of literature.

P.S. Just joking, kids. Stay in school!

What about...

Let's see the srtwfaoe cut its tteeh anigist tihs lttilte puzzle! (blatant reference to an older article [slashdot.org])

Another Killer App

They should use this technology to transcribe legalese into plain English and back. Like, you feed it with "Due to unanticipated circumstances as listed under the terms of the clause 17(a), we may be unable to comply with your request within this and successive fiscal year(s)", and it spits out "bugger off".

Of course, millions of lawyers worldwide would lose their jobs, but I, being bitten by them, just take it as an added benefit.

Finally ...

a "-1, redundant" generator.

Paraphrase of the article.

Without thinking too much about it, we paraphrase all the time. Trying to give a sentence to a computer to reword, is a complicated task.

At Cornell, University, researchers decided to avail themselves of two different sources of the same news and use computational biology methods to make it possible for computers to automatically paraphrase input sentences. Their first step was to compare the two different sources of the same news.

Eventually, it is hoped that this research will have benefits in computer processing of natural-language queries, translation engines, and in assisting people with certain types of reading disabilities.

The project began when two ideas came together, said one of the Cornell researchers, Regina Barzilay. Regina Barzilay is an assistant professor of computer science at the Massachusetts Institute of Technology.

The vast amount of duplicated content online is a valuable resource for computer systems learning to paraphrase. A number of reporters report the same news but using different wording. The redundant sources of news are able to assist in learning the different ways one piece of information can be paraphrased, as the same basic facts are reported in each. So with these multiple sources, you can sort out the noise and get the facts and then work out different ways of stating those facts.

Even with similar styles of writing, paraphrasing of sentences is more than just working out ans substituting synonyms. The researchers' provide a couple of common business phrases to illustrate this:

After the latest Fed rate cut, stocks rose across the board.
Winners strongly outpaced losers after Greenspan cut interest rates again.

The next step, was to use computational biology techniques to determine how much in common two sentences had and how closely they were related. The technique used was similar to when biologista are looking to see how close two sets of genes are that may have started from the same seed but then evolved. They are different but have a degree of similarity.

They important thing was to compare news sources that were written differently but covered the same event. This generated a whole set of word patterns that were kind of the same. This was exactly the core data needed to inform a computer paraphrasing technique.

The Reuters and AFP news sources were used to test the system. News was selected from English articles produced between September 2000 and August 2002.

The system developed by the researchers performs two groupings; firstly comparing articles from the same source:

Word-based clustering methods were used to identify sets of text that had a high degree of overlapping words. This method identified articles that reported distinct acts of violence occuring in Israel and the Palestinian territories.

Computational biology techniques were then used on these sets of articles to generate lattices or sentence templates for the computer to use. Each lattice contains a number of sets of words that occur in parallel and empty slots where arguments, such as locations, number of fatalities, times and dates can be inserted.

The challenge was to sort out which lattices were indeed due to different events and which were due to writing variability.

The researchers were thus able to identify common templates used by journalists to describe similar events. Ie. journalists who take the same article and change or take out a word, add a detail, reverse the sentence and so on are hereby busted.

One of the templates, or lattices, read: Palestinian suicide bomber blew himself up in NAME on DATE killing NUMBER (other) people and injuring/maiming NUMBER. In addition to the injuring/maiming variable, there are several variables within the name argument: settlement of, coastal resort of, center of, southern city, or garden cafe.

43 AFP and 32 Reuters templates were thus discovered by the system. The researchers then cross-compared these lattices.

They compared the

Obligatory Paraphrases

How do you paraphrase Slashdot ?
Ans : Dupes for nerds, stuff that matters again and again.

How do you paraphrase Microsoft Innovation ?
Ans :

Better idea

Significant achievements in this area could revolutionize the information searching field.

Not to mention the increased ability to quickly spot "re-written" bought term papers.

Interesting

There's this algorithm called Latent Semantic Analysis [coloradu.edu] which has been under development for quite some time (freely available!). It's quite good at comparing the semantic content of 2 bits of speech based on its database of many thousands of book (in fact you can specify the education level by choosing different databases).

The output of LSA has been shown to be roughly equivalent to human scorers for examining summary essays produced in tests.

Point is, that by combining this here paraphrasing algorithm with LSA, we can have computers summarizing text and other computers giving them grades on it. This takes students and teachers out of the equation entirely. Saves us big bucks and get public education back on its feet!

SCO Analysis

I tried running this on all statements and press releases coming out of SCO and Darl McBride for the last six months and after a thorough semantic analysis, this is the resulting summary:

"Pass me the crackpipe, man!"

Proudly karma-whoring since the turn of the millenium

LOLITA?

can anyone else shed any light into how far the LOLITA project (under Roberto Garigliano) got at Durham Unversity? Yeah, it's a research project, but last I heard (10 years ago) it was able to parse complete texts (for example, newspaper articles) and answer simple questions based on it. I believe ther was also work underway to make it understand/'speak' chinese/russian. There was also supposed to be some kind of 'script' support which would give it contextual information about certian situations (the common example was what contextual knowlegde do you need to know when you go into a restaurant and how can that knowledge help you understand what is said there).

Spamfilter

Shouldn't this make it possible to improve spam filters?

Advances in Automatic Text Summarization

If anyone is interested in the history of this field then I would highly recommend the book with the above title, edited by Inderjeet Mani and Mark T. Maybury. amazon [amazon.com]. Lots of very interesting articles, including discourse trees and a brief bit of stuff about summarising non-textual assets such as diagrams, video streams etc etc

Call Infocom!

Just think of the ramifications this will have for Zork. Now I'll be able to say "Will you just open the damn egg?"

For the lazy, or interested, a summary via OS X!

Set on the lowest setting, a summary of the article is:

The method could eventually allow computers to more easily process natural language, produce paraphrases that could be used in machine translation, and help people who have trouble reading certain types of sentences.

At a roughly 10% size:

The researchers used gene comparison techniques to identify word patterns from different news sources that described the same event.

The method could eventually allow computers to more easily process natural language, produce paraphrases that could be used in machine translation, and help people who have trouble reading certain types of sentences.

...When two reporters describe the same news event, for instance, they may use different details, but they tend to report about the same basic facts, said Barzilay.

...you have genes which started from the same kind of seed, and then they change during evolution [but] there is some similarity," said Barzilay.

...Given a sentence to paraphrase, the system finds the closest match among one set of lattices, then uses the matching lattice from the second source to fill in the argument values of the original sentence to create paraphrases.

At a quarter size:

The researchers used gene comparison techniques to identify word patterns from different news sources that described the same event.

The method could eventually allow computers to more easily process natural language, produce paraphrases that could be used in machine translation, and help people who have trouble reading certain types of sentences.

...When two reporters describe the same news event, for instance, they may use different details, but they tend to report about the same basic facts, said Barzilay.

...Second, to sort out sentence similarities, the researchers borrowed techniques from computational biology that determine how closely related organisms are by finding similarities among genes.... you have genes which started from the same kind of seed, and then they change during evolution [but] there is some similarity," said Barzilay.

...Lattices are made up of words or parallel sets of words that occur across several examples, and arguments, or slots, where names, dates or number of people hurt or killed occur.

...One pattern, or lattice, read: Palestinian suicide bomber blew himself up in NAME on DATE killing NUMBER (other) people and injuring/wounding NUMBER.

...Given a sentence to paraphrase, the system finds the closest match among one set of lattices, then uses the matching lattice from the second source to fill in the argument values of the original sentence to create paraphrases.

...The researchers' ultimate goal is to use the system to allow computers to be able to paraphrase like humans, and to understand paraphrases, "but that's very far [off]", said Barzilay.

...Barzilay's previous work, which used a different technique to paraphrase at the level of words and phrases rather than sentences, is part of the Columbia News Blaster project, which summarizes news stories.

...The researchers' system has the potential to accomplish the same thing by taking one human translation and creating 10 paraphrases of it automatically, she said.

...The system could be used to produce paraphrases based on a specific model, for example, for phasic readers, who find it difficult to read certain types of phrases, she said.

...For example, the system learned incorrectly that "Palestinian suicide bomber" and "suicide bomber" were the same, and that "killing 20 people" is the same as "killing 20 Israelis", said Barzilay.

How I do this in my product

I use a fairly effective algorithm to do this in my product:

I first classify the text into a category, then weight every word in the text based on how much it contributed to this classification - I then output as a "summary" of the one or two sentences in the original text that most contribute to the classification of the entire text.

Not really sumarization, but useful.

-Mark