Algorithm for Negating Sentences

I was wondering if anyone was familiar with a开发者_运维技巧ny 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?

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.

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.

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.

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.

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.

For a rule-based negation approach, you can take a look at the Python module negate¹.

^{1 Disclaimer: I am the author of the module.}

As for some papers related to the topic, you can take a look at:

• Understanding by Understanding Not: Modeling Negation in Language Models
• An Analysis of Natural Language Inference Benchmarks through the Lens of Negation
• Not another Negation Benchmark: The NaN-NLI Test Suite for Sub-clausal Negation

Nice demos using NTLK - http://text-processing.com/demo and a short writeup - http://text-processing.com/demo/sentiment/.