Lexical paraphrasing (replacing one word with another) is an inherently context sensitive problem because a word's meaning depends on context. Most paraphrasing work finds patterns and templates that can replace other patterns or templates in some context, but we are attempting to make decisions for a specific context. We have developed a global classifier that takes a verb v and its context (sentence that v appears in, along with a candidate verb u, and determines whether u can replace v in the given sentence while maintaining the original meaning. The classifier makes its decision by finding other contexts that both v and u appear in, and seeing how similar these are to the given context of v. We train the classifier without supervision by utilizing a large set of local classifiers each trained to locate paraphrases of a single word. These local classifiers then generate labeled data for the global classifier.