The North-west Passage

Since I was "outed" last week in an Edmonton Journal story, there is no need to hide my secret hobby any longer. For almost my entire life, I have had a fascination with the polar regions, with an emphasis on the Canadian Arctic. This has translated into a book collecting obsession, especially the Arctic and Antarctic exploration literature. Last year I realized my dream of many decades and sailed through the North-west Passage. I have been fortunate to visit many places in the world, but no trip has captivated me more than a trip to the Canadian north. I was inspired by the spectacular landscapes, watched incredible wildlife, reflected on the historic sites, and admired the local people of a place that is so near (it is Canada, after all), yet so far away.

The following are a few reflections from that trip. I flew from Toronto to Kangerlussuaq on the south-west coast of Greenland. The trip ended at the western end of the North-west Passage, and I caught a flight from Tugluktuk (on the northern mainland coast of Canada) back to Edmonton.

Approximate route of the trip (http://www.adventurecanada.com).

Jakobshavn Fjord
Most of the icebergs that are seen on the east coast of North America come from the Jakobshavn Fjord on the west coast of Greenland. Think of Greenland as being a large bowl, with mountains being the rim that keeps the water (ice) inside. There is so much ice in the interior of Greenland that the weight has pushed down the land -- most of the interior land is actually below sea level. The Fjord is one of the few drains for the ice to escape. Ice slowly moves down the Fjord, until reaching the "freedom" of Davis Strait. Oddly, the water currents carry the ice north into Baffin Bay, before eventually turning it around and then descending south.

The rate at which the ice traverses the Fjord has greatly accelerated in the past few decades (i.e., the bathtub is emptying faster). One theory is that the water on the ice surface melts, seeps into the cracks leading to the bottom of the glacier, and this helps “lubricate” the slide towards the ocean.

This is but one example of many that I saw that illustrated the effect of global warming on the Arctic. One can debate the causes of global warming, but there is no doubt that the impact on the north is profound, especially on the people and wildlife.

Ice flowing down the Jacobshavn Fjord. Note the large ship in the middle of the picture.

Beechey Island
The highlight of the trip was the visit to Beechey Island. Since the age of 12, I have been fascinated by the quest to discover the North-west Passage through the Canadian Arctic. I've read all the exploration journals, up to and including Roald Amundsen’s successful traversal of the Passage (1903-1906). Leading up to that you have the dramatic stories of Martin Frobisher's illusion of fool’s gold (1576-1578), the mutiny on Henry Hudson’s voyage (1610-1611), the incredible overland journey of Samuel Hearne (1770-1772), Franklin’s overland expedition that endured horrific starvation ("the man who ate his boots",1819-1822), the incredible escape of John Ross (1829-1833), Franklin’s tragic voyage for which there were no survicors (1845-1848), and the intense search for his fate that culminated in discovering a trail of bones and a single document (McClintock, 1857-1859). All these stories fired the imagination of a young boy would yearned to be an explorer. In many ways, I realized my dream by becoming a scientific explorer rather than a geographic explorer.

Beechey Island is where Franklin’s expedition spent its first winter (1845). Three men died and were buried on the Island. The graves are visible to this day (although the original headboards have been replaced with replicas), and were made famous in the 1980s when University of Alberta anthropologist Owen Beattie exhumed the bodies.

For me, it was a sombre experience to visit this sad memorial to the lost expedition. I felt compelled to dress in my best clothes, give a minute of silence, and reflect on the tragedy that befell these three men and, eventually, their compatriots. Amidst the barren landscape -- all rocks with not a sign of vegitation anywhere -- one could imagine the sense of isolation and hopelessness that the crew must have felt as their ships were soon to become inextricably trapped in the ice.

The three Franklin graves on Beechey Island (the fourth is from a Franklin search expedition).

Polar Bears
Two days later, our ship anchored in Conningham Bay on the south-east end of Prince of Wales Island. So far we had not seen any whales on the trip, and the captain decided to make a short detour because Beluga whales often populated the bay.  Although we arrived late at night and were far from the shore (because of shallow waters), from the ship’s bridge the crew could see animal activity in the distance. Thus, we were roused at 5:30AM and quickly boarded Zodiac boats to bring us closer to shore. Almost immediately we were witness to a spectacular sight. Apparently as many as six Beluga whales had been trapped near shore when the tide went out. They were quickly discovered by the polar bears, and the feast commenced. Before me I saw 22 bears: some were eating, mothers were caring for cubs, young bears were wrestling in the water, some were swimming, others were posturing. It is the grandest spectacle of raw Nature that I have ever witnessed.

The polar bears of Conningham Bay.

Navigating through "brash ice" (small pieces of icebergs) off the coast of Illulisat, Greenland. 

A Tale of Two Meetings

As one becomes more senior, it seems inevitable that a greater percentage of one’s time is spent in meetings. As a fledgling assistant professor, during a given week perhaps only 10% of my time was spent in meetings. As I built up my research program, there were more weekly meetings, mostly with students but also with collaborators. It was only once I became an Associate Professor with tenure that administrative meetings began to have a significant impact on my daily routine. These meetings were mostly in service of the inevitable set of Departmental and University committees that needed representation.

Beginning in 2005, when I became Acting Chair for Computing Science, I reached a critical tipping point: administrative meetings out-numbered research meetings. Over time, this trend has only accelerated such that most of my working day is spent in meetings, with only a small percentage of time available to meet with students or discuss research. I don't bemoan this change; after all, it was my choice to assume administrative responsibilities.

In the past two weeks, I have had two meetings that stand out in my mind. The details of these meetings have been obfuscated to protect the innocent, as well as being slightly embellished (to make a point).

Meeting A

A colleague and I met with a graduate student to discuss progress related to their thesis. The student had a satisfactory work plan that would take her through the remaining tasks towards a successful graduation. But as she talked, it dawned on me that the work could be couched in a more general way. I interjected with my idea, and for the next hour or so we went off on a brainstorming tangent. Suggestions and ideas flowed easily, and the level of excitement kept rising. Eventually, we had to stop, but only because of other commitments. We resumed the next day and made more progress, but the level of passion had been partially diminished by the interruption.

The result of the meetings was an important contribution to the student’s thesis, and one that will allow us to make broader claims about the impact of her research. The real value to me was the joy of being creative. The first meeting was exciting – even inspirational. I have had many exhilarating research meetings in my life, some of which are forever imprinted on my mind. They are very special memories. Letting one’s imagination run wild is one of the joys of life.

Meeting B

I sat around the table with four colleagues, discussing strategies for dealing with an important administrative problem. There were few options available to us, so each was assessed for its short- and long-term impact. By the end of the meeting, there was consensus on the right strategy to adopt. It was a workman-like meeting, focused on the matter at hand with no deviations from the agenda. In summary, it was a satisfying meeting that achieved all of its objectives.

For a professor, job satisfaction comes when one has at least 10% of their time for “inspiration” to offset the 90% for “perspiration”. Although we all love the time we spend being creative, you can’t eliminate or play down the importance of perspiration. After all, it can take a lot of work (perspiration) to realize one good idea (inspiration). The chance to come up with a new idea -- imaginative, innovative, inspired -- is seductive.

Research meetings can take me to an intellectual high that is greater than anything I have ever experienced in an administrative meeting. Administrative matters can lead to creative solutions, but in my experience they are the exception rather than the rule. I go into every research meeting hoping to be excited, but I go into every administrative meeting praying to be satisfied.

The implication for me is obvious: I need more meetings that generate ideas -- brainstorming -- and less that deal with mundane matters.

The Horseless Carriage Becomes the Driverless Car

Toronto, Ontario. The annual Association for the Advancement of Artificial Intelligence conference ended yesterday. For me, Thursday’s talk by Sebastian Thrun (Stanford University and Google) was a highlight: Google’s self-driving car project. The bottom line: this technology isn’t science fiction any more. More than a century ago, the introduction of the horseless carriage dramatically changed the world. The next step in this evolution, the driverless car, promises to be no less impactful.

Sebastian is passionate about building robotic systems for every-day use. For a decade now, he has been concentrating on self-driving cars. Seeing a car pull up beside you with no one in the driver’s seat would be an unnerving experience for most, but for Sebastian it’s a daily experience. In 2005, his team won the U.S. Department of Defense Grand Challenge, having a computer-controlled car successfully travel 212 kilometers on California desert roads. His team came second in the 2007 Grand Challenge, where the car had to navigate through a mock-up downtown area. Since 2010 he has been working with Google on realizing his dream of turning this technology into something that will change the world.

In 2006 I saw him give a presentation on his work. It was interesting, but the road (so to speak) from where he was to where he wanted to be was long and the research problems to be solved, hard. Six years later, the only word I can use to describe where he’s at is “stunning.” The advances that have been made are truly impressive, suggesting that the technology is almost ready for prime time. Sebastian says it’s at least a decade way from being widely deployed. More on this later.

The Google car is being extensively used in the San Francisco and Silicon Valley area. To date it has 320,000 kilometers of accident-free driving. Can you make the same claim? Sebastian showed numerous impressive videos of the car doing its thing, such as driving down San Francisco’s (in)famous Lombard Street, negotiating downtown traffic, and easily traversing highways. What made this even more impressive was that demos showed the car performing well in a variety of difficult situations, including day and night (day turns out to be harder because of the sun), in the presence of pedestrians, and even through a construction zone (lanes shifted). In the latter case, although the car uses GPS maps, it has the ability to improvise when it comes across signs that force it to deviate from its planned route. Impressive!

The technology has been added to a handful of smaller vehicles (golf carts). He showed a video where a person uses their phone to request a ride. The call is routed to an available vehicle that, upon receiving the request uses your GPS coordinates to automatically drive to you. Imagine how this could change your life. You can be chauffeured anywhere, sans the chauffer.

Sebastian revealed some interesting details on the car’s performance. It tends to drive slower than other vehicles on the road (not a surprise given safety concerns), prefers an interior lane (the vision system works better if there’s left and right feedback), does less braking and less acceleration than humans, and maintains a safer distance between cars (which helps reduce the chance of an accident).

What remains to be done? Lots, mostly special cases. For example, the research team has not addressed the problem of snow and ice. They admit that their work has been California-centric. Another example he cited was a policeman on the road directing traffic. This situation is challenging since the software needs to distinguish a policeman from a pedestrian, and understand that the hand gestures have meaning. They also have problems with sudden surprises, such as an animal running across the road. He did not mention a variety of other possible situations, such as getting a flat tire, hitting a pothole at high speed, or being crowded by another vehicle (does the car honk its horn?). Every one of them has to be addressed and then thoroughly tested.

Sebastian believes that it will take at least a decade before we will see widespread use of driverless cars on the road. Part of the reason is the many uncommon circumstances that need to be addressed. However, the bigger hurdles have nothing to do with technology: political, legal, and psychological matters all stand in the way. As well, insurance companies will have to weigh in.

The implications of this technology if/when it becomes commercially viable are transformative, some of which include:

•  improved quality of life (the one-hour daily commute becomes usable time);
•  fewer accidents (data strongly supports this case);
• increased freedom for people with mobility-related disabilities; and
•  better traffic throughput (less need for increased road infrastructure).

A high-reliability self-driving car will dramatically change the world as we know it. I have seen the future and it’s exciting, coming much sooner than I would have expected, going to have enormous societal benefits, and will be transformative.

It’s not often that I come away truly excited about technology. A single research talk has made this a memorable day for me. I will not soon forget the excitement I felt being in the audience for Sebastian Thrun’s wonderful talk. 

“Big Breakthroughs Happen When What Is Suddenly Possible Meets What Is Desperately Necessary” – Thomas L. Friedman

Toronto, Ontario. I am attending the annual conference of the Association for the Advancement of Artificial Intelligence (AAAI). This year roughly 1,000 attendees have converged on Toronto to hear about and see demonstrations of the latest advances in building “intelligent” computing systems.

This morning I attended Andrew Ng’s talk on “The Online Revolution: Education at Scale.” For those of you who may not have been following the shake-up that’s happening in higher education, Andrew is at the heart of the revolution. In the fall of 2011, he taught his Stanford University course on Machine Learning to 400 students in class, simultaneously with 100,000 students online. That course (and the Artificial Intelligence course taught by Sebastian Thrun and Peter Norvig) ignited a firestorm, generating massive international media attention on MOOCs – massive open online courses. The result was that Andrew (with colleague Daphne Koller) founded Coursera and Thrun started Udacity, both companies having the goal of bringing superior educational courses to the world via online technology.

Here is a brief summary of the key points in Andrew’s talk. Warning: this is a much longer post than usual. There is lots to talk about!

Motivation

Andrew argues that world-wide there is a shortage of opportunities for getting access to high-quality higher education. There are many reasons for this, including financial obstacles and limited enrolments. By offering courses online for free, both barriers get razed. His online Machine Learning course reached an audience 250 times larger than his traditional in-class audience. He did not say how many successfully completed the course. I understand from other sources that it was around 5,000. Still, getting that many people to pass an advanced highly-technical course is stunning.

Of course, there is a difference: a certificate for passing an online course is not the same as academic credit towards a Stanford degree. However, in terms of learning outcomes, the point is mute.

Of interest is that he received appreciative feedback from people around the world, such as from a 39-year-old single mother in India who had never dared to dream of taking a Stanford University course. When I went to talk with Andrew after his lecture today, I had to wait in line. Most of the 20 people ahead of me were international students who had enrolled in his online course. They wanted to thank him in person for their excellent learning experience.

In less than a year, Coursera has had 800,000 registrants from 190 counties for a total of 2 million course enrollments in the 111 online courses offered (science, humanities, business, etc.). No word on how many people passed the courses. Regardless, by any standard these are impressive numbers.

Andrew noted that many people did not finish a course because “their life got busy”; they could not sustain the three-month intensive experience. Coursera is considering offering courses at “half speed,” to spread the workload over a longer period.

Secrets of Success (1): Video-based Instruction

I have looked at courses offered by Udacity (specially filmed) and Coursera (professor lectures), and been more impressed with the Udacity production values. However, Andrew argued that the lecture approach is critical to success. Instructors can create lectures in their home or office; all they need is a quiet space with a computer and web cam. This avoids the expensive production infrastructure that, presumably, Udacity invests in. The argument is that this is the easiest way to quickly scale up the number of courses available since, essentially, it enables anyone to prepare an online course.

Coursera doesn’t offer the traditional hour-long lectures. Instead the material is broken into 10-minute “bite-sized” chunks, allowing students to more easily absorb the material.

Students are presented with optional pre-requisite material (for those who need to refresh their background skills) and optional advanced material (for the keeners). This allows Coursera to say they have moved away from the one-size-fits-all model offered by most online courses.

Secrets of Success (2): Assessment

Andrew argues that the online world allows for novel assessment opportunities. He did not claim this, but I inferred that he believed they were superior to traditional assessment models. He raised several important points:

• videos can have test questions interspersed, allowing the student to pause (for as long as they want) and test whether they understand the material;
• Coursera uses extensive software-based tools to validate student answers;
• students can attempt a problem as many times as needed until they get it right;
• additional test questions can be automatically generated;
• the online system can be adaptive so that when a student makes a mistake, they are pointed to the relevant instructional material; and
• use of a peer grading system.

The last point is critical to their model. The education literature, as well as Coursera’s own research, says that peer grading can be highly correlated to grading done by the instructor. By combining peer grading with crowd sourcing, Coursera can scale up to accommodating (hundreds of) thousands of students.

Students must attend a grading boot camp. They demonstrate their proficiency by assigning marks to assignments that have already been graded by the instructor. If their result closely matches that of the instructor, then they are allowed to grade other students’ work. For each course assignment, every student is expected to grade five and, in return, gets feedback from five. Coursera has data to say this produces high-quality results.

Secrets of Success (3): Community

The global nature of the course audience means that students have 24x7 access to course assistance. A support community quickly builds, with students helping each other. For the Machine Learning course, the median time for a student question to be answered by someone was 22 minutes – much better than anything I could ever do in any course that I have taught.

Perhaps surprisingly, some of the online study groups translated into face-to-face study groups, including two in China, three in India, and one in London. A study group has recently been set up in Palo Alto and 1,000 people have signed up!

Secrets of Success (4): Statistics and Analytics

I have read several papers in the education literature that involve experiments with human subjects. They usually involve small samples (as low as five, and rarely more than 100). As a scientist who is used to working with large data sets, I find these papers unsatisfying. Contrast that with what Coursera is doing. Because of the large enrolments, they have the opportunity to do some amazing analysis. For example, to test a hypothesis they will use data gathered from 20,000 students, with a further 20,000 as a control group. They collect anonymized data on every student mouse click, key stroke, time spent reading a web page, number of times questions were answered incorrectly, how often a video is watched, and so on. They mine this data to better understand the pedagogy of their courses – what works and what doesn’t work. Andrew claimed that what Amazon did for e-commerce, Coursera will do for e-education.

He gave one interesting example of how data mining can work. On an assignment, the system identified that 2,000 students submitted the same wrong answer. After manually looking at the incorrect solutions, it became clear that there was a trivial misunderstanding. The online system was then modified to detect when the mistake is made and then point the student to a web page that hints at what they are doing wrong. Coursera is working on automating this process.

Conclusions

Andrew raised an interesting characterization of how the online world differs from the in-class experience. In a traditional course, time is held constant (you need to complete something by a specific date); the amount you learn is variable. In a Coursera course, the amount you learn is a constant (you can try as many times as you like until you get it right); the time you spend on the course is variable. He believes (and may have data to support his claim) that the amount learned per student in his online course was higher than for his in-class course.

Whether you agree or disagree with the move towards online education is irrelevant; it;s here and it's not going away. How often does university teaching attract extensive international media attention? These massive open online courses may be the disruptive technology that will shake the traditional educational system to its very foundation. It is too early to know the full implications of what is happening, but it is obvious that we are only feeling the tremors of change right now; the full seismic impact is yet to come.

Let me conclude with a quote from the New York Times: “This is the tsunami,” said Richard A. DeMillo, the director of the Center for 21st Century Universities at Georgia Tech. “It’s all so new that everyone’s feeling their way around, but the potential upside for this experiment is so big that it’s hard for me to imagine any large research university that wouldn’t want to be involved.”

We Have The World’s Fastest Computer Program For Solving Rubik’s Cube. Who Cares?

Niagara Falls, Ontario.  The fourth annual Symposium on Combinatorial Search (SoCS) started this evening. Fifty-five of the top people in this research area will spend two days intensely discussing the latest results. I hope to come away with at least one good idea from this event.

Let me tell you a bit about my research and then use that to motivate the point I want to make in this blog posting. I am best known for my work in applying artificial intelligence technology to computer games and puzzles (one-player games). Consider the well-known Rubik’s Cube. This puzzle is daunting to solve for a human, but what about a computer? Combinatorial search, the subject of the SoCS conference, includes the search techniques used to sift through the myriad of move sequences that one can try to solve the puzzle. Humans solve Rubik’s Cube non-optimally, using many unnecessary moves to orient the Cube into a familiar position. As computer scientists, we do not want just any answer; we want the optimal answer – solve it in the minimum number of moves.

Technology developed by Joe Culberson and I (pattern databases) in the mid-1990s is used by many puzzle-solving programs. For Rubik’s Cube, Rich Korf (UCLA) used our work to build the first practical solver. Today, a team of Israeli (Ariel Felner) and University of Alberta (Robert Holte and I) researchers have the fastest program for getting an optimal solution to this challenging puzzle. Fastest. In the world.

From an article on Rubik's Cube and my work on Checkers
www.sciencenewsforkids.org/2007/09/play-for-science-2

 We’re number 1! We’re number 1!

<Wait for applause>

<Deadly silence>

<Sheepish person bravely speaks up>

“Excuse me, sir. Who cares that a computer can solve Rubik’s Cube?”

<Pause while I compose myself>

Solving Rubik’s Cube, in and of itself, isn’t earth shattering. The world is not a better place because computers have super-human skills here. It's not the application that's important; it's the techniques used to solve the problem. Where can this technology be used? Real-world problems such as:

• Path finding: finding the shortest route between two locations. This is used in GPS systems, computer games, and even on Mars (the Mars Rover). It would be pretty cool if I found out I had created “out of this world” technology.
•  Scheduling: produce a schedule that satisfies constraints. The technology can be used for arranging a trip (minimal travel distance), airline schedules (guarantee that the planes will be in the right location at the right time), and classroom bookings (accommodate all the classes at appropriate times without conflicts).
• DNA sequence alignment: measuring the similarity of two strands of DNA. The measure is important to researchers as they attempt to decipher the human genome.

Working with puzzles is an example of curiosity-based research. You investigate a challenging problem to devise better ways of solving it – perhaps getting an answer faster, or getting a better answer. If all your new technology can do is solve that one problem, then it’s probably not interesting (unless the problem being solved is important). More often than naught, the application domain is a placeholder for a class of problems. In my case, I use games and puzzles as my experimental test-bed because a) they are fun to work with and b) they map to real-world situations.

Over the past decade, research funding in Canada has become increasingly targeted towards projects that have direct industrial applications. The reasoning is obvious: potential economic impact. But this is a short-term view. What about research that produces results for which there is no obvious “usefulness”? Consider the recent discovery of the Higgs boson. There are no commercial products that will likely come out of the discovery itself. However, there can be side effects. For example, building the billion-dollar infrastructure needed to “see” the Higgs may have real impact; surely creating the technology needed to find a particle so small that you can pack 10²⁵ of them into a kilogram will translate into products.

Research does not have to have commercial value to be valuable. One can never predict how ideas will eventually be used. For example, in my area of games, an innocuous Ph.D. thesis of less than 30 pages published in the early 1950s has enormous commercial impact today. Three decades later, John Nash’s work on equillibria in games (showing that in some games a state can be reached where neither player has an incentive to change their strategy) became essential for diverse applications such as auctions and military strategy. Nash won the 1994 Nobel Prize in Economics and was the subject of the Academy-Award-winning film A Beautiful Mind.

As a society we must continue to fund – even grow – our investments in curiosity-driven research. A faster Rubik’s Cube solver may not mean much today, but who knows about tomorrow?