Seeking Prior Art on Markov-Based SPAM Filters? 36
"Not too long ago, I was discussing it with a co-worker who has a degree in Electrical Engineering. She had taken an AI class in college which mentioned the idea of negative examples for Markov models, and this was well before the year 2000. The bottom line is that I think I have a great idea that could potentially add to our collective arsenal against the ever-growing SPAM problem. I would very much like to work on it and publish it under GPL, but before I can do this, I have to protect my self against the patent and the large pocketbook of Mitsubishi.
I'm not asking for legal advice. I have already consulted an attorney, and it was suggested that I should remove the SourceForge project, which I have done. I also attempted to contact the EFF (no luck so far). I'm asking for those of you out there who are familiar with this sort of thing to help me to find verifiable prior art that dates from before the 2000 patent. I would very much like to share with the world my ideas and the code I have written, but this is standing in our way."
hummmm (Score:1)
How about... (Score:1)
--
drug, n: A substance that, injected into a rat, produces a scientific paper
Andrei (Score:3, Interesting)
Andrei Markov himself used his models to filter text. Not e-mails obviously, but poetry.
He would both write and solicit poetry and he devised what are now know as markov models to assess poetry for aesthetic quality. Sounds like a silly idea now, but this was in the Victorian era when science and maths were blossoming. It was believed that everything could be measured and quantified; even philosophical qualities such as 'goodness' of poetry.
So,
step 1 : first search for rhyme and meter.
step 2 : then search for spamlike characteristics.
Re:Andrei (Score:2)
step 4: PROFIT!
This idea.... (Score:2)
Obviosly Not (Score:3, Insightful)
The full term in patent law is 'obvious to one with ordinary skill in the art'.
In other words, it has to be REALLY obvious.
Re:Obviosly Not (Score:1)
On the other had, if "ordinary" means someone who has had a college education in the field (which seems to be a reasonable definition), and "the art" is AI, and then it does seem qualify as obvious.
Re:Obviosly Not (Score:4, Informative)
Since this is law, not programming, definitions of terms are worked out over time. One thing to keep in mind is that in an infringement trail, if you try to assert obviousness to invalidate a patent, the burden of proof is on you.
Interestingly, the long-felt commercial need for an effective spam filter may put the use of Markov algorithms as spam filters into the 'non-obvious' category, and thus patentable.
Here is how it is normally done in an infringement case:
The court MUST determine obviousness based on four factual inquiries:
(1) the differences between the prior art and challenged claims;
(2) the level of ordinary skill in the field of the pertinent art at the time of plaintiff's invention;
(3) what one possessing that level of skill would have deemed to be obvious from the prior art reference; and
(4) objective evidence of obviousness or nonobviousness.
See B.F. Goodrich Co. v. Aircraft Braking Systems Corp., 72 F.3d 1577, 1582 (Fed.Cir.1996); Hoover Group, Inc. v. Custom Metalcraft, Inc., 66 F.3d 299, 303 (Fed. Cir. 1995). It is important to note, however, that the test endorsed by the United States Supreme Court contained only a three part inquiry, which does NOT mandate that secondary considerations be considered. Rather, the Supreme Court test, which was set forth in Graham v. John Deere Co., 383 U.S. 1, 86 S.Ct. 684, 15 L.Ed.2d 545 (1966), states that secondary considerations "might" be useful in determining obviousness. Graham v. John Deere Co., 383 U.S. at 17-18. Nevertheless, the Graham factors as set forth by the Supreme Court are:
(1) the scope and content of the prior art;
(2) the differences between the prior art and the claims at issue; and
(3) the level of ordinary skill in the pertinent art.
Graham v. John Deere Co., 383 U.S. at 17.
Notwithstanding, today secondary considerations of obviousness MUST be considered by the court before reaching a conclusion on obviousness. These secondary considerations include, but are not limited to:
(1) the commercial success of the invention;
(2) whether the invention satisfied a long-felt need in the industry;
(3) failure of others to find a solution to the problem at hand; and
(4) unexpected results.
B.F. Goodrich, 72 F.3d at 1582; see also Hybritech, Inc. v. Monoclonal Antibodies, Inc., 802 F.2d 1367, 231 U.S.P.Q. 81 (Fed. Cir. 1986), cert denied, 480 U.S. 947 (1987).
Re:Obviosly Not (Score:2)
If Markov Models have been used to classify text, then the only potentially novel part of this invention is the following two ideas:
1) email is text
2) the classification of email into "wanted" and "unwanted" is usefull
Both are obvious.
What's next, a patent on counting sheep? (Score:2, Insightful)
This is absurd. The whole point of mathematical techniques is that they work no matter what you apply them to--which is why you didn't used to be able to patent mathematics.
If this keeps up we'll start seeing patents on "counting small ovoids" and "counting imaginary woolly creatures" and people will be posting here asking if anyone can prove prior art on counting sheep.
General purpose mathematical tools should be wide open, patent free for any purpose because they are general purpose tools!
-- MarkusQ
Re:What's next, a patent on counting sheep? (Score:4, Informative)
Current patent law does forbid patenting natural law, including mathematical principals. The problem is not the lack of that law, but the fact that clever lawyers have been successful in shaving ever closer to effectively getting coverage of an algroithm.
In this patent what we have is the following claim:
1. A Markov model discriminator system comprising:
means for providing an input sequence to be classified;
means coupled to said means for providing an input sequence for performing two different model likelihood calculations based on two different Markov model parameters representing two different classes of examples, each class having a predetermined characteristic on which discrimination between classes is based;
means for comparing said likelihood calculations as to which of said characteristics said input sequence is likely to exhibit based on said comparison, thus to classify said input sequence; and
means for training said means coupled to said input sequence for performing said two calculations by generating said Markov model parameters taking onto account both negative and positive examples of said different classes.
Now notice that nowhere is there an attempt to claim ownership of the actual algorithm, only means of implementing that algorithm.
Another key word here is "comprising". This word is key to understanding what is covered by this invention. In this case it covers any means of implementing the process described that contains all of the steps described. Other steps can be added and the patent would still apply.
This link gives a good overview on how to read a patent claim.
http://www.tms.org/pubs/journals/JOM/matters/ma
Re:What's next, a patent on counting sheep? (Score:2)
Now notice that nowhere is there an attempt to claim ownership of the actual algorithm, only means of implementing that algorithm.
You are, of course, quite correct. I'm out of step with my times, and just enough of a fuddy-duddy to think that the means of implementing an algorithm (in the sense of "implementing" they are using here) is itself an algorithm. If you can't patent an algorithm (say, counting base 10) and you can't patent the fact that a particular real-world-domain (say, sheep) falls within the algorithm's domain of aplicabilty (e.g., the fact that sheep are enumerable), then there shouldn't be anything left to patent in these cases.
Lawyers who would grant the points just mentioned but still justify a patent on counting sheep on the grounds that counting is somehow a novel means to enumerate something are (IMHO) either weak on math or weak in ethics. The same goes for the patent at issue. You shouldn't have to look for prior art. If the process doesn't work, it isn't an "invention" and the patent should not stand. If it does work, the fact that it does is part of natural law (which has been discovered, not invented) and the patent still shouldn't stand.
Claiming "means" to apply math to a problem is pure smoke.
-- MarkusQ
Re:What's next, a patent on counting sheep? (Score:2)
Not really. The 'means' means a physical implementation, i.e. a computer that performs the algorithm. The strength of a patent like this is in in how broad a coverage you can get of the means. Often you can claim the means is a computer, and have enough coverage for practical purposes. This is what a lot of patents, say like the RSA patent have done.
Claiming "means" to apply math to a problem is pure smoke.
In this case I would agree, because of the way the first claim is phrased it seems to cover a very wide range of physical means of implementing the algorithm.
One thing that often confuses the issue of patents coverage of algorithms is the 'process patent'. When you think of a process as an algorithm you can be led to think that the patent is covering a mathematical law. That is not really the case; many algorithms can be derived from the same mathematical law. And in fact a process need not have a mathematical basis at all.
For example, I wonder if a clever mathematician, given the process here could not work out an alternative algorithm that results in the same ending.
Re:What's next, a patent on counting sheep? (Score:2)
The 'means' means a physical implementation, i.e. a computer that performs the algorithm.
I would also object to them patenting the use of a computer do to what a computer is intended to do (perform any algorithm that can be coded for it).
That is not really the case; many algorithms can be derived from the same mathematical law.
But the fact that they can be derived is itself a mathematical law. I think this is the crux of my objection. Mathematics isn't just the axioms, it's the whole set of true statements that can be derived from them (including statements of the form "Given the set of inputs I and the set of steps S, the result R of performing S on I will have property P").
And in fact a process need not have a mathematical basis at all.
Fine, they can patent those. The patent in question, however, isn't one of them.
For example, I wonder if a clever mathematician, given the process here could not work out an alternative algorithm that results in the same ending.
*laugh* Sure thing. You wouldn't even have to be clever. I still object to this way of looking at things, but if you take it as a given, there is a simple "algorithm" for coming up with a different "process" that yields the same result:
- Compile process-1 to a non-deterministic finite state autmomaton (if you can write a program for process-1) you can do this.
- Enforce an ordering on the state transitions that leads to a different series of steps than were found in process-1.
- Call this process-2.
- If needed, lather, rinse, and repeat.
-- MarkusQRe:What's next, a patent on counting sheep? (Score:2)
This is why I think many of these kinds of patents will untimately fail. The only fly in the ointment is the 'doctrine of equivalents' which is in a giant legal muddle right now. Sooner or later I expect some legislation in this area - courts are handing down grossly conflicting rulings on what this means.
http://www.tms.org/pubs/journals/JOM/matters/ma
I used to be a researcher in the field of synthetic polymers. The patent literature in this area is a real bear - but if you had the right attitude you could make it a tool to aid your work. My boss used to say that the patent literature is a map leading you to new results.
Ultimately I think that this is what the software industry will come to. Programmers will need to understand the patent literature in their area of expertise, just like technical practioners in other fields do now. I think it's very much a sign of the immaturity of the software field that we have this great hue and cry over software patents. The fact of the matter is that finding a new way to calculate an FFT is IMPORTANT and the inventor should be well rewarded.
Business method patents, on the other hand, are just WRONG. They have nothing to do with the advancement of technology that was envisioned by Article 1, section 8.
To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries. .
Business process? Poppycock.
Re:What's next, a patent on counting sheep? (Score:2)
Ultimately I think that this is what the software industry will come to. Programmers will need to understand the patent literature in their area of expertise, just like technical practioners in other fields do now. I think it's very much a sign of the immaturity of the software field that we have this great hue and cry over software patents. The fact of the matter is that finding a new way to calculate an FFT is IMPORTANT and the inventor should be well rewarded.
It may be a sign of immaturity in "the software industry" but I am more fond of "computer science" and in that context it is the patents that are a sign of immaturity. Mathematics at least grew out of that particular my-me-mine stage hundreds of years ago, and I still harbour a hope (faint, at this point, but still flickering) that computer science will make a comeback and reclaim the ground that has been lost to the computer industry.
Why, you might ask? There are obvious advantages to the present state of affairs, including funding and mainstream acceptability. But there are a number of serious disadvantages, not the least of which is the noise it injects into the conceptual space:
- A tendency to rename extent concepts and play up difference in closely related concepts, rather than seeking underlying patterns hidden connections.
- A warping of priorities away from deeper, long term questions towards faddish, buzzword driven crud.
- The erection of lots of fences intended to limit the scope of enquiring minds.
A guess I lump the computer industry in with the music industry, the fast food industry, the sex industry, etc. in that they are all (reasonably successful) attempts to turn something that is rewarding in its own right into a "product" that can be mass marketed, and in the process trample much of the charm of the original. I agree inventing a better algorithm should be rewarding, just as good sex or getting a tricky syncopation just right should be rewarding. But I differ by thinking they are intrinsically rewarding.I tend to use open source software and oppose software patents for the same reasons that I prefer sex with amatures instead of professionals, would rather play a piano than a CD, and find math books more entertaining than "reality television". As I believe I mentioned earlier in the thread, I suspect I am out of step with my times.
-- MarkusQ
P.S. Thanks for keeping up this thread; conversation between people whose views differ is also on my list of the best things in life.
Re:What's next, a patent on counting sheep? (Score:2)
You don't really believe that, do you? If this were really true, mathematics journals would publish their articles without author's names attached to them, and their would be no Fields Medal. The fact is that the method of keeping score is different, that's all.
# A tendency to rename extent concepts and play up difference in closely related concepts, rather than seeking underlying patterns hidden connections.
# A warping of priorities away from deeper, long term questions towards faddish, buzzword driven crud.
# The erection of lots of fences intended to limit the scope of enquiring minds.
This sounds to me like the traditional lament of the academic when he finds his pursuit has a practical use.
The engineer who takes joy from building something people can use has a different view.
We need both.
As I believe I mentioned earlier in the thread, I suspect I am out of step with my times.
The British have a long tradition of toleration of eccentricity that is sadly lacking in the US.
Re:What's next, a patent on counting sheep? (Score:2)
MarkusQ: Mathematics at least grew out of that particular my-me-mine stage hundreds of years ago
the eric conspiracy: You don't really believe that, do you? If this were really true, mathematics journals would publish their articles without author's names attached to them, and their would be no Fields Medal. The fact is that the method of keeping score is different, that's all.
Sorry, I should have been clearer. I wasn't talking about squables over giving/taking credit for discoveries, I was talking about the practice of trying to control the use of the discoveries as if the were the property of the discoverer. This was common in Europe at least from the time of the Pythagoreans through 1600 or so [st-and.ac.uk].
To my mind, the present climate of "intelectual property" in software is about as petty and counter productive as that of pre-Renaissance mathematics. Petty, for obvious reasons and counter-productive because trying to control what people can think (or what thoughts they can use), no matter what your motives, is never good for science.
This sounds to me like the traditional lament of the academic when he finds his pursuit has a practical use.
No, the lament only comes out when the practical people jumping on the band waggon that the academics built start trying to boss the academics around and impose goals and limits based on their lust for gold instead of the academics lust for knowledge.
--MarkusQ
The engineer who takes joy from building something people can use has a different view.
We need both.
*smile* That's the basis of my relationship with my wife (She's EE+MBA).
You haven't (Score:1)
If every inventor/programmer gave up because there was a similar patent, no one would ever program or invent anything.
No one knows if you are really infringing on a patent until the judge actually hands down a ruling. Patents aren't as clear cut as trademarks or copyrights. It's impossible to say something like "this code infringes" or "this code doesn't" until it actually goes to court. Same with even whether the patent is valid.
I think this is the reason behind Linus basically saying "fuck patents". Once you get the cease and desist, then make your decision, until then, you might as well not worry about it (unless you have large bank accounts, in which case, you should already have a relationship with a lawyer).
I am not a lawyer. Get a lawyer if you want legal advice, because this isn't it.
Re:You haven't (Score:1)
Prior Art (Score:2)
have thought about (Score:2)
-Sean
Markov Models, Negative Reward, Negative Examples (Score:5, Informative)
The google groups message says the patent covers explicity "markov model discriminator using negative examples". Markov decision problems are often those associated with a set of states and a policy which transitions between them. For spam filtering, I would guess there are three states: unknown, spam, non-spam, and the policy needs only determine if the transition should go between the unknown and and either the spam or non-spam state.
The optimal policy in an MDP is static, and thus it would say "the optimal policy is to mark an email spam". This sounds useless. A Partially Observable MDP (POMDP) may follow more with your plans since it follows percepts and probability distributions over the current set of beliefs.
As for training for an optimal policy for MDPs, one algorithm ("Value Iteration") makes use of a reward function. This reward function is explicitly allowed to be negative, and probably should be for some decisions or else the problem is trivial. And "positive" or "negative" examples is just a boolean simplification of multiple categories. Why not have "pr0n" "ads" "personal" "work" and a bunch of other categories?
In this case, positive and negative are meaningless, but all (both) are *always* neeeded to define the optimal policy.
In other words, I'm not sure I understand enough of what you are attempting to help find prior art, but from what I can tell "negative" examples are inherently part of defining the optimal policy in an MDP. For a reference, Russel & Norvig, Artificial Intelligence, A Modern Approach (1995) has a ton of information about MDPs and the training of them.
Re:Markov Models, Negative Reward, Negative Exampl (Score:3, Interesting)
I don't know enough about MDP to know if this is feasible work but it may move the scope of the solution far enough away from the patent to allow the submitter to continue his work.
Much prior art (Score:3, Informative)
Spreading acitivation models are mathematically similar to Markov chains, and ha ve also been used for similar purposes, trained and/or designed with both positi ve and negative exemplars.
Further, concept categorization and discovery research in cognitive science has used Markov chains for automated categorization, once again using positive and n egative examples.
If you're serious about this, I'd check the literature in this area, particularl y journals like Discoure Processes and similar. Also check the Proceedings of t he Cognitive Psychology conference.
All of this is published, peer-reviewed work well before 2000. Your best bet is to hit a decent university library and start searching.
Heck, my dissertation work didn't use negative examples, but the spreading activ ation models were originally Markov chains.
Markov chains and their use in AI, cognitive psychology, speech/text recognition , categorization, and text comprehension have been in use for decades. With the interdisciplinary approach common in the 80's and 90's, there were many efforts that adapted things like Markov chains and neural network learning algorithms, simulated annealing techniques, and so forth. It shouldn't be hard to dig some up. Worst case, find a cognitive psychology professor specializing in text proc essing and ask. UCSD has a strong showing, as UC Boulder, Manitoba, U Memphis, U Chicago, and many, many others.
Stop trying to work within the system.. (Score:1)
Problem solved, and you're (mostly) protected. FreeNet is a superb example of peaceful civil disobedience, and quite frankly, if we have the power of superior technology (which we do) we need to employ that to Just Say No to the corporations that are screwing us all over.
The only thing that's needed now is a system by which collaborators on a project can do so completely anonymously. FreeNet CVS, anyone?
Re:Stop trying to work within the system.. (Score:2)
Wildly publishing something doesn't put it into the public domain.
a better mousetrap? (Score:3, Informative)
Utility Patents - The most common type of patent, utility patents are issued to inventors of new devices and processes or improvements to existing devices or processes. Most utility patents are issued for inventions that improve existing devices. Inventors of the proverbial "better mousetrap," seek utility patents.
The existing patent you mention says "inappropriate web page material"
It may be possible the wording can be changed to be more specific - "unsolicited electronic mail messages" and "advertisements". I've bounced around the patent site a bit, and it seems there are a lot of patents that are given with prior art in existence, they just have to find it and say 'reference this patent' or something. If someone can get a patent for swinging on a swing, it's worth a shot if you've got the $$.