The dream search engine would search by topic, by the detailed content of the items searched, ideally finding the desired information immediately. Actual understanding of text remains a unfulfilled promise of artificial intelligence. Statistical language processing can achieve a degree of searching by topic. This article introduces the basic concepts and mathematics of statistical language processing and its applications to search. It gives a brief introduction and overview of more advanced techniques in statistical language processing as applied to search. It also includes sample Ruby code illustrating some simple statistical language processing methods.

Read the rest of Faster, Better, Cheaper Search Engines on Scribd, where you’ll be able to download it in several formats including PDF, or click Fullscreen in the embedded document below.

Source code: trigram.zip

PDF: Faster-Better-Cheaper-Search-Engines.pdf

Bookmark and share:

1. Some of our readers are likely familiar with your work, but could you tell us more about yourself and your mathematical background?

I majored in mathematics as an undergraduate at Yale, from which I graduated in 1976. I think I even won a couple of math prizes, but I have to confess that I wasn’t the top mathematician in my class. That distinction would surely have gone to Jonathan Rogawski, who last I knew was a professor of mathematics at UCLA. (Notice that I just created the impression that I was the second-best mathematician in my class. I don’t know whether that’s true, but I’ll take it.)

Anyway, I went on to get a Ph.D. in mathematics at M.I.T. and have remained in the Boston area ever since. I went into the investment business in the early 1980s, based on the assumption that quantitative expertise would be a good match. But the truth is that I got progressively more qualitative as time went by, going from securities analyst to investment writer. I don’t know whether that transition made complete sense, but it ultimately gave me the opportunity to write some books – first about investments and then about numbers, including several volumes of puzzle books.

2. What inspired you to write Number Freak?

I was asked by a publisher to come up with a concept that would do for mathematics what a slightly different concept did for the natural sciences. The idea I came up with was more of a coffee-table book than the sized-down version I now have in my hands, but that effort was considered too expensive. I subsequently cast a wider net for the project, and was fortunate enough to attract publishers in the U.S., the U.K., and Australia.

3. The book is chock-full of interesting facts about the first 200 natural numbers. What did you learn in the process of writing this book that you didn’t know before?

Well, I guess the pat answer is that I learned how little I actually knew. Some of the work on planar tilings was new to me, even though it probably shouldn’t have been – for example, the Archimedean and Laves tilings I discuss in #11 are quite beautiful but I hadn’t been aware of their categorization and duality. And I wasn’t familiar with the work of mathematicians such as Erich Friedman of Stetson University, somebody who surely could have pulled off a book like this: I was only too happy, for example, to include “Friedman numbers” such as 127.

In self-defense, I wasn’t a complete neophyte. One big advantage I had in writing the book – apart from doing it in the Internet age, which gave me an abundance of material – was that I have a good memory for mathematical and pop culture trivia. For example, I enjoyed reaching back and remembering that the ultra-high security “D” block at Alcatraz prison had precisely 42 individual cells, something that meshed quite nicely with the picture of the “magic cube” I displayed elsewhere in the discussion of #42.

4. Having read this book I feel that it’s accessible to virtually anyone. Who do you feel is the ideal target audience for the book?

Boy is that a good question. My answer is that it’s for absolutely anyone, but if that’s too mealy-mouthed a reply, I guess I would say that I’d be especially pleased if parents bought Number Freak to (successfully!) introduce their kids to the world of numbers in a way that maybe, just maybe, is friendlier than what those kids were getting elsewhere.

5. Was there anything that you wish you could have included in the book but didn’t?

Another good question, and I’m afraid a painful one. The book was originally slated to go from 1 to 300 — as in a perfect game in bowling, among other things — but the editorial powers-that-be eventually whittled that down to 200. Too bad, as my discussion of the infamous 256th level of Pac-Man was worth the price of admission. (Say, that’s a topic I didn’t know about when I started the book!) I also lost some precious photos, charts and diagrams along the way. And you can imagine how I felt when a friend berated me for not mentioning “77 Sunset Strip,” when of course my original manuscript mentioned the show – and I have a photograph of Efrem Zimbalist, Jr. to prove it! (Those of my vintage – I’m 54 – will remember the show’s catchy theme song, but not many are aware that 77 was a particular good choice for the street address because it is the smallest integer whose English pronunciation requires five syllables.)
Other than that, I deliberately went easy on the cult surrounding the number 23, for example, and left a bunch of numerology and religious interpretations for somebody else to ponder. That’s another book all by itself.

6. What’s the answer to life, the universe and everything?

Why it’s 42, of course. You know, I had already answered question #3 above before I saw this one!

7. What’s your favorite number and why?

When I started the book, 17 had the edge. First of all, “At 17” by Janis Ian is probably my favorite song of all time. It came out in 1975, which was my favorite music year of all time. (Perhaps I should have written it in 1975.) But 17 is famous in mathematics for Carl Friedrich Gauss’s famous straightedge-and-compass construction of a regular 17-gon, for the 17 “wallpaper” symmetries of the plane, and for the fact that if you connect 17 suitably spaced dots with a segment of red, blue, or green, you will automatically create a “monochromatic” triangle whose three vertices are among the original 17 dots. And nobody has yet created a solvable Sudoku puzzle with fewer than 17 original entries. How about that?

But by the time I finished Number Freak, my favorite number had become 36. What happened is that while doing research for the book I came across a conjecture from the 18th century called the 36 Officer Problem. I had never heard of it before (yet another example!), perhaps because the problem was resolved in the early 20th century and then ceased to be of interest. But there was a three-dimensional wrinkle to the problem that hadn’t been explored, and I used that wrinkle to design a puzzle with a gray base and 36 towers of various colors. I went to Toy Fair and showed the puzzle to ThinkFun, a great game and puzzle company out of Alexandria, Virginia. And guess what? They made me a deal for the puzzle and after a year tinkering with the basic model, they launched it as “36 Cube” in the fall of 2008—many months before Number Freak came out! I was thrilled that the lessons of the book came to life in such a tangible way, so I’d be lying if I didn’t admit that 36 holds a very special place in my heart.

Thank you very much, Derrick, for your insightful answers. And to our readers, if you haven’t already done so, check out his book.

Bookmark and share:

The gambler’s fallacy, also known as the Monte Carlo fallacy or the fallacy of the maturity of chances, is the belief that if deviations from expected behavior are observed in repeated independent trials of some random process then these deviations are likely to be evened out by opposite deviations in the future.

This definition may seem a bit abstract, so let’s clarify it through a practical example. What’s the probability of flipping a fair coin 10 times in a row and obtaining heads consecutively each time? The answer is:

.

This would be very unlikely. How unlikely? One in 1,024 to be exact. So if we’ve just observed the coin appear as heads 9 times in a row, what are the odds that the same coin will land on heads on the 10th toss?

Many people would argue that the chance of this happening is less than one in a thousand, as we just calculated. However, that answer is blatantly wrong. The probability that the 10th fair coin toss is going to come up as heads is still 0.5, because each trial (toss) is statistically independent from those that preceded it. Tossing 9 heads in a row is very unlikely, however once it has happened, it doesn’t influence the outcome of the 10th toss in any way.

People who fall for this fallacy, do so because of a fundamental misunderstanding of how probability works. They combine the probability of past events (irrelevant for independent trials), with that of future events. With the example above, some people would also erroneously conclude that “tails is long due to come up” and as such would think that it’s more likely to occur.

This informal fallacy has contributed to the ruin of many gamblers over the years. A tragic example of what happens when you uphold this way of looking at odds occurs with many who play the game of “Lotto” in Italy, a very popular lottery game played amongst the general population.

The idea behind this game is very simple. Five distinct numbers between 1 and 90 are randomly selected in 10 different Italian cities, three times a week. Gamblers can place several types of bets, but the one we’re interested in, for the sake of this article, is called the “estratto semplice” (simple draw). This type of game requires gamblers to correctly predict that a specific number will be drawn in a particular city.

The probability of placing a winning bet is 1 in 18 (i.e., 5/90), while the payout is 11.232 times the amount that you put down (so if you bet 1 Euro and won, you’d walk away with 11.23 Euros before taxes). The odds are clearly stacked in favor of the house, of course. Incidentally, Lotto is run by the state and as is also known as “a tax on the stupid” for rather obvious reasons.

There are many “systems” and theories used by a large pool of gamblers who want to “beat the system”. More often then not such systems are based on some flawed understanding of how probability really works. A very popular theory is that of the “numeri ritardatari” (”late numbers”, as we will refer to them throughout this article). The basic principle behind late numbers is this: since it’s extremely unlikely that a given number will fail to appear at least once out of 150, 180 or 200 draws in a row, in a given city, you can identify what numbers are “due” to appear and thus bet on them. For example, if a number hasn’t been drawn in the past 140 trials, the number of bets on it will start to grow very quickly.

Of course, despite the fact that a number hasn’t come up in a given city 140 times in a row, its probability of occurring on the next draw is still just 1 in 18. So betting any of the other 89 numbers would yield the same probability of winning.

The application of this fallacy becomes extremely dangerous when coupled with Martingale betting systems, which are often adopted by “late number theorists”. The theory they use is very simple. Since they assume these late numbers are “due” very soon, they think they are going to be able to afford to put down double their previous wager on every bet until the number eventually appears. So when it does happen, the last sum they bet is multiplied 11 times (for the payout) and they will recoup all the money they’ve spent up until then, and end up netting a large additional payout, which is the (last wager x 9.232 + 1) Euros.

Martingale betting systems are guaranteed to work provided that the gambler has an infinite amount of capital and no limits are imposed on the maximum bet that’s allowed to be placed. In the real world, both of these requirements cannot be realistically met. The amount bet grows exponentially, so the Martingale system ends up being a surefire way to bankrupt those who employs it.

In the case of the Italian Lotto, both the fallacy that late numbers are “due” and the choice of betting systems (Martingale) are responsible for the ruin of many. The gambler’s fallacy plays an important role in this case because most people realize that they can’t sustain a Martingale type system for 200 consecutive draws. It’s their faith in the idea that late numbers are very likely to pop up soon, that tempts them into toying with this risky system.

If we assume these people are convinced that a very late number (say, one that hadn’t been drawn in the past 180 lottery draws) will be selected at some point during the next 5 weeks or so (15 trials), and that they’re starting with a bet of one Euro, we can see that the maximum amount they’d need to invest (according to their theory) would be 32,768 Euros, with a max bet of 16,384 Euros by the 15th draw. This is a sizable sum of money, but something that some people would still be able to put down, especially because they knew they payout would be 184,025.088 Euros (before taxes). A tempting prize indeed.

But what are the real odds that the number in question, the one that’s been eluding the gamblers, will not end up occurring at least once in the next 15 draws?

So there is a 42.43% risk that the punter will lose their 32,768 Euros, because they won’t have sufficient funds to double their wager at the next turn (assuming 32,768 Euros was the maximum amount they can afford to bet).

Bear in mind that with an exponential growth of the bet, a huge amount of capital will only afford our late number gamblers a few extra draws, thereby only slightly increasing their probability of making a profit. (With a payout of 11.232 times the wager, they could afford a smaller increase in the amount of money they put down draw by draw, but the overall principle remains the same.)

What has an adoption of this faulty theory led to in Italy? What kind of impact has it really had on those who adhere to it? The honest truth is that it’s gone so far as to contribute directly to things like suicides, people swindling their friends and employers, divorces, people betting their life savings and their homes, families being destroyed, and so on. Do such dire consequences occur to everyone who plays this game? No, of course not, but the fact that it’s happened to some people, and that these flawed theories are still employed today, is indicative of the misunderstanding about probability (and the risks of gambling) that occurs in the general population.

One could – and should – argue that such peoples’ demise is due to their gambling habits and to good old fashioned greed, yet I can’t help but feel that a solid understanding of probability theory would go a tremendous way in helping to cut down on the number of people who fall prey to these types of widespread theories.

An increased awareness of probability and statistics can only improve society and its ability to assess situations and make rational decisions. How do we begin to remedy this situation, not only in Italy, but around the world? We can start by devoting far more time in grade, middle and high school math classes, in order to teach students about this important subject and the implications that it can have on their everyday lives, understanding of society, and ability to make wise financial decisions.

Bookmark and share:

The author of the site, describes the project as follows:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

When you first register, you will be presented with 252 problems available to be solved. This number changes frequently, however, as new problems are routinely created and added to the list. The solutions to some problems veer towards the obvious, while others require advanced mathematics to tackle. Likewise, a few can be solved with paper and pencil and a good dose of insight. Most however, will require the aid of a computer program written in the language of your choice.

A sample problem (187)

Each program you execute should output your result within a minute. That’s part of the challenge, even though there is no way for the site to enforce this rule.

When you think you’ve found the correct result for a given problem, you can fill in the result field for the problem, and see if you got it right. If you have, your answer will be added to the list of problems you solved and will count towards your overall score, while bumping up your position on the participant scoreboards. There are several scoreboards, depending on what level you are at, which in turn is determined by the number of problems you have solved so far.

More importantly, solving a problem will gain you access to the respective forum (for that problem), where you’ll be able to see solutions and discussions from other participants, who may have used different languages and solution strategies.

Project Euler is appealing for a variety of reasons. In particular:

• It allows you to explore areas of math that you might not be familiar with. Solving certain problems may require you do a fair amount of research and in turn help you to learn more about certain branches of mathematics;
• If you are a math major who is trying to hone their programming skills, you’ll find Project Euler to be challenging, fun, and an excellent opportunity for improvement. Having to implement several small programs and being able to compare your style with those of other people in the forum, will definitely end up improving your knowledge of many algorithms and your skills as a programmer;
• The site’s one minute rule has an important consequence. The computational complexity of your programs really ends up mattering. While some simple problems can in fact be brute forced, the majority of them require you to write faster algorithms and take advantage of mathematical insight so as to improve the performance of your program. For certain problems a naive approach would take more than a lifetime on current PCs;
• Finally, if you are a programmer who’s scoping out a new programming language, be it Python, Ruby, Scala, Haskell or Erlang, you’ll find a great ally in Project Euler. Having to write hundreds of programs in a given language, will naturally increase your familiarity with that language. And again, comparing your newcomer coding style with those of more experience participants, will no doubt contribute to your advancement within the given language you’re focusing on.

Project Euler truly deserves five stars. I recommend it highly to anyone who is unafraid of writing a few lines of code in order to solve interesting math problems.

Bookmark and share:

The other day I noticed that a lot of bandwidth consumption was due to external sites who had republished some of our content without permission. It turns out that many of these spammers were “hotlinking”. In other words they didn’t copy the images on their own servers, they simply linked to the original on my servers, to be displayed on their sites. The end result is that they consumed my bandwidth, in an attempt to make money off my content.

It is possible to configure your server to replace each image if the URL serving them is not in your approved list. So I did just that. I authorized *.math-blog.com, a couple of my other sites, including my programming blog, and search engines. For those of you who are into computer programming: I simply wrote some rewrite rules and conditions in my .htaccess file for the Apache web server.

What went wrong? My feeds are served by FeedBurner, a service that Google acquired some time ago. I regretfully forgot to add Google’s service to the list of accepted domains.

I’ve remedied this and everything should be back to normal now. Please accept my apologies for the inconvenience.

Bookmark and share:

Mathematicians: An Outer View of the Inner World is a hardcover book of photos that centers around 92 well-established mathematicians. It is a work of art that presents, through each of the glossy images (which are printed on excellent quality paper), an autobiographical note on the left, and a large, black and white photograph of a mathematician on the right hand side.

The beautiful portraits, along with the short essays, help the reader to establish a brief emotional connection with each mathematician, as you become privy to the “outer view of their inner world”. Some of the featured mathematicians are young, many are older, some are well-known worldwide, others are relatively unknown. Their stories are intense and each fascinating in its own right. Many of these brilliant minds lived through WW2, and found that doing so had a strong impact on their lives and career choices.

Each mathematician interpreted the assignment of writing their micro-bio in a different way. Some tell you about their childhood and how they came to discover they joy of mathematics, others about what their biggest accomplishments to date have been, and a few talk about the open challenges they see in their field. The common thread amongst this diverse group is the wondrous search for knowledge, beauty and truth that transpires from their words. As Mariana Cook (the book’s photographer) mentions in the foreword, though she has photographed scientists and many other unrelated groups of people, she’s never experienced so many people referring so often to beauty and truth. Indeed math is beauty, elegance and truth!

Stunning photography and intimate essays make for a great work of art. Mathematicians is a book that can be enjoyed by anyone, from people who are passionate about mathematics to those who have been adverse to the subject all their lives. The latter group will probably look at the subject of math in a new light after experiencing this book.

The affordable price and large format of this book make it a coffee table piece that every geek should have. The hardest part for most math aficionados will be treating it like a coffee table book though, and not reading it cover to cover right away, as I did. This title left me with a strange sense of harmony and peace, and a renewed awareness about the importance of mathematics, as well as a desire to join their efforts in furthering the discipline. Well above what I was expecting from a photography-based book.

Have you read a math book that you’d like to review for Math-Blog.com? Let us know.

Bookmark and share:

I bought some of these books, others were sent to me as evaluation copies for my consideration. I plan to devote detailed reviews to my very favorites in the coming months. Here, I’m simply going to list all my math-related reading up to mid-2009, for those of you who’d like to check it out.

Sacred Mathematics: Japanese Temple Geometry

Mathematicians: An Outer View of the Inner World

Is God a Mathematician?

Euler’s Gem: The Polyhedron Formula and the Birth of Topology

The Great Equations: Breakthroughs in Science from Pythagoras to Heisenberg

The Golden Ratio: The Story of PHI, the World’s Most Astonishing Number

A Mathematical Nature Walk

The Mathematical Mechanic: Using Physical Reasoning to Solve Problems

Divine Proportions: Rational Trigonometry to Universal Geometry

Modeling with Data: Tools and Techniques for Scientific Computing

Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Performance Modeling

Prime-Detecting Sieves. (LMS-33) (London Mathematical Society Monographs)

Bookmark and share:

The first narrates the story of Andrew Wiles, who proved Fermat’s last theorem in 1994. It’s a relatively short documentary, coming in at about 45 minutes, but I find it to be both inspiring and a nice aid to better understanding Andrew “as a person”, before thinking of him as a superb mathematician. This documentary is based on Simon Singh’s excellent book
Fermat’s Enigma: The Epic Quest to Solve the World’s Greatest Mathematical Problem.

The second documentary focuses on the obsessive quest for knowledge shared by Georg Cantor, Ludwig Boltzmann, Kurt Gödel and Alan Turing. The basic idea behind “Dangerous Knowledge” is that the genius of these outstanding mathematicians and their obsession ultimately lead to their madness and tragic deaths. In truth, I feel that the underlying thread that tries to tie the four stories together is forced.

For example, Alan Turing was persecuted for his homosexuality, and it is believed that this had a significant impact on his eventual suicide. The filmmakers are trying to lead the viewers to come to the certain conclusion that the quest for understanding infinity is what led these mathematicians to insanity, which is entirely unsupported. Nevertheless, if you’re aware of the agenda behind this film, you’ll get a beautiful 1h 29m documentary that is absolutely worth watching. It poses interesting questions about the nature of knowledge, our understanding of nature, and other puzzling dilemmas that encompass mathematics, physics and philosophy.

What other mathematical documentaries are you fond of? If various titles are suggested, we could definitely start a nice must-watch math documentary list here on Math-Blog.com.

Bookmark and share:

The most interesting feature of this initiative is the open letter that prefixes each paper, in which the author illustrates what they believe is the reason behind their work’s rejection and asserts their paper’s case. Scientific papers, like notorious novels, do sometime get undeservedly rejected before their true value is acknowledged. The hard part is distinguishing the hidden gems.

Contrary to what one may have expected though, this edition clearly debunks the notion that Rejecta Mathematica would be a breeding ground for crackpots. The six papers included in this first edition all appear to be interesting and well researched.

Is it the revenge of the rejected? Perhaps, but this unusual publication will still help to enrich our beloved discipline in its own way.

Bookmark and share:

Complex algorithms are typically implemented as either computer software or in custom VLSI chips (e.g. Application Specific Integrated Circuits or ASICs). Research and development of complex algorithms is a specialized area and differs in a number of ways from most software and hardware development. Remarkably, many computer software business and engineering professionals often underestimate or do not understand the difficulties and scope of complex algorithm projects.

Complex algorithms are already in widespread use in commercial applications. Prominent examples include the video compression algorithms that enable BluRay, DVD Video, YouTube, and many other modern digital video systems. The US DVD Video market is around $25 billion per year (2007). Although limited, speech recognition such as now frequently encountered in telephone help and customer service systems is another example. Other examples include encryption, seismic modeling used in oil and gas exploration, sophisticated financial models, traffic models, and many others.

Complex algorithms may solve a range of major problems confronting the human race including major diseases such as cancer, the need for more and cheaper energy, and so forth. Molecular modeling may enable the design of drugs or systems of drugs that can selectively target and destroy cancer cells based on the identifying characteristics of cancer cells such as chromosomal anomalies, something currently impossible. Electromagnetic modeling software may enable the successful design and fabrication of working commercial fusion power sources. These are potential trillion-dollar markets. The global annual energy market is over $1 Trillion.

Note: Since I am a software developer, I will focus primarily on complex algorithms developed and implemented as computer software. Many of my comments apply equally well to hardware implementation. Where I have some knowledge and experience, I will make some comments on specific hardware issues.

Complex Algorithms Are Difficult

Complex algorithms are usually quite difficult to develop and often take longer than experience with other software projects would indicate. Although there are exceptions, complex algorithm projects usually take between four (4) months and several years. True research projects in which new mathematical or logical methods are developed are extremely unpredictable and typically take years. Most major scientific discoveries and inventions have taken at least five (5) years.

Complex algorithms frequently involve a tight coupling between different parts of the algorithm. All parts must work together within tight tolerances for the entire algorithm to work. This is similar to mechanical systems such as automobile engines or mechanical clocks. Indeed, implementations of complex algorithms are often referred to as “engines”, partly for this reason. Complex algorithms are often very unforgiving. Even very small errors, getting a single bit wrong, results in the implementation failing. This occurs frequently with encryption where usually every bit must be correct and video compression where even small errors often result in unacceptable “artifacts” in the decoded video. In practical terms, this means that the amount of time spent per line of working code is often significantly larger for complex algorithm projects than other software projects such as web sites, user interfaces, database reporting systems, and so forth.

Most commercial software projects involve at most mathematics taught in early high school (9th, 10th grade) in the US. Even advanced high school mathematics such as the solution to quadratic equations is uncommon outside of computer graphics. Complex algorithms in widespread use today typically involve mathematics that is taught in the first and second year of college at a good college or university in the US. A few complex algorithms involve more advanced mathematics. For example, the Global Positioning System (GPS) uses General Relativity, advanced undergraduate or graduate level mathematics, to determine the location and time correctly. In the future, more advanced mathematics may be needed for pattern recognition and other advanced tasks. Most commercial software developers do not have much experience with mathematical software at the level found in complex algorithms. Research and development of complex algorithms often requires a range of mathematical and logical skills that are not common.

Return on Investment

The return on investment for a successful complex algorithm project can be very high. Complex algorithm research and development is typically done by small teams or individuals. Small teams are the most common. Even a multi-year project, for example five years, with a ten person team (a large team) has a total cost of about $7.5 million (using a total cost per full time employee of $150K/year). A home run can solve a billion dollar or larger problem, bringing in hundreds of millions or even billions of dollars.

• Return = $100 M / $7.5 M = 13.3 (small home run)
• Return = $1 B / $7.5 M = 133 (big home run)
• Return = $1 T / $7.5 M = 133,000 (off the charts)

The greatest opportunities and the greatest risks lie in areas that require development of new mathematical or logical methods; that is true research. New complex algorithms can be converted very rapidly to commercial software products, even in a matter of months, as happened with new video compression algorithms in 2003.

Research and Development

The commercial software industry focuses overwhelmingly on “technically feasible” projects. Many venture capital firms explicitly claim to only invest in proven, technically feasible projects. Similar thinking pervades the commercial software industry. Where complex algorithms are concerned, technically feasible means proven algorithms for which working prototypes exist somewhere. The working prototypes are usually computer programs, often slow, that successfully implement the algorithm. These are frequently prototypes in the C or C++ programming languages, although Java is becoming more common (see the discussion of software engineering below). Thus, most commercial projects in the complex algorithms arena involve such tasks as porting algorithms to a different platform (for example, Unix to Windows), optimizing the algorithms for a new platform, integrating the algorithms into an application program such as a media player, converting a prototype into a production system, and so forth. Most research scientists would call these activities “Development” and not “Research” or “Research and Development”.

The commercial software industry follows a widely accepted rule to avoid projects that are not technically feasible, meaning true research projects. Nonetheless, the rhetoric of the commercial software industry, both aimed at unsophisticated investors and customers is the opposite. Terms like research, science, and research and development are used routinely to describe commercial software development activities. Many companies make statements that either explicitly claim or imply that the company has a large R&D group engaged in true research. Note that rhetoric aimed at sophisticated investors such as venture capitalists is often the opposite, which can be quite confusing.

Historically, the commercial software industry has relied heavily on government sponsored research programs such as the Defense Advanced Research Projects Agency (DARPA) and the National Aeronautics and Space Administration (NASA) for the true research in software. Many types of software and specific software products can be traced back to government sponsored research programs. Some well known examples include the Internet, originally a DARPA project, and the World Wide Web, which grew out of research projects at CERN and NCSA. Many other examples exist. Essentially all speech recognition software is derived from research sponsored by DARPA, especially projects at Carnegie-Mellon University. Nonetheless, industry rhetoric often invokes the image of private inventors in garages, the Wright brothers, and similar images of “free enterprise” and individual initiative. Typically, the putative inventor such as Tim Berners-Lee or Marc Andreessen is emphasized and the relevant government research program ignored or downplayed. Often there is little or no progress in commercial software if the relevant government research program is unable to make progress. This is most evident in pattern recognition and artificial intelligence, where progress has been very slow or non-existent.

Many government research programs are afflicted by a single “right way” that is pursued to the exclusion of all others. If this right way is good, then there is steady progress in the associated commercial software field. DARPA in particular relies upon periodic contests pitting different methods against one another. This has repeatedly resulted in a single approach that showed early promise taking over a field. A contest of this type during the 1970’s resulted in the so-called Hidden Markov Model (HMM) based speech recognition approach replacing essentially all speech recognition research on a global scale. Essentially all major speech recognition research groups, many directly funded by DARPA, pursue some variant of the HMM algorithm. Yet the performance of the HMM algorithm continues to be quite limited after 30+ years.

Most major commercial opportunities in complex algorithms require a company to fund and undertake genuine research, a difficult task that few companies understand. Artificial intelligence, speech recognition, cures for major diseases such as cancer or working fusion energy sources require substantial research.

Evaluating Technical Feasibility

In complex algorithms, technical feasibility generally means that a working prototype of the complex algorithm exists. In practice, working prototypes are often implemented in computer programming languages such as ANSI C, C++, or Java. Special algorithm research and development tools such as Matlab and Mathematica are also used. The working prototype may be slow, inefficient, or have other limitations, but it is or should be a proof of concept.

Seemingly, it should be easy to evaluate technical feasibility. Simply acquire and test the working prototype. Nonetheless, there is a long history of ostensibly sophisticated organizations and investors investing in complex algorithm projects that are not technically feasible, often apparently in the belief that the relevant problem had been solved. This has happened repeatedly with pattern recognition and artificial intelligence. It has also happened with various data compression algorithms.

For some reason, some organizations and investors do not even acquire and test the working prototypes. This is absolutely essential. It is often said that one should invest in people, not in ideas. Venture capitalists and other sophisticated investors often quote this platitude. However, the history of complex algorithms is filled with companies and projects with officers, directors, managers, chief scientists, and so forth with gold-plated resumes, impressive credentials, top degrees from top universities, and so forth that have flopped. The bottom line in complex algorithms is that the ideas count. If the complex algorithm doesn’t work, it doesn’t work. The company or project will fail for purely technical reasons. This is the lesson, for example, of the Pen Computing fad of the early 1990’s, GO, and Lernout and Hauspie (see below). This is also one of the lessons of the complex financial models involved in the current global financial crisis (2008). Due diligence requires a thorough, well-considered independent test and evaluation of the working prototype.

It can be difficult to evaluate technology demonstrations of complex algorithms. Often there are subtle and not so subtle ways to manipulate a technology demonstration. For example, in the early days (1995) of MPEG digital video on personal computers, MPEG software video player companies gave technology demonstrations on high-end personal computers with high-end video acceleration graphics cards. In pattern recognition, many present-day (2008) pattern recognition algorithms can achieve recognition rates in the range of 80-95% at least under certain controlled conditions. This seems high. In schools, 80-95% is usually a B or an A, a good grade. However, practical real-world pattern recognition often requires a recognition rate of 98 or 99% or even better under field conditions. In both examples, the technology demonstration can be misleading without demonstrably false statements.

Actual fraud can be difficult to detect and difficult to prove. It is important to conduct tests and evaluations of working prototypes independent of the purveyor or other interested parties who may have a reason to perpetrate a fraud. Complex algorithms can involve the potential for very large returns on investment—as noted above. Consequently, there is considerable motivation for fraud in some cases.

How Does Research Differ from Development?

Commercial software development is usually unpredictable. Software projects frequently involve unexpected problems and usually take substantially longer than planned. Nonetheless, technically feasible commercial software development projects are more predictable than true research projects. Often if one takes a conservative cost and schedule estimate and multiplies this by a factor of three to four, one gets the actual cost and schedule of the project. A common joke with a great deal of truth is: to get the real schedule multiply the official schedule by PI (3.14) for running around in a circle. Because the project is technically feasible it can certainly be completed. Massive cost and schedule overruns (such as factors of ten) can usually be explained by incompetence or severe political problems. True research is extremely unpredictable. Many true research projects simply fail. The researchers are unable to find the solution. For example, to date (2008), essentially all attempts to decipher human speech have failed in close to a century of attempts. Substantial research efforts at Bell Labs, MIT, and other institutions have failed to determine why certain sound spectra correspond to the different sounds in English and other languages. Even in successful research, estimates are often way off. For example, the mathematician Johannes Kepler made a bet in 1600 that he could determine the orbit of Mars in eight (8) days. His discovery of the elliptical orbit of Mars and other planets, one of the most important and difficult discoveries in scientific history, took five frustrating years in which every attempt to solve the problem failed until he found the answer in just a few days in 1605. This process in which long periods of little or no progress are punctuated by sudden unpredictable leaps forward is typical of true research, especially major scientific discoveries or technological inventions.

True research, especially major scientific discoveries or inventions, usually involves a very large amount of trial and error. Often, after many failures, there is a leap or leaps in which a new approach or concept is tried which unexpectedly solves the problem. Most major scientific discoveries or inventions took somewhere between five (5) and twenty (20) years. This is significantly longer than the time frame of typical commercial software industry and venture capital funded projects. In many cases, one is talking about five to twenty years of failure followed by a “breakthrough”, as in Kepler’s case.

In my experience, people involved in commercial software development are often unaware that they have little or no experience with true research. The misleading rhetoric of the computer software industry often leads people involved in commercial software development to think that they are engaged in the sort of true research conjured up by iconic names like Einstein or the Wright brothers. This undoubtedly leads to many bad decisions and frustrating experiences.

The Importance of Rapid Prototyping

History records many remarkable instances when an individual or small team succeeded in making a major scientific discovery or invention on a very small budget, sometimes beating far better funded competitors. Major scientific discoveries or inventions almost always involve a large amount of trial and error. Discoverers or inventors who managed to make a major discovery or invention on a shoe-string budget usually found a very fast, inexpensive way to perform the many trials and errors required to make a major discovery or invention.

For example, James Watt is remembered for inventing the separate condenser steam engine, a major conceptual leap that turned the steam engine from a niche device used in coal mining to a major driver of the industrial revolution. The Newcomen steam engines of Watt’s time were huge expensive house-sized engines. Watt however built and experimented with tiny scale models built from inexpensive wood, copper, and other materials. This enabled him to perform hundreds of trials and errors that led to the breakthrough concept of the separate condenser that radically improved the Newcomen steam engine.

Octave Chanute and the Wright brothers, his proteges, conducted research and development of gliders constructed of cheap wood and canvas. The gliders were flown at low altitude on soft sand beaches, first in Gary, Indiana near Chicago where Chanute lived, and later at Kitty Hawk in North Carolina. This meant that the inevitable damage from crashes was limited and easily repaired. The pilots did not die from the crashes as was common with other early would-be aviators. By delaying work on the expensive engines until last (they planned to buy a commercial off-the-shelf engine), they avoided the enormous cost involved in repairing or replacing an engine after each crash. This enabled Chanute and the Wright brothers to eventually succeed where better funded efforts such as Hiram Maxim and Samuel Langley failed.

Progress in aviation and rocketry today is quite slow, almost flat-lined since 1970, in part because the cost of a single trial, especially a new high performance engine, has become extremely high, easily in the millions if not billions of dollars per prototype engine and vehicle. In rocketry and other high performance engines, the prototype engine and vehicle are often destroyed during each trial. Internet entrepreneur Elon Musk of PayPal fame encountered this problem with his SpaceX startup as have many other Internet and software entrepreneurs attracted by the dream of space travel.

In algorithm research and development today, rapid prototyping tools such as Matlab and Mathematica (see below) speed up and reduce the cost of the many trials and errors required in true research. This is very important because the number of trials and errors is usually very large.

The Importance of Conceptual Analysis

Most major scientific discoveries and inventions usually involve a large amount of conceptual analysis expressed in words and pictures (often hundreds of thousands of words). It is common to find lengthy verbal discussions of the issues combined with rough sketches or drawings of concepts. For example, Octave Chanute wrote an entire book Progress in Flying Machines containing his lengthy verbal analysis of the problem of flight. This book outlines his successful research plan to develop working powered flight. It contains several rough drawings, as is common in major breakthroughs, and only a few brief calculations. The mathematician Johannes Kepler devoted much of his book, now known as New Astronomy, to a lengthy conceptual analysis of the problem of planetary orbits which was critical to his resolution of the problem.

At some point, these verbal analyses are refined into precise technical drawings in the case of mechanical inventions and specific mathematical expressions in the case of mathematical discoveries like Kepler’s. However, the verbal and visual analysis appears to be critical in many discoveries and inventions and usually comes first. It is likely that this sort of verbal and visual analysis will be essential to solve many problems such as artificial intelligence and pattern recognition.

Historically, this conceptual analysis was considered a part of philosophy. Much of the classical training in Greek philosophy and mathematics probably provided important training in this conceptual analysis. The discovery of new mathematical expressions of practical use strictly by the symbolic manipulation and the highly abstract thought favored by the famous mathematician David Hilbert and his school at the University of Gottingen in the early 20th century seems to be rare. This is specifically mentioned because Hilbert’s extremely abstract approach to higher mathematics has come to dominate mathematics and theoretical physics in the 20th century.

Some Famous Flops

Complex algorithm research and development is a treacherous area. There have been numerous flops and fiascoes over the years. It is easy to misjudge the technical feasibility of projects. There is a long history of exaggerated claims for complex algorithms that emulate aspects of human intelligence such as speech recognition. There has been enormous success in data compression over the last few decades. Nonetheless, there is a long history of exaggerated claims for advanced in data compression. Video and other data compression involves complex algorithms that are difficult to evaluate. Caveat emptor!

The Pen computing fad of the early 1990’s is an example of a famous flop. The most prominent of these firms was Jerry Kaplan’s GO, described in his book Startup. GO and similar firms’ business plans hinged on handwriting recognition, an unsolved problem in pattern recognition. Kaplan actually devotes only a few pages of his book to the handwriting recognition problem.

Another notorious example is the speech recognition firm Lernout and Hauspie. Lernout and Hauspie collapsed in a major financial scandal with court cases and allegations of massive fraud. Again, the success of Lernout and Hauspie’s business depended on the solution of the speech recognition problem, which remains largely unsolved even today.

Note that many apparently sophisticated investors invested many millions of dollars in both GO and Lernout and Hauspie, even though a modicum of research would have revealed the poor state of handwriting and speech recognition technology at the time.

Some Famous Successes

Video and audio compression is one of the most successful areas in complex algorithms. Technologies such as VideoCD, DVD, MP3, and BluRay all incorporate sophisticated audio and video compression algorithms.

A major breakthrough in video compression reached the market in 2003, embodied in H.264, Windows Media 10, Flash Video, and other video standards and products. Prior to 2003 the bitrate for usable, loosely VHS quality video was about one (1) megabit per second. In 2003, the new video technologies achieved a bit rate of around 275 Kilobits/second, often with close to DVD quality with proper tuning of the compression. This was a truly major advance, a rare technological leap forward. This enabled YouTube and other forms of Internet/web video over DSL connections.

The bottom line is that complex algorithm research and development can be done, but it is difficult.

Software Engineering

There are significant differences between software engineering for complex algorithm research and development and mainstream software development. As mentioned above, complex algorithms often involve a tight coupling between parts of the algorithm that makes development more difficult and tedious than most software development.

It is often easier to research and develop complex algorithms using tools such as Matlab, Mathematica, AXIOM, or Maxima (formerly known as MACSYMA). These are scripting languages similar to Python or PHP. They usually have implicit variable declaration and/or conversion. They are usually “weakly typed” languages and break many textbook rules of “good” software engineering. They include comprehensive, well-integrated libraries of mathematical, numerical, and statistical functions. They usually have a data type known variously as a list, vector, or matrix that represents sequences of numerical or symbolic data in a flexible way. These tools are sometimes referred to as computer algebra systems (CAS), although this is really only one subset of their features.

Adding Two Vectors in Mathematica

A = {1.0, 2.0, 3.0}; (* A is a Mathematica list *)
B = {1.1, 0.0, 4.0};
C = A + B
Out[1]={2.1, 2.0, 7.0}

Adding Two Vectors in C/C++

#include <iostream.h>
double A[3] = {1.0, 2.0, 3.0}; // A is a C++ array
double B[3] = {1.1, 0.0, 4.0};
double C[3];
int index;

for(index = 0; index <3; index++)
   C[index] = A[index] + B[index];

cout << “{“ << C[1] << “,” <<
C[2] << “,” << C[3] << “}” <<
endl;

Note that there is a vector class template in the C++ Standard Template Library (STL) with somewhat similar properties to the lists in Mathematica. The above comparison is for illustrative purposes. Even using the STL classes, it is usually much easier to research, develop, and test algorithms in these tools than using traditional compiled, strongly typed languages such as C/C++, Java, or <insert your favorite programming language here>. However, these tools are slow and require large amounts of memory. This is a significant drawback. Once an algorithm is developed, it is often necessary to convert the algorithm to a fast compiled language for performance reasons. This is easier if the target fast language has good libraries of mathematical, numerical, and statistical functions.

One can also research and develop algorithms directly in a fast programming language such as C/C++ or Java. This avoids conversion costs, speed, and memory issues. However, it is often much easier to do research and development using a tool such as Matlab or Mathematica.

The leading algorithm research and development tools are:

• MATLAB: Matlab is widely used in the commercial world, especially in digital signal processing.
• MATHEMATICA: Mathematica is widely used in government sponsored research and development and academic research. It has a following in Wall Street finance and economics.
• AXIOM: Axiom is free, open source, with a Berkeley style license. AXIOM was started in 1971 and has over 300 man years of work integrated into it.
• MAXIMA: Maxima is free, open-source, with a GNU license.

Many fast programming languages have been used for complex algorithms. The most popular are probably:

• ANSI C: ANSI C is almost universally available for all processors. It is simple, efficient, with small memory needs and high speed.
• C++: C++ is object-oriented. It often has larger memory needs than C and can be slower.
• Java: Java is compiled to byte-codes, but is approaching C/C++ in speed. It can be slower and less efficient. It can be easier to reverse engineer.

The dream algorithm R&D tool would be similar to Matlab or Mathematica but could be compiled to fast, efficient binaries similar to ANSI C and would be available for all platforms. An integrated GUI builder similar to Visual Basic and integrated network support would be helpful. The biggest single weakness of all kinds of scripting languages is that they are slow and cannot be compiled. For compute- intensive complex algorithms this can be a very significant problem. Of scripting languages, only Visual Basic 6 appears to have solved the problem of producing a compiler that can produce binary executables with similar performance to C/C++.

These algorithm research and development tools are not, of course, a substitute for thought, creativity, and the extensive conceptual analysis frequently required for major advances. Trial and error alone, without insight, rarely succeeds.

Conclusion

Complex algorithm research and development can be done successfully. Some great successes exist. Nonetheless, it is not easy and many things can go wrong. The project scope is significant. Project feasibility is difficult to assess. Genuine breakthroughs are unpredictable and take time. The return on investment for a home run can be five to thousands of times the original investment. There are great unrealized opportunities, most of which require genuine research.

About the Author

John F. McGowan, Ph.D. is a software developer, research scientist, and consultant. He works primarily in the area of complex algorithms that embody advanced mathematical and logical concepts, including speech recognition and video compression technologies. He has many years of experience developing software in Visual Basic, C++, and many other programming languages and environments. He has a Ph.D. in Physics from the University of Illinois at Urbana-Champaign and a B.S.in Physics from the California Institute of Technology (Caltech). He can be reached at jmcgowan11 (at) earthlink.net.

References

Some Complex Algorithms

• MPEG compression, one of the great success stories: http://www.chiariglione.org/mpeg/
• x264 is a free, opensource h.264 video encoder: http://www.videolan.org/developers/x264.html
• The Carnegie Mellon Sphinx Project, an open-source speech recognition engine: http://cmusphinx.sourceforge.net
• National Library of Medicine Insight Image Registration and Segmentation Toolkit: http://www.itk.org

Books and Articles

1. Startup: A Silicon Valley Adventure, by Jerry Kaplan, Houghton Mifflin Co, Boston, 1995, ISBN 0-140-25731-4
2. “How High-Tech Dream Shattered in Scandal at Lernout & Hauspie”, by Mark Maremont, Jesse Eisinger, and John Carreyrou, Wall Street Journal, December 7, 2000
3. New Astronomy (Nova Astronomia), by Johannes Kepler, Translated from the Latin original by William H. Donahue, Cambridge University Press, Cambridge, UK, 1992, ISBN 0-521-30131-9

This article was written by John F. McGowan, PhD. If you’d like to write for Math-Blog.com, please email us at submissions (at) math-blog.com.

Bookmark and share: