Showing posts with label maths. Show all posts
Showing posts with label maths. Show all posts

08 July 2010

Free Software Coder Bullied over *Algorithm*

As long-suffering readers of this blog will know, one of the many reasons I am against software patents is that software consists of algorithms, and algorithms are just maths, so a software patent is a patent on knowledge - the purest knowledge there is (a mathematician writes).

Sometimes defenders of software patents deny that software is just algorithms (don't ask me how, but some do). So I was particularly interested to read about this poor hacker being contacted over - you guessed it - algorithms, pure and simple:

Landmark Digital Services owns the patents that cover the algorithm used as the basis for your recently posted “Creating Shazam In Java”. While it is not Landmark’s intention to alienate those in the Open Source and Music Information Retrieval community, Landmark must request that you do not ship, deploy or post the code presented in your post. Landmark also requests that in the future you do not ship, deploy or post any portions or versions of this code in its current state or in any modified state.

As you can see, there is no way of disguising the fact that this claims to be a patent on an *algorithm* - that is, on maths, which is knowledge and therefore unpatentable.

But it gets worse. As the poor chap points out:

I've written some code (100% my own) and implemented my own methods for matching music. There are some key differences with the algorithm Shazam uses.

That is, he didn't copy the code, and it's not even the same approach.

But wait, there's more.

As he notes:

Why does Landmark Digital Services think they hold a patent for the concepts used in my code? Even if my code works pretty different from the Shazam code (from which the patents came).

What they describe in the patent is a system which:
1. Make a series of fingerprints of a media file and/or media sample
(such as audio, but could also be text, video, multimedia, etc)
2. Have a database/hashtable of fingerprints as lookup
3. Compare the set of hashtable hits using their moment in time it happened

This is very vague, basically the only innovative idea is matching the found fingerprints linearly in time. Because the first two steps describe how a hashtable works and creating a hash works. These concepts are not new nor innovative.

Moreover:

I've also had contact with other people who have implemented this kind of algorithms. Most notible is Dan Ellis. His implementation can be found here: http://labrosa.ee.columbia.edu/~dpwe/resources/matlab/fingerprint/

He hasn't been contacted (yet), but he isn't planning on taking his MatLab implementation down anyway and has agreed for me to place the link here. This raises another interesting question, why are they targetting me, somebody who hasn't even published the code yet, and not the already published implementation of Dan?!

And if they think its illegal to explain the algorithm, why aren't they going after this guy? http://laplacian.wordpress.com/2009/01/10/how-shazam-works/

This is where I got the idea to implement the algorithm and it is mentioned in my own first post about the Java Shazam.

So, moving to that last site, we find a detailed analysis of the algorithm - which is all pretty obvious. How did he do that?

So I was curious how it worked, and luckily there is a paper [.pdf] written by one of the developers explaining just that. Of course they leave out some of the details, but the basic idea is exactly what you would expect: it relies on fingerprinting music based on the spectrogram.

In other words, the description of the algorithm by the company's programmers shows that it "is exactly what you would expect".

At every level, then, this is an obvious, algorithmic, mathematical approach. And yet someone in Holland - a country that doesn't recognise software patents at all - finds himself under pressure in this manner for some code he wrote independently implementing that general, algorithmic mathematical idea.

Now explain to me how patents promote innovation, please...

Update: Re-reading the post I realise that things are even more ridiculous. Here's what the company wants:

we would like you to refrain from releasing the code at all and to remove the blogpost explaining the algorithm.

Now, you recall that the algorithm is the thing that the company claims to have a patent on. The original idea behind a patent was that in return for its grant, the inventor would *reveal* all the details of his or her invention so that others could use it once the patent had expired, as a quid pro quo. So if the company claims a patent on its invention, it must *by definition* reveal the algorithm.

Against that background, this demand to remove an explanation of the algorithm is simply absurd, and contradicts the very nature of a patent - it's like asking the USPTO not to reveal the patents it grants.

Follow me @glynmoody on Twitter or identi.ca.

23 December 2009

All Hail the Mighty Algorithm

As long-suffering readers of this blog will know, one of the reasons I regard software patents as dangerous is because software consists of algorithms, and algorithms are simply maths. So allowing software patents is essentially allowing patents on pure knowledge.

Against that background, this looks pretty significant:

Industries, particularly high tech, may be waiting for the U.S. Supreme Court decision, expected this coming spring, in the Bilski case to decide some fundamental questions of when you can patent business methods. But in the meantime, there’s a newly published decision from the Board of Patent Appeals and Interferences that establishes a new test to determine whether a machine or manufactured article that depends on a mathematical algorithm is patentable. The ruling is a big deal because it’s one of the few precedential decisions that the BPAI issues in a given year, and it will have a direct impact on patents involving computers and software.

For a claimed machine (or article of manufacture) involving a mathematical algorithm,

1. Is the claim limited to a tangible practical application, in which the mathematical algorithm is applied, that results in a real-world use (e.g., “not a mere field-of-use label having no significance”)?
2. Is the claim limited so as to not encompass substantially all practical applications of the mathematical algorithm either “in all fields” of use of the algorithm or even in “only one field?”

If the machine (or article of manufacture) claim fails either prong of the two-part inquiry, then the claim is not directed to patent eligible subject matter.

Now, the devil is in the details, and what impact this has will depend upon its interpretation. But what I find significant is that algorithms are foregrounded: the more people concentrate on this aspect, the harder it will be to justify software patents.

Follow me @glynmoody on Twitter or identi.ca.

15 October 2009

Open Sourcing America's Operating System

And how do you do that? By making all of the laws freely available - and, presumably, searchable and mashable:

Public.Resource.Org is very pleased to announce that we're going to be working with a distinguished group of colleagues from across the country to create a solid business plan, technical specs, and enabling legislation for the federal government to create Law.Gov. We envision Law.Gov as a distributed, open source, authenticated registry and repository of all primary legal materials in the United States.

This is great news, because Carl Malamud - the force behind this initiative - has been urging it for years: now it looks like it's beginning to take a more concrete form:

The process we're going through to create the case for Law.Gov is a series of workshops hosted by our co-conveners. At the end of the process, we're submitting a report to policy makers in Washington. The process will be an open one, so that in addition to the main report which I'll be authoring, anybody who wishes to submit their own materials may do so. There is no one answer as to how the raw materials of our democracy should be provided on the Internet, but we're hopeful we're going to be able to bring together a group from both the legal and the open source worlds to help crack this nut.

I particularly liked the following comment:

Law.Gov is a big challenge for the legal world, and some of the best thinkers in that world have joined us as co-conveners. But, this is also a challenge for the open source world. We'd like to submit such a convincing set of technical specs that there is no doubt in anybody's mind that it is possible to do this. There are some technical challenges and missing pieces as well, such as the pressing need for an open source redaction toolkit to sit on top of OCR packages such as Tesseract. There are challenges for librarians as well, such as compiling a full listing of all materials that should be in the repository.

What's interesting is that this recognises that open source is not just an inspiration, but a key part of the solution, because - like the open maths movement I wrote about below - it needs new kinds of tools, and free software is the best way to provide them.

Now, if only someone could do something similar in the UK....

03 April 2009

Why We Should Teach Maths with Open Source

Recently, I was writing about science and open source (of which more anon); here are some thoughts on why maths ought to be taught using free software:

I personally feel it is terrible to *train* students mainly to use closed source commercial mathematics software. This is analogous to teaching students some weird version of linear algebra or calculus where they have to pay a license fee each time they use the fundamental theorem of calculus or compute a determinant. Using closed software is also analogous to teaching those enthusiastic students who want to learn the proofs behind theorems that it is illegal to do so (just as it is literally illegal to learn *exactly* how Maple and Mathematica work!). From a purely practical perspective, getting access to commercial math software is very frustrating for many students. It should be clear that I am against teaching mathematics using closed source commercial software.

Follow me on Twitter @glynmoody

15 November 2008

Of Lawyers and Software Patents

Regular readers will know that I have a bee in my bonnet about the non-patentability of software, largely because of the fact that software is made up of algorithms, algorithms are maths, and maths is not patentable: QED. So, as you might expect, the following, from a patent attorney, makes me go a funny colour:

Software is not a mathematical equation, nor is it a mathematical language. How anyone who writes software or professes to understand software could argue to the contrary is beyond me. Do people who write software actually think they are sitting down and writing mathematical equations and stringing them together? It is absurd to have such a narrow view of software.

The good news is that I do not intend to rebut this (and the rest of the post) here, because the comments to it, and those on Groklaw discussing it, are so good, and so varied, that it would be superfluous. If you ever come across people who have doubts about the non-patentablility of software, just point them towards those comments.

08 December 2007

Sage Does the Maths of Free Software

One of the persistent myths about free software is that successes like Linux are one-offs, and that the open source methodology can't be applied easily to tackle complex software challenges. In the early days of free software, the relative paucity of end-user apps was trotted out as proof of this idea - The GIMP stood in splendid isolation back then.

Things have change, though; today, there is a wide range of high-quality open source apps, and the list keeps on growing. Here's there latest, and it's a biggie:

Until recently, a student solving a calculus problem, a physicist modeling a galaxy or a mathematician studying a complex equation had to use powerful computer programs that cost hundreds or thousands of dollars. But an open-source tool based at the University of Washington won first prize in the scientific software division of Les Trophées du Libre, an international competition for free software.

The tool, called Sage, faced initial skepticism from the mathematics and education communities.

"I've had a surprisingly large number of people tell me that something like Sage couldn't be done -- that it just wasn't possible," said William Stein, associate professor of mathematics and lead developer of the tool. "I'm hearing that less now."

Open-source software, which distributes programs and all their underlying code for free, is increasingly used in everyday applications. Firefox, Linux and Open Office are well-known examples.

But until recently, nobody had done the same for the everyday tools used in mathematics. Over the past three years, more than a hundred mathematicians from around the world have worked with Stein to build a user-friendly tool that combines powerful number-crunching with new features, such as collaborative online worksheets.

"A lot of people said: 'Wow, I've been waiting forever for something like this,'" Stein said. "People are excited about it."

Sage can take the place of commercial software commonly used in mathematics education, in large government laboratories and in math-intensive research. The program can do anything from mapping a 12-dimensional object to calculating rainfall patterns under global warming.

The benefits of using free software for maths extend far beyond the usual ones:

The frustrations weren't only financial. Commercial programs don't always reveal how the calculations are performed. This means that other mathematicians can't scrutinize the code to see how a computer-based calculation arrived at a result.

"Not being able to check the code of a computer-based calculation is like not publishing proofs for a mathematical theorem," Stein said. "It's ludicrous."

(Via A Blog Around the Clock.)

17 October 2007

Patently Wrong, Mathematically Proved

Well, after yesterday's post about a paper drawing fascinating parallels between today's patent trolls and yesteryear's patent sharks, here's another zinger from academia, one of whose authors has just won this year's Nobel-ish prize for Economics. And look what it says:

the software industry in the United States was subjected to a revealing natural experiment in the 1980’s. Through a sequence of court decisions, patent protection for computer programs was significantly strengthened. We will show that, far from unleashing a flurry of new innovative activity, these stronger property rights ushered in a period of stagnant, if not declining, R&D among those industries and firms that patented most.

We maintain, furthermore, that there was nothing paradoxical about this outcome. For industries like software or computers, there is actually good reason to believe that imitation promotes innovation and that strong patents (long patents of broad scope) inhibit it. Society might be well served if such industries had only limited intellectual property protection. Moreover, many firms might genuinely welcome competition and the prospect of being imitated.

What's interesting about this - aside from the fact that a respected economist is arguing against patents for industries like software, and using maths to prove it - is that the whole idea of welcoming competition so that everyone can build on the communal advances is incredibly close to the underlying dynamic of open source, which gets better much faster because it can always draw on the work of others.

So essentially the result of the paper is that industries like software work better (a) without patents and (b) when they operate according to the open source development model. Imagine. (Via Slashdot.)

10 August 2007

Of Maths, Shares and Horoscopes

I have been a mathematician since the age of eight. As such, I tend to look at the world through the optics of mathematics. For this reason, I have never understood why people believe that they can model financial markets: they're clearly far too complex/chaotic to be reduced to any equation, and trying to extrapolate with computers - no matter how powerful - is just doomed to failure.

And so it seems:

I hear many Risk Arb players at big shops are getting creamed. It seemed like you make money for 3 years, then give it all back in a couple weeks. Classic mode-mean trade: mode is positive, mean is zero.

In fact, what is most surprising - nay, shocking - is that this apparently unshakeable belief in the existence of some formula/method that will one day allow such markets to be tracked accurately enough to make dosh consistently is equivalent to a belief in horoscopes. After all, horoscopes are all about "deep" correlations - between the stars and your life. Maybe financial markets should try casting a few - they'd be just as likely to succeed as the current methods. (Via TechDirt.)

28 March 2007

Openness, Surveillance and Privacy

Previous posts have noted that there is an inherent tension between openness and privacy. That tension is even more acute in the case of surveillance, which goes beyond consensual openness. Despite this, there is relatively little public debate around these issues; instead, as has been remarked, the UK is effectively sleepwalking into a surveillance society.

Against this depresseing background, the new report from the Royal Academy of Engineering, entitled Dilemmas of Privacy and Surveillance Challenges of Technological Change, is particularly welcome.

This is not least because it offers a depth of knowledge about the technological issues involved that is rarely encountered (these are engineers, remember). But it is also notable for its even-handedness and sensible suggestions. For example:

In this scenario, disconnection technologies are widely used in a co-ordinated manner: personal data is routinely encrypted and managed in a secure fashion, so co-ordinated connectivity does not threaten it and even substantial processing resources are not a day-to-day threat. This leads to Little Sisters who, by themselves, watch over only a fragment of a person's identity, but when co-ordinated can reveal all.

It would be possible to devise a store loyalty card which incorporated a computer chip that could perform the same functions as an ID card, but without giving away the real name of its owner. Someone might choose a loyalty card in the name of their favourite celebrity, even with the celebrity's picture on the front. If they were to use that card to logon to Internet sites, the fact that they are not really the film star whose name they have used would be irrelevant for most applications, and the privacy of the consumer would be maintained. However, if they did something they should not, such as posting abusive messages in a chat room, law enforcement agencies might then ask Little Sister (ie, the company that runs the loyalty card scheme, in this case) who the person really is, and Little Sister will tell them. In this
scenario, government departments are just more Little Sisters, sharing parts of the picture without immediate access to the whole.

This approach exploits both mathematics and economics. If it is technically possible to find out who has done what - for example when a crime has been committed - but cryptography makes it economically prohibitive to monitor people continuously on a large scale, then a reasonable privacy settlement can be achieved.

This approach suggests a interesting way of balancing the opposing requirements for privacy and accountability.

Recommended reading. (Via the Open Rights Group.)