April 12, 2017
Isaac J. Michaud, PhD Candidate
Sitting in traffic leaves you plenty of time to think about whether there is a faster way of getting to work. Inching along thinking about the problem, you imagine the myriad routes you could take. How would you ever find the best one?
If we thought like computers, we would approach the problem in a straightforward and inefficient way. Every day we would pick a different route between our home and work and see how long it takes us. Over time we would try every route and would know which is the best. It would take us years or perhaps even decades to get our answer. By that time, the answer would be useless because we’d have switched to a new job or moved.
This is all quite silly, you say to yourself; no one would ever try every route–and you are right! The point I am making is that computers are only as intelligent as the instructions we give them. They are simple machines, like pulleys and levers, for the human mind. They magnify our ability to solve problems. If we can turn a complex problem into a long series of easier tasks, then we can feed it to a computer. The computer’s tremendous speed then augments our problem-solving.
Going back to our original problem, I bet you already have a better strategy to find the best route. You may have thought of some principles that would guide our search. Here are two that I think are reasonable:
(1) Shorter routes (in miles driven) are better than long routes. If you could fly to work the problem would be simple because you could take a beeline to work. It would have the shortest travel time, but you have to travel along roads. Even so, the fastest path is probably among the shortest paths. In other words, we would not consider a cross-country trip as a plausible commute. This principle filters out possibilities which we wouldn’t want to waste our time testing.
(2) Similar routes will have similar travel times. Small differences between routes will only result in small differences in the travel time. Clearly, using an interstate will be a very different than using secondary roads. But two routes going over most of the same secondary roads will be nearly the same. Therefore, we can infer the time a route will take if we have already driven a similar one in the past.
Now we can start the process of sifting through all the routes. Principle (1) tells us whether a route is plausible. Principle (2) says that we can change our beliefs about the plausibility of a route based on those routes we have already tested.
To begin, you may take a route that is short but drives straight through downtown. You get snarled in traffic and are late for work. The next day, when picking a new way, you know that routes that go through downtown are slow, so you pick one that avoids downtown. Repeating this winnowing process, you will find the best route in a few days.
This solution approaches the problem in the same way that humans learn. People use their logical reasoning to explore and create generalizations about the world. They adapt to new information without being reprogrammed. Is it possible to get a computer to do the same?
The trick is to translate the problem into terms that a computer can understand. The details can become complicated because you need to mathematize the problem. We must embed the rules mentioned above into a statistical model. This model provides the computer with the language it needs. It can then describe a plausible solution and update these descriptions with new information. The computer is free to use its speed to do the exploration and updating of beliefs.
The term for this algorithm is Bayesian Optimization. It represents the current cutting-edge of solving optimization problems. Beyond finding the best route to work, there are many areas of our lives that are touched by optimization. Maximization and minimization are instrumental in providing us with the quality of life we enjoy today. How well Amazon can cut overhead determines the price of the products we buy. If Ford engineers can maximize the MPG of your car, you will consume less gasoline. Without optimization, we would always be doing things inefficiently!
These important optimization problems are always growing in complexity. They are too complex for humans to solve by hand and too complex for a computer to brute-force. But by changing how a computer approaches optimization, we can solve problems that were once impossible.
Isaac is a PhD Candidate whose research interests include epidemiology, differential equation modeling, and reinforcement learning. His current research focuses on pursuit-evasion and cooperative reinforcement learning. We thought this posting was a great excuse to get to know a little more about him, so we we asked him a few questions!
What do you find most interesting/compelling about your research?
I enjoy working on hard problems. They give me something to always be thinking about.
What do you see are the biggest or most pressing challenges in your research area?
The development of theory is the most pressing challenge. Theory tells us why things work and without which we will be lost when things break.
The Archangel Gabriel is known as the left-hand of god. How did he get that nickname? (Hint: it was in middle school.) Your answer should be exactly 666 characters.
My answer has been encrypted using a one-time pad. It is impossible to crack unless you are omniscience. I did not encrypt the space or punctuation characters to retain a semblance of the original text. Even though this significantly reduces the entropy of the final ciphertext, it is still uncrackable.
Yxf fgzll nf xjv yz xp mlywg gfxke iqxlfw? Yvkw kgezu bg sae istyplmm heiqz wroe Aiggg pfs grzr nyqu iu re askac. Y ak ywtoa xy ypomtkyg flri kgukslbe ko kedj xbv cpvcg. Iabfbn, Pik hs pky nerdpaltc vs ewazw btzpch odufwg. Ca xao ndqis es gqaxj kgi fftetqvu cjjptjkk. Nda qlkqszbi qsb Lobvuef. Dyhspze kqekn gvvm Nas clsttgxc uh wud eszznsu’p arzhiy. Ddgygkz yvh qf hknh xete Bjo mrmqvrrpd gwy rjy ijoa veob xy Oic htdbscg jvy mxmi wxqk og gbvlv if frw ppukk wlzw bie Rrcyfzs hxb tvf qhrp rlxbess cdkg avlhc rzsw keo dhejq xji xo Tmc. Ue trcfr bkf rwqe rm! Djx igz a nzqximqdi, fnu Kecxuzo vqh o abaedylm puwfxz owouk. D igld tgbw Zseit dkxr vdlp. Kcgn ze rjq! Yyin!