UW computer scientists work to make computers smarter
“Mona Lisa ready to step out” demonstrates some of the image manipulation computers can do.
His back turned to a glowing computer screen, Oren Etzioni ponders before answering a basic question: What is software?
“Think of a computer as a puppet,” he says. “Without software, it’s just sitting there, limp, arms dangling at its side.”
Etzioni doesn’t say it, but you just know from his demeanor that he thinks it still takes far too much human effort to make the “puppet” do much beyond arm dangling.
The computer science professor is passionate about “intelligent” computers. He says it began when he read Douglas Hofstadter’s Godel, Escher, Bach: An Eternal Golden Braid in high school. He has no patience with computers that fail to understand what people want from them.
“If you get an error message, that’s a design flaw in the computer,” he says. “The message might suggest you’ve made the mistake. But the correct way to look at it is that the machine failed to understand you.”
Using artificial intelligence—the idea that robots and computers can be taught to act like intelligent living organisms—Etzioni wants to “raise the level of discourse between people and machines by making the machines smarter.”
Drawing on ideas from Hofstadter, Isaac Asimov and other visionaries, Etzioni and fellow software scientists delight in thinking about concepts with distant horizons. They foresee future civilizations where ever-helpful technologies liberate and elevate life. These technologies were spawned by something ancient and quaintly 20th century: computers.
Software engineers look to those concepts for ideas that can be applied now—or soon—by creating programs that will turn computers into the ultimate in personal assistants, capable of bringing out the best in their users and as easy and trustworthy to interact with as an old friend.
Etzioni’s efforts to make tomorrow’s computers more tolerant have resulted in “softbots.” These software robots, developed by Etzioni and Computer Science Professor Daniel Weld, could help millions of first-time computer users navigate the Internet—a network a Seattle Times columnist called “a vast, anarchical and thoroughly unorganized slag heap of raw data.”
But don’t confuse softbots with the kind of robot that vacuums the living room rug or walks the family dog. The electronic version doesn’t grip tools or go through the complex business of recognizing specific physical objects such as chairs, Etzioni explains.
Using a mouse in a menu-driven environment familiar to any PC user, Etzioni demonstrates how a softbot he calls Rodney can be instructed to find a professor’s office phone number. He tells Rodney the person’s name and the fact that he is a university professor. Nothing more.
Within a minute, Rodney responds with a phone number at the University of Maryland. To obtain it, Rodney searched a bibliographic data base for the person’s name. Learning that he had published papers at the University of Maryland, it then went through a series of searches to find the person’s electronic mail address. That led to the person’s phone number.
Next, Etzioni asks Rodney a deliberately dumb question: Does it know “anyone” in Maryland? Rodney responds with the name and phone number of the person it just looked up.
This demonstrates an important attribute of artificial intelligence: the ability to accumulate information and make further use of it.
How long would this overall exercise have taken without Rodney’s help?
“A computer hacker could do this a little faster than Rodney,” Etzioni replies. “But the goal here is not speed; it’s simply not having to do it.”
Etzioni does worry about a dark side to softbots—the possibility that they could cause harm. With more and more information on individuals being stored in computers—everything from what videos someone rented last week to when, where and how they paid for their last gallon of gasoline—softbot special agents could be capable, for instance, of mining significant amounts of data many people might like to keep private.
Softbot safety is discussed in a paper Weld and Etzioni wrote earlier this year entitled, “The First Law of Robotics (A Call to Arms).” The title pays tribute to Asimov’s 1942 classic, I Robot, which set forth the principle that every mechanical robot ever built would, above all else, not harm humans. The same rule should apply to softbots, Weld and Etzioni argue.
With softbots, Etzioni says the day also will come when people will be able to use natural language—the way they’d talk to a human assistant—to get the computer to do things for them.
“You’d say, ‘I’ll have my usual for dinner,’ and it will remember that you liked the pepperoni pizza from this particular chain,” he explains. “And it will know that the branch nearest you is closed but there is another one that can deliver it. And the softbot just goes out and orders it for you, keeping you isolated from all kinds of details that you couldn’t possibly keep track of and wouldn’t even want to know.”
Sounds quick and easy. But talk to any software scientist and you’ll soon discover that there’s nothing soft about creating software that works. While ideas might come from the world of science fiction, the realization comes from slogging through agonizingly detailed minutiae.
It’s called writing lines of code—very unliterary statements such as “put value of B plus C into A” that instruct computers how to do whatever task is at hand. Some software systems have tens of thousands of such lines; others, millions. Smooth functioning depends on all the lines working together.
“Basically, you have to give a set of instructions that is very precise,” says Etzioni’s colleague, David Notkin.
“When building a bridge across a river, a small change won’t necessarily cause harm. But in software, that’s not always true: you can make a one-statement change to a million-line program—a very, very small change—that affects the entire program,” he adds.
Such changes can be good or bad. Notkin and his students specialize in techniques that make everything throughout large software systems adapt and compensate to small changes. Thus, if a company wanted to convert its complex billing system to the nine-digit ZIP code, for instance, it could skip the disruption and cost of purchasing a new accounting system.
Sensitive software systems already have crept into many corners of our daily lives—from the centralized computers that clear all the personal checks in the nation every clay to systems under the hood of the family car.
“We all use computers hundreds of times a day without thinking about it,” says Notkin. “The fact is, like it or not, computers are going to be affecting more and more of your everyday life.”
New graphics software is one of those ways. UW computer scientists are writing graphics software that could give everyday PC users the power to create Hollywood-quality 3-D fantasy worlds right on their own desktop.
Now, such worlds are created only by expert programmers working on $100,000 workstations. But within a decade, predicts Computer Science and Engineering Professor Tony DeRose, “Your hardware will be able to support your being able to manipulate a complex virtual world, walk through it, visualize it, even be in it if you have a head-mounted display. And it will be as easy as using a word processor.”
With powerful graphics capabilities in their computers, people tied into the same networks could customize and participate in entire virtual worlds. “Part of the fun is that you will be able to take on an entirely different persona: have a mustache, be a woman or become a writer of romance novels,” he notes. “And if you have a million people contributing to a virtual world, it could start to get pretty darned interesting!”
Many complex technological issues remain to be resolved before the general public has access to such virtual worlds. DeRose and his computer science and engineering colleagues, including David Salesin, are among those perfecting experimental software to bring this day closer.
Currently, for example, the main way to create a computer representation of anything you’d want to include in a virtual—whether trees, chairs, desks or even—is to enter into a long and laborious process of creating the shapes, shadows and colors that make something appear “just right.”
While effective painting and drawing software already exists for computers, users still have to do everything pretty much by hand using a mouse or similar tool. To draw something even as simple as a golf club in anatomically and visually precise detail can take hours, DeRose says. “For anything complicated—a car, for instance—there’s an unimaginable amount of detail,” he points out.
The problem is that computers can’t see. “When you or I look at an object, we say, ‘Oh sure, that’s a distributor cap,'” explains DeRose. “It seems easy, but we’re using vast computational power built into us over 4 million years of evolution.”
DeRose wants computers to visualize physical objects with the same ease that occurs in the interchange of human mind and eye.
Look at it from the computer’s point of view: To “see,” computers must first receive the visual information in digital form, DeRose explains. For this, he uses a laser device to scan physical objects such as golf clubs or distributor caps.
For a distributor cap, the computer might have to ingest as many as 30,000 three-digit numbers—a memory-eating quantity equivalent to a novel or two of text. Multiply that by a virtual world consisting of hundreds of physical objects, all moving around the screen, and the problem comes into sharper focus.
“Imagine being given a list of numbers this long and asked not only to identify what it is but to give a concise geometric representation?” he says.
So DeRose has created software that boils the “novel” down to a few pages and also fills in the gaps between data points—critical spaces that make the object appear “whole” instead of just connect-the-dots. Using such software, DeRose believes industrial manufacturers such as Boeing might one day be able to store precise representations of airplanes in computers, not warehouses. Right down to the last nut and rivet.
Salesin, who holds one of the department’s 15 Presidential Young Investigators Awards from the National Science Foundation (NSF), shares DeRose’s interest in computational geometry. After graduating from Brown University, he spent several years at Lucasfilm, where he did computer graphics research and created animation software for a number of popular motion pictures.
His office shelves lined with a melange of computer and art books, Salesin explains how he and his students are developing new types of software capable of bringing out the artistic in virtually everyone who uses it.
With funding from the NSF and a number of private companies, including Xerox and Microsoft, Salesin uses a mathematical theory called wavelets in developing experimental computer graphics software.
Salesin, who along with DeRose has close ties to a strong computer graphics group at Microsoft, demonstrates how wavelets work by showing a large, detailed outline of Florida. As he shrinks the outline using his multi-resolution curve software, the level of detail decreases proportionately. Jagged sections of coastline shrink and melt into gently curving lines. But overall, the outline retains the same proportions.
The same process also works in reverse: as the object expands, the program fills in more detail.
“The idea is to have the computer—or the printer—handle only the amount of information it needs at any given time to execute a task,” he explains.
The technique has a number of other applications. For instance, it can be used to manipulate surfaces at different levels of detail: take a scanned image of someone’s face and change the curve of the nose to a finely stretched point, or elongate the curves all over the face. In either case, the face remains completely recognizable.
The same software facilitates interactive painting and drawing using computers. Salesin calls up one of his favorite demonstrations, “Mona Lisa ready to step out,” in which he has given the famous face a bit of eye shadow, lipstick and a playful glint in the eye.
Other software by Salesin and students transforms scanned photographs of people, houses and other objects into masterful pen-and-ink illustrations at the wave of a mouse. A similar program enables objects or scenes to be drawn from scratch but frees the artist from having to lay down repetitive pen strokes in areas of texture or detail.
Dan Ling, a senior researcher at Microsoft Research, says he is “very excited” about the relationship his graphics group has established with Salesin and DeRose. “We think that 3-D graphics and applications will be a very important part of consumer products in the future. That’s why we were very interested in establishing contact with David and Tony, who have an outstanding track record in this area.”
While he also values such interaction, Salesin has no plans for bolting to the private sector. “I have a lot of reasons for staying put,” he explains. “One of the big ones is that if I were working on my own or in a company, I maybe could pursue just one of these things. But working with students, we can do lots of things at once. It’s really great to see students learning to do research, too.
“There’s more than one way to get this stuff out to the world,” he adds.
DeRose and Salesin’s work is part of what Computer Science and Engineering Chair Ed Lazowska calls the “huge synergy” between Washington’s tremendously successful software industry and the UW, which Upside magazine last May dubbed “Seattle’s answer to MIT.”
“It would be overselling to claim that we have significant responsibility for all of the good things happening in Washington’s software industry,” says Lazowska. But, he adds quickly, you never see anything like this happen in a place that doesn’t have a major research university.
Today, about two-thirds of the students who graduate from Lazowska’s department—regularly ranked among the top 10 nationally—are gobbled up by Washington’s roughly 900 software firms. Most of these firms—unlike Washington’s famous software giant, Microsoft—have fewer than 10 employees and seem to spring up almost overnight.
Neither is the UW /software industry relationship anything new: The world’s first popular operating system for desktop computers, CP/M, was written in 1973 by one of the UW’s very first graduates in computer science, Seattle native Gary Kildall, who died last July.
And there are other links through alumni, including desktop publishing software pioneer Jeremy Jaech. After obtaining his UW computer science master’s degree in 1980, he helped found not one but two of the world’s most successful computer software companies, Aldus Corp. and Shapeware Corp.
Shapeware markets its popular Visio software drawing and drafting program worldwide. Shapeware President Jaech says his company benefits from a “strong, ongoing relationship with the UW.”
Research by faculty, graduate and undergraduate students figures prominently in these relationships. As Lazowska sees it, though, the goal of such research isn’t developing commercial technology: “Our faculty set out to do education and research, and they want to have an impact—not only directly, but through their graduating students. Sometimes companies spawn off to commercialize technology they’ve developed; we have to pay attention to that, but it’s not our fundamental goal.”
There are non-commercial applications of research as well. Computer Science and Engineering Professor Alan Barning, an expert on constraint-based programming languages, has created innovations used in software applications throughout the world. Many are in the public domain, available free over the Internet.
In drawing software, for example, his constraint-based programming ensures that a change in the length of one side of a triangle forces corresponding adjustments in the other two sides.
“We’re changing the kinds of commands you can give to the computer so that it’s easier to write programs that make computers easier for everyone else to use,” he explains.
Which begs a question: Do software engineers enjoy all these mental gymnastics? Barning thinks a moment. “It’s sort of a pain,” he admits.
But it’s what makes the puppet dance.