O-notation considered harmful (use Analytic Combinatorics instead)

From Robert Sedgwick's lecture "Analytic Combinatorics, Part I - A Scientific Approach".https://class.coursera.org/introACpartI-001/lecture/index

From Robert Sedgewick’s lecture “Analytic Combinatorics, Part I – A Scientific Approach”.
https://class.coursera.org/introACpartI-001/lecture/index

For so long I’ve been skeptical about the classic approach of the “Theory of Algorithms” and its misuse and misunderstanding by many software engineers and programmers. Big O notation, the Big Theta Θ and Big Omega Ω notations are often not useful for comparing the performance of algorithms in practice. They are often not even useful for classifying algorithms. They are useful for determining theoretical limits of an algorithms’ performance. In other words, their theoretical lower bound, upper bound or both.
I’ve had to painfully and carefully argue this point a few times as an interviewee and many times as part of a team of engineers. In the first case it can mean the difference between impressing the interviewer or missing out on a great career opportunity due simply to ignorance and/or incorrigibility of the person interviewing you. In the latter it could mean wasted months or even years in implementation effort and/or a financial failure in the worst case.

In practice the O-notation approach to algorithmic analysis can often be quite misleading. Quick Sort vs. Merge Sort is a great example. Quick Sort is classified as time quadratic O(n²) and Merge Sort as time log-linear O(n log n) according to O-notation. In practice however, Quick Sort often performs twice as fast as Merge Sort and is also far more space efficient. As many folks know this has to do with the typical inputs of these algorithms in practice. Most engineers I know would still argue that Merge Sort is a better solution and apparently Robert has had the same argumentative response even though he is an expert in the field. In the lecture he kindly says the following : “… Such people usually don’t program much and shouldn’t be recommending what practitioners do”.

There are many more numerous examples of where practical application does not align with the use of O-notation. Also, detailed analysis of algorithmic performance just takes too long to be useful in practice most of the time. So what other options do we have ?

There is a better way. An emerging science called “Analytic Combinatorics” pioneered by Robert Sedgewick and the late Philippe Flajolet over the past 30 years with the first (and only) text appearing in 2009 called Analytic Combinatorics. This approach is based on the scientific method and provides an accurate and more efficient way to determine the performance of algorithms(and classify them correctly). It even makes it possible to reason about an algorithms’ performance based on real-world input. It also allows for the generation of random data for a particular structure or structures, among other benefits.

For an introduction by the same authors there is An Introduction to the Analysis of Algorithms(or the free PDF version)and Sedgewick’s video course. Just to make it clear how important this new approach is going to be to computer science (and other sciences), here’s what another CS pioneer has to say :

“[Sedgewick and Flajolet] are not only worldwide leaders of the field, they also are masters of exposition. I am sure that every serious computer scientist will find this book rewarding in many ways.” —From the Foreword by Donald E. Knuth

 

Codebreaker – A new film about the life of Alan Turing

CODEBREAKER tells the story of one of the most important people of the 20th century.  Alan Turing set in motion the computer age and his World War II codebreaking helped save two million lives.  Yet few people have heard his name, know his tragic story, or understand his legacy.  In 1954, Turing committed suicide at age 41 after being forced to undergo hormone therapy to “fix” his sexual orientation.  He  left behind a lasting legacy and lingering questions about what else he might have accomplished if society had embraced his unique genius instead of rejecting it.  100 years after his birth, an international production team takes viewers on a journey to rediscover the man and the mystery.

Previously, previously and previously.

Cognitive Robotics And Artificial Intelligence

Eccerobot

Eccerobot

At the swissnex San Francisco conference earlier this year, scientists from Switzerland and the US discussed their research on humanoid robots, cognitive robotics, and artificial intelligence (AI). Talk revolved around how some robots self-reflect, self-improve, and adapt to new circumstances, and whether it’s possible for robots of the future to possess the same cognitive characteristics as humans.

more …

Welcome to John McCarthy’s new website.

From the website: John was a legendary computer scientist at Stanford University who developed time-sharing, invented LISP, and founded the field of Artificial Intelligence.* In March 2011 John launched Project JMC with the objective to make his work more approachable and accessible. The Project JMC team is continuing to help realize his objective. In this site you will find all John’s work, including his social commentary, and acknowledgements of his outstanding contributions and impact. Additional comments, suggestions, stories, photographs and videos on John and his work are very welcome. Please send them to the Project JMC team. His old website is here.

Chaitin Proving Darwin

White paper : To a mathematical theory of evolution and biological creativity

We present an information-theoretic analysis of Darwin’s theory of
evolution, modeled as a hill-climbing algorithm on a fitness landscape.
Our space of possible organisms consists of computer programs, which
are subjected to random mutations. We study the random walk of in-creasing
fitness made by a single mutating organism. In two different
models we are able to show that evolution will occur and to characterize
the rate of evolutionary progress, i.e., the rate of biological creativity

For many years we have been disturbed by the fact that there is no fundamental
mathematical theory inspired by Darwin’s theory of evolution.
This is the fourth paper in a series attempting to create
such a theory.

In a previous paper we did not yet have a workable mathematical frame-work:
We were able to prove two not very impressive theorems, and then the
way forward was blocked. Now we have what appears to be a good mathematical
framework, and have been able to prove a number of theorems. Things
are starting to work, things are starting to get interesting, and there are many
technical questions, many open problems, to work on.

So this is a working paper, a progress report, intended to promote interest
in the field and get others to participate in the research. There is much to be
done.

Artificial Intuition

Artificial Intuition – A New Possible Path To Artificial Intelligence – by Monica Anderson


Artificial Intelligence was born in Computer Science departments, and inherited their value sets including Correctness. This mindset, this necessity to be logical, provable, and correct has been a fatal roadblock for Artificial Intelligence since its inception. The world is Bizarre, and Logic can not describe it. Artificial Intuition will easily outperform Logic based Artificial Intelligence for almost any problem in a Bizarre problem domain. From the very beginning, Artificial Intelligence should have been a soft science.

Most humans have not been taught logical thinking, but most humans are still intelligent. Most of our daily actions such as walking, talking, and understanding the world are based on Intuition, not Logic.
I capitalize (for stylistic reasons) all major named memes such as “Intuition” and “Logic”
Others have used the label “Artificial Intuition” for other ideas.
I will attempt to show that it is implausible that the brain should be based on Logic. I believe Intelligence emerges from millions of nested micro-intuitions, and that true Artificial Intelligence requires Artificial Intuition.
Intuition is surprisingly easy to implement in computers, but requires a lot of memory.

In what follows I will argue that AN approaches are Biologically Plausible; that they rather elegantly sidestep many problems and limitations of Logic-based AI approaches; and that they are likely to be implementable in current or near-future generations of computer hardware.

LLATech’s “Artificial Intelligence And Intuition” article :

Roger Penrose considered it impossible. Thinking could never imitate a computer process. He said as much in his book, The Emperor’s New Mind. But, a new book, The Intuitive Algorithm, (IA), suggested that intuition was a pattern recognition process. Intuition propelled information through many neural regions like a lightning streak. Data moved from input to output in a reported 20 milliseconds. The mind saw, recognized, interpreted and acted. In the blink of an eye. Myriad processes converted light, sound, touch and smell instantly into your nerve impulses. A dedicated region recognized those impulses as objects and events. The limbic system, another region, interpreted those events to generate emotions. A fourth region responded to those emotions with actions. The mind perceived, identified, evaluated and acted. Intuition got you off the hot stove in a fraction of a second. And it could be using a simple algorithm.

Wired : ‘Artificial Intuition,’ Earthquake Detectors vie for Pentagon Prize


… an Israeli high-tech firm that has developed “artificial intuition” software that can scan large batches of documents in Arabic and other languages. According to the company’s website, this tool can “instantly assesses any Arabic-language document, determines whether it contains content of a terrorist nature or of intelligence value, provides a first-tier Intelligence Analysis Report of the main requirement-relevant elements in the document.

The Dangers of Computer Science Theory

Quotes from Don E. Knuth :


“If we make an unbiased examination of the accomplishments made by mathematicians to the real world of computer programming, we are forced to conclude that, so far, the theory has actually done more harm than good. There are numerous instances in which theoretical “advances” have actually stifled the development of computer programming, and in some cases they have even made it take several steps backward!”

(Whoah !)


“Thus the theoretical calculations, which have been so widely quoted, have caused an inferior method to be used. An overemphasis on asymtotic behavior has often led to similar abuses.”

(This is common in certain groups of programmers. Group-think ?)


“Another difficulty with the theory of languages is that it has led to an overemphasis on syntax as opposed to semantics. For many years there was much light on syntax and very little on semantics; so simple semantic constructions were unnaturally grafted onto syntactic definitions, making rather unwieldy grammars, instead of searching for theories more appropriate to semantics.”

(Is this why the current generation of programmers has such an unfounded aversion to languages that do not read like Java ?)


“You see that computer science has been subject to a recurring problem: Some theory is developed that is very beautiful, and too often it is therefore thought to be relevant.”


“My experience has been that theories are often more structured and more interesting when they are based on real problems; somehow such theories are more exciting than completely abstract theories will ever be.”


The Dangers of Computer Science Theory – Donald E. Knuth
[An invited address presented to the International Congress on Logic, Methodology and Philosophy of Science in Bucharest, Romania, September 1971. Originally published in Logic, Methodology and Philosophy of Science 4 (Amsterdam: Noth-Holland, 1973) 189-195.]
Selected Papers on the Analysis of Algorithm – Donald E. Knuth

Winter 2009 reading



Sonoluminescence: A Galaxy of Nanostars Created in a Beaker (NASA)

The Idea Factory – Learning to Think at MIT, Pepper White :

“This is a personal story of the educational process at one of the world’s great technological universities. Pepper White entered MIT in 1981 and received his master’s degree in mechanical engineering in 1984. His account of his experiences, written in diary form, offers insight into graduate school life in general—including the loneliness and even desperation that can result from the intense pressure to succeed—and the purposes of engineering education in particular. The first professor White met at MIT told him that it did not really matter what he learned there, but that MIT would teach him how to think. This, then, is the story of how one student learned how to think.”

Bio-Inspired Artificial Intelligence – Theories, Methods, and Technologies, Dario Floreano and Claudio Mattiussi :

“New approaches to artificial intelligence spring from the idea that intelligence emerges as much from cells, bodies, and societies as it does from evolution, development, and learning. Traditionally, artificial intelligence has been concerned with reproducing the abilities of human brains; newer approaches take inspiration from a wider range of biological structures that that are capable of autonomous self-organization. Examples of these new approaches include evolutionary computation and evolutionary electronics, artificial neural networks, immune systems, biorobotics, and swarm intelligence—to mention only a few. This book offers a comprehensive introduction to the emerging field of biologically inspired artificial intelligence that can be used as an upper-level text or as a reference for researchers.”

On the Edge – The Spectacular Rise and Fall of Commodore, Brian Bagnall :

“Filled with first-hand accounts of ambition, greed, and inspired engineering, this history of the personal computer revolution takes readers inside the cutthroat world of Commodore. Before Apple, IBM, or Dell, Commodore was the first computer maker to market its machines to the public, eventually selling an estimated 22 million Commodore 64s. These halcyon days were tumultuous, however, owing to the expectations and unsparing tactics of founder Jack Tramiel. Engineers and managers share their experiences between 1976 and 1994 of the groundbreaking moments, soaring highs, and stunning employee turnover that came with being on top of the PC world in the early computer business.”

The Road to Reality : A Complete Guide to the Laws of the Universe – Roger Penrose :

“At first, this hefty new tome from Oxford physicist Penrose (The Emperor’s NewMind) looks suspiciously like a textbook, complete with hundreds of diagrams and pages full of mathematical notation. On a closer reading, however, one discovers that the book is something entirely different and far more remarkable. Unlike a textbook, the purpose of which is purely to impart information, this volume is written to explore the beautiful and elegant connection between mathematics and the physical world. Penrose spends the first third of his book walking us through a seminar in high-level mathematics, but only so he can present modern physics on its own terms, without resorting to analogies or simplifications (as he explains in his preface, “in modern physics, one cannot avoid facing up to the subtleties of much sophisticated mathematics”). Those who work their way through these initial chapters will find themselves rewarded with a deep and sophisticated tour of the past and present of modern physics. Penrose transcends the constraints of the popular science genre with a unique combination of respect for the complexity of the material and respect for the abilities of his readers. This book sometimes begs comparison with Stephen Hawking’s A Brief History of Time, and while Penrose’s vibrantly challenging volume deserves similar success, it will also likely lie unfinished on as many bookshelves as Hawking’s. For those hardy readers willing to invest their time and mental energies, however, there are few books more deserving of the effort.”

Born to Run – A Hidden Tribe, Super Athletes, and the Greatest Race the World Has Never Seen, Christopher McDougall :

“Full of incredible characters, amazing athletic achievements, cutting-edge science, and, most of all, pure inspiration, Born to Run is an epic adventure that began with one simple question: Why does my foot hurt? In search of an answer, Christopher McDougall sets off to find a tribe of the world’s greatest distance runners and learn their secrets, and in the process shows us that everything we thought we knew about running is wrong.”