Algorithm for Negating Sentences

Question

I was wondering if anyone was familiar with any attempts at algorithmic sentence negation.

For example, given a sentence like "This book is good" provide any number of alternative sentences meaning the opposite like "This book is not good" or even "This book is bad".

Obviously, accomplishing this with a high degree of accuracy would probably be beyond the scope of current NLP, but I'm sure there has been some work on the subject. If anybody knows of any work, care to point me to some papers?

Answer 1

The naïve way of course, is to try to add "not" right after {am,are,is}. I have no idea how this will work in your setting though, it will probably only work with predicate-like sentences.

Answer 2

For simple sentences parse looking for adverbs or adjectives given the English grammar rules and substitute an antonym if only one meaning exists. Otherwise use the correct English negation rule to negate the verb (ie: is -> is not).

High level algorithm:

1. Look up each word for it's type (noun, verb, adjective, adverb, conjunction, etc...)
2. Infer sentence structure from word type sequences (Your sentence was: article, noun, verb, adjective/adverb; This is known to be a simple sentence.)
3. For simple sentences, choose one invertible word and invert it. Either by using an antonym, or negating the verb.

For more complex sentences, such as those with subordinate clauses, you will need to have more complex analysis, but for simple sentences, this shouldn't be infeasible.

Answer 3

There's a similar process for first-order logic. The usual algorithm is to map P to not P, and then perform valid translations to move the not somewhere convenient, e.g.:

Original:    (not R(x) => exists(y) (O(y) and P(x, y)))
Negate it:   not (not R(x) => exists(y) (O(y) and P(x, y)))
Rearrange:   not (R(x) or exists(y) (O(y) and P(x, y)))
             not R(x) and not exists(y) (O(y) and P(x, y))
             not R(x) and forall(y) not (O(y) and P(x, y))
             not R(x) and forall(y) (not O(y) or not P(x, y))

Performing the same on English you'd be negating "If it's not raining here, then there is some activity that is an outdoors activity and can be performed here" to "It is NOT the case that ..." and finally into "It's not raining and every possible activity is either not for outdoors or can't be performed here."

Natural language is a lot more complicated than first-order logic, of course... but if you can parse the sentence into something where the words "not", "and", "or", "exists" etc. can be identified, then you should be able to perform similar translations.

Answer 4

While I'm not aware of any work that specifically looks at automatically generating negated sentences, I imagine a good place to start would be to read up on linguistics work in formal semantics and pragmatics. A good accessible introduction would be Steven C. Levinson's Pragmatics book.

One issue that I think you'll run into is that it can be very difficult to negate all the information that is conveyed by a sentence. For example, take:

John fixed the vase that he broke.

Even if you change this to John did not fix the vase that he broke, there is a presupposition that there is a vase and that John broke it.

Similarly, simply negating the sentence John did not stopped using drugs as John stopped using drugs still conveys that John, at one point, used drugs. A more thorough negation would be John never used drugs.

Some existing natural language processing (NLP) work that you might want to look at is MacCartney and Manning 2007's Natural Logic for Textual Inference. In this paper they use George Lakoff's notion of Natural Logic and Sanchez Valencia's monotonicity calculus to create software that automatically determines whether one sentence entails another. You could probably use some their techniques for detecting non-entailment to artificially construct negated and contradicting sentences.

Answer 5

There is an algorithm (trigger-word based) for negation detection in medical reports. You may be able to reverse the logic to algorithmically negate sentences in non medical text (with a modified list of negation phrases, of course).

http://www.dbmi.pitt.edu/chapman/NegEx.html

http://www.dbmi.pitt.edu/chapman/ConText.html

Answer 6

I'd recommend checking out wordnet. You can use it to lookup antonyms for a word, so you could conceivably replace "bad" with "not good" since bad is an antonym of good. NLTK has a simple python interface to wordnet.