Computational Biology Hosts Its First Precollege Program

Sampling, Analysis of River Microbes Provides Hands-On Learning

Lucia Barrera's father is a computer scientist, so she's gotten an earful about how computation is impacting biology, her major interest. After attending Carnegie Mellon University's precollege program in computational biology in July, the New York City girl thinks maybe the old man is on to something. "It really is the future of biology," she said as the three-week residential program was nearing its end. "You just can't work with large data sets without computing power." She and 25 other high school students attended the Computational Biology Department's precollege program — the nation's first for computational biology. They split their time between computer labs and wet labs, using computational methods to perform actual microbial research in a matter of weeks that would otherwise take years using traditional methods for colonizing bacteria. Phillip Compeau and Josh Kangas, both assistant teaching professors, co-direct the program. Its curriculum was similar to a module of a lab course Kangas teaches for undergraduate computational biology majors. The idea, Kangas said, is to push the students to learn by gathering real biological data and analyzing it with computational methods to solve real problems. First, the students went on a cruise on Pittsburgh's three rivers, where they collected water samples. Then, working with Kangas, they learned to perform DNA sequencing of the bacteria in each sample. Finally, Compeau taught them how to use software to analyze the data in the computer lab. The students learned methods and techniques, but they also performed actual research, observing how microbial communities in the river differ depending on location, season and proximity to pollution sources. "It's a real, modern problem that requires a real, modern solution," Compeau said. Data from the summer program, combined with data previously gathered by undergrads, shows that bacteria in Pittsburgh's rivers change with the season. "You can use bacteria almost like a calendar," Compeau added. Pending some final test results, plans are to submit those findings for publication. Likewise, the DNA sequence for a bacterium isolated by the students but apparently never before sequenced will likely be submitted. "That's cool," Berrera said of the never-before-sequenced bacterium. "That was something that my school never would have been able to do." "It wasn't all theory," said Stephanie Eristoff, a rising senior at the American School in Tokyo. "We were able to apply algorithms to real data." She said she appreciated the program's balance between wet labs and computer labs, and said she plans to use what she learned this year in her synthetic biology club. "This was a really amazing experience," she said.

Procaccia Wins Social Choice and Welfare Prize

Ariel Procaccia, an associate professor in the Computer Science Department, has been awarded the 2020 Social Choice and Welfare Prize for his work on social choice and fair division. In 2014, Procaccia launched the not-for-profit website "Spliddit," which creates provably fair solutions to help people divide anything from cab fare to football tickets. To date, the site has attracted more than 160,000 users. Procaccia and his team developed most of the algorithms used on the site, including the one used for the most popular application — rent division. "He is a deep mathematician with an uncanny instinct for turning theoretical results into concrete methods for solving real-world problems," said Herve Moulin, a professor of economics at the University of Glasgow who nominated Procaccia for the award. "Ariel's recent work on liquid democracy, on redistricting to avoid gerrymandering and on statistical approaches to voting continue to open new directions where social choice can and probably will develop soon." Fair division has been "a very theoretical area since it started in the 40s," Procaccia said. "What's special about Spliddit is that it's getting these algorithms out there and getting people to actually use them." The award, presented every two years by the Society for Social Choice and Welfare, has primarily recognized economists. Procaccia said it is significant that the community is looking closer at the role of computer science in fair division. "People realize there's a lot computer scientists can contribute to these discussions," Procaccia said, "and the fact that these things are getting applied is drawing people in and bringing excitement."

Oflazer Authors Resource for Understanding Turkish Natural Language and Speech Processing

Kemal Oflazer, associate dean for research at Carnegie Mellon University in Qatar and a faculty member in computer science, has authored "Turkish Natural Language Processing," a one-stop resource for understanding the state of the art in Turkish natural language and speech processing. Oflazer has spent the last 25 years developing techniques and resources for natural language processing for Turkish, which offers challenges for the field that aren't present in English. For example, Turkish is an agglutinative language, which means that suffixes attach to a root word like beads on a string. One complex Turkish word with several suffixes could express the same meaning as an entire sentence in English. The language also contains other interesting properties, such as free word order where the subject, object or verb can be arranged in any possible order (whereas in English the order is more or less fixed.) The book was published in 2018 and more than 2,000 copies of various chapters have been downloaded. Turkish is spoken by more than 70 million people in Turkey, the Middle East and in European countries, and the wider family of Turkic languages are spoken as a native language by approximately 165 million people worldwide. Before joining CMU’s Qatar campus, Oflazer received his Ph.D. from the CMU's Computer Science Department.

Carnegie Mellon and Facebook AI Beats Professionals in Six-Player Poker

"Superhuman" Card Shark Achieves New AI Milestone

An artificial intelligence program developed by Carnegie Mellon University in collaboration with Facebook AI has defeated leading professionals in six-player No-Limit Texas Hold'em, the world's most popular form of poker.The AI, called Pluribus, defeated poker professional Darren Elias, who holds the record for most World Poker Tour titles; and Chris "Jesus" Ferguson, winner of six World Series of Poker events. Each pro separately played 5,000 hands of poker against five copies of Pluribus.In another experiment involving 13 pros, all of whom have won more than $1 million playing poker, Pluribus played five pros at a time for a total of 10,000 hands and again emerged victorious."Pluribus achieved superhuman performance at multiplayer poker, which is a recognized milestone in artificial intelligence and in game theory that has been open for decades," said Tuomas Sandholm, Angel Jordan Professor of Computer Science, who developed Pluribus with Noam Brown, who is finishing his Ph.D. in Carnegie Mellon's Computer Science Department as a research scientist at Facebook AI. "Thus far, superhuman AI milestones in strategic reasoning have been limited to two-party competition. The ability to beat five other players in such a complicated game opens up new opportunities to use AI to solve a wide variety of real-world problems."A research paper, "Superhuman AI for Multiplayer Poker," will be published online by the journal Science on Thursday, July 11."Playing a six-player game rather than head-to-head requires fundamental changes in how the AI develops its playing strategy," said Brown, who joined Facebook AI last year. "We're elated with its performance and believe some of Pluribus' playing strategies might even change the way pros play the game."Pluribus' algorithms created some surprising features in its strategy. For instance, most human players avoid "donk betting" — that is, ending one round with a call but then starting the next round with a bet. It's seen as a weak move that usually doesn't make strategic sense. But Pluribus placed donk bets far more often than the professionals it defeated."Its major strength is its ability to use mixed strategies," Elias said last week as he prepared for the 2019 World Series of Poker main event. "That's the same thing that humans try to do. It's a matter of execution for humans — to do this in a perfectly random way and to do so consistently. Most people just can't."Pluribus registered a solid win with statistical significance, which is particularly impressive given its opposition, Elias said. "The bot wasn't just playing against some middle-of-the-road pros. It was playing some of the best players in the world."Michael "Gags" Gagliano, who has earned nearly $2 million in career earnings, also competed against Pluribus."It was incredibly fascinating getting to play against the poker bot and seeing some of the strategies it chose" Gagliano said. "There were several plays that humans simply are not making at all, especially relating to its bet sizing. Bots/AI are an important part in the evolution of poker, and it was amazing to have first-hand experience in this large step toward the future."Sandholm has led a research team studying computer poker for more than 16 years. He and Brown earlier developed Libratus, which two years ago decisively beat four poker pros playing a combined 120,000 hands of Heads-Up No-Limit Texas Hold'em, a two-player version of the game.Games such as chess and Go have long served as milestones for AI research. In these games, all of the players know the status of the playing board and all of the pieces. But poker is a bigger challenge because it is an incomplete information game: players can't be certain which cards are in play and opponents can and will bluff. That makes it both a tougher AI challenge and more relevant to many real-world problems involving multiple parties and missing information.All of the AIs that displayed superhuman skills at two-player games did so by approximating what's called a Nash equilibrium. Named for the late Carnegie Mellon alumnus and Nobel laureate John Forbes Nash Jr., a Nash equilibrium is a pair of strategies (one per player) where neither player can benefit from changing strategy as long as the other player's strategy remains the same. Although the AI's strategy guarantees only a result no worse than a tie, the AI emerges victorious if its opponent miscalculates and can't maintain the equilibrium.In a game with more than two players, playing a Nash equilibrium can be a losing strategy. So Pluribus dispenses with theoretical guarantees of success and develops strategies that nevertheless enable it to consistently outplay opponents.Pluribus first computes a "blueprint" strategy by playing six copies of itself, which is sufficient for the first round of betting. From that point on, Pluribus does a more detailed search of possible moves in a finer-grained abstraction of the game. It looks ahead several moves as it does so, but does not look all the way to the end of the game, which would be computationally prohibitive. Limited-lookahead search is a standard approach in perfect-information games, but is extremely challenging in imperfect-information games. A new limited-lookahead search algorithm is the main breakthrough that enabled Pluribus to achieve superhuman multiplayer poker.Specifically, the search is an imperfect-information-game solve of a limited-lookahead subgame. At the leaves of that subgame, the AI considers five possible continuation strategies it and each opponent might adopt for the rest of the game. The number of possible continuation strategies is far larger, but the researchers found that their algorithm only needs to consider five continuation strategies per player at each leaf to compute a strong, balanced overall strategy.Pluribus also seeks to be unpredictable. For instance, betting would make sense if the AI held the best possible hand, but if the AI bets only when it has the best hand, opponents will quickly catch on. So Pluribus calculates how it would act with every possible hand it could hold and then computes a strategy balanced across all of those possibilities.Though poker is an incredibly complicated game, Pluribus made efficient use of computation. AIs that have achieved recent milestones in games have used large numbers of servers and/or farms of GPUs; Libratus used around 15 million core hours to develop its strategies and, during live game play, used 1,400 CPU cores. Pluribus computed its blueprint strategy in eight days using only 12,400 core hours and used just 28 cores during live play.Sandholm has founded two companies, Strategic Machine Inc. and Strategy Robot Inc., that have exclusively licensed strategic reasoning technologies developed in his Carnegie Mellon laboratory over the last 16 years. Strategic Machine applies the technologies to poker, gaming, business and medicine, while Strategy Robot applies them to defense and intelligence. Pluribus builds on and incorporates large parts of that technology and code. It also includes poker-specific code, written as a collaboration between Carnegie Mellon and Facebook for the current study, that will not be applied to defense applications. For any other type of usage, the parties have agreed that they can use the additional code as they wish.The National Science Foundation and the Army Research Office supported the Carnegie Mellon research. The Pittsburgh Supercomputing Center provided computing resources through a peer-reviewed XSEDE allocation. With funds provided by Facebook, Elias and Ferguson were each paid $2,000 for their participation in the experiment, and Ferguson received an extra $2,000 for outperforming Elias. The 13 pros who played against an individual Pluribus divided $50,000, depending on their performance.

NASA Selects Carnegie Mellon, Astrobotic To Build Lunar Robot

CMU's Red Whittaker Adds a Third Moon Project to His To-Do List

NASA has chosen Carnegie Mellon University and Astrobotic to build a rover that will land on the moon as early as 2021. The rover, called MoonRanger, will be about the size of a suitcase and weigh about 24 pounds on Earth. It will be fast and autonomous to accomplish long-range exploration missions within the span of a week. That's about the amount of time that a robot could operate on the moon before the onset of the lunar night and the accompanying deep freeze that would damage its electronics. "This capability will transform the exploration achievements that are possible by near term 'missions in a week,'" said William "Red" Whittaker, director of the Field Robotics Center, who will lead the development and construction of MoonRanger. The rover is designed to produce detailed 3D maps of the terrain and could be used to explore the polar regions for signs of ice or lunar pits for entrances to moon caves. MoonRanger is too small to carry a radio powerful enough to communicate directly with Earth. That means it must have autonomy for navigating, making data-gathering decisions and returning to its lander. Data and discoveries from MoonRanger's explorations will be relayed to Earth when it periodically returns within radio range of its lander. NASA's Lunar Surface and Instrumentation and Technology Payload (LSITP) program awarded a $5.6 million contract to Astrobotic and Carnegie Mellon to develop a flight-ready robot. It will be delivered to the moon on an upcoming mission through NASA's Commercial Lunar Payload Services program. This is the third moon research project for Whittaker that has been announced since early June. NASA already has approved $2 million for Whittaker to develop robotic technology necessary for investigating lunar pits. Such a mission likely wouldn't be launched until 2023. Carnegie Mellon also announced it will send a smaller, four-pound robot built by Whittaker's team to the moon in 2021 aboard a lander built by Astrobotic. "This latest NASA award to develop MoonRanger for a mission to the moon is another example of how Astrobotic is the world leader in lunar logistics," said John Thornton, CEO of Astrobotic, a CMU spinoff. "Our lander and rover capabilities are designed to deliver our customers to the moon and allow them to carry out meaningful, low-cost activities for science, exploration and commerce."