Year: 2018

The gender gap in technology is growing, and it’s not just for the reasons that you might expect. While access to opportunity – or rather the lack thereof – is often pointed to as the culprit for why there are so few women working in the U.S. technology sector, new research conducted by Accenture and Girls Who Code suggests it’s more complex than that – it also about holding on to their interest.

Last month, the National Science Foundation announced that it will fund COSMOS, a large-scale, outdoor testbed for a new generation of wireless technologies and applications that will eventually replace 4G. Covering one square mile in densely populated West Harlem just north of Columbia’s Morningside Heights campus, COSMOS is a high-bandwidth and low-latency network that, coupled with edge computing, gives researchers a platform to experiment with the data-intensive applications—in robotics, immersive virtual reality, and traffic safety—that future wireless networks will enable.

Columbia is one of three New York-area universities involved (with Rutgers and New York University being the other two). Columbia’s COSMOS proposal was overseen by principal investigator Gil Zussman (Electrical Engineering) who worked with a number of Columbia professors, including Henning Schulzrinne.

A researcher in applied networking who is also investigating an overall architecture for the Internet of Things (IoT), Schulzrinne has previous experience in setting up an experimental wireless network. In 2011, he oversaw the installation of WiMAX, an early 4G contender, on the roof of Mudd. WiMAX helped demonstrated the feasibility of doing wireless experiments on campus while also setting a precedent for the Computer Science Department to work with Columbia facilities, which ran the fiber, provided power, and installed the antennas.

In this interview, Schulzrinne discusses the benefits of COSMOS to researchers and students within and outside the department.

What is your role?

I have three separate roles. In the area of licensing and public policy, I did the spectrum license applications so the campus could use frequencies in the millimeter-wave radio band—not previously used for telecommunications—and I’ll work to ensure we don’t interfere with licensees who will someday be assigned those frequencies.

The way licensing is done will change under 5G. Instead of specifically requesting licenses for certain frequencies and then waiting for permission, or maybe an auction, as is done now, spectrum will be shared dynamically as needed, a more efficient way to use a limited resource. Part of COSMOS is to better understand how sharing of spectrum will work.

In the application area, I will be looking at both stationary and mobile IoT devices, putting mobile nodes on Columbia vehicles—buses and public safety and utility vehicles—to measure noise pollution, for example. I am also working with Dan Rubenstein on testing safety precautions with connected vehicles that use wireless connectivity and looking for ways to protect pedestrians and bicyclists.

And thirdly, for many years I have collaborated with researchers in Finland on a series of wireless spectrum projects, including mobile edge computing. These projects are funded by the NSF and the Academy of Finland through the WiFiUS program (Wireless Innovation between Finland and US). COSMOS gives us the chance to deploy and study mobile edge computing on a high-bandwidth, low-latency network.

Who will be able to access the test bed?

COSMOS is unique as an NSF project for building an infrastructure available to anyone, both on- and off-campus. In principle, anyone who has an email address at a US education institute can submit a proposal to use COSMOS for teaching and research.

While K-12 education plays an important role in this project—high school students, for example, might run experiments showing the propagation of radio waves—most educational interest and activity will likely be at the higher-education level, especially in networking and wireless classes, with both faculty and student researchers using the testbed to run experiments at a scale not possible in a lab.

What does COSMOS mean for Columbia researchers and students?

Columbia students, being physically close to the test bed, will have obvious advantages, like being able to easily enlist pedestrians or students for experiments on devices that are worn or carried.

I expect we’ll see many proposals coming out of the Computer Science Department in particular as we understand what becomes possible on these new networks where processing is done on edge servers rather than being sent up to cloud servers further away. Can we for instance control traffic lights to more efficiently move traffic along and increase safety of pedestrians and bicyclists? Can we use the network for augmented reality? Can public safety applications benefit from high-bandwidth video processing? Do the propagation characteristics force designers of network protocols to deal with short-lived connections with highly-variable transmission speed? The COSMOS testbed gives us a wireless infrastructure to find out.

Henning Schulzrinne is the Julian Clarence Levi Professor of Mathematical Methods and Computer Science at Columbia University. He is a researcher in applied networking and is particularly known for his contributions in developing the Session Initiation Protocol (SIP) and Real-Time Transport Protocol (RTP), the key protocols that enable Voice-over–IP (VoIP) and other multimedia applications. Active in public policy, he has twice served as Chief Technology Officer at the Federal Communications Committee (his most recent term ended October 2017). Currently he serves on the North American Numbering Council. Schulzrinne is a Fellow of the ACM and IEEE and a member of the Internet Hall of Fame. Among his awards, he has received the New York City Mayor’s Award for Excellence in Science and Technology, the VON Pioneer Award, TCCC service award, IEEE Internet Award, IEEE Region 1 William Terry Award for Lifetime Distinguished Service to IEEE, the UMass Computer Science Outstanding Alumni recognition.

Posted 05/14/2018

Daniel Hsu and his student Arushi Gupta show it is possible to build discrete choice models by estimating parameters from a small subset of options rather than having to analyze all possible options that may easily number in the thousands, or more. Using linear equations to estimate parameters in Hidden Markov chain choice models, the researchers were surprised to find they could estimate parameters from as few as two or three options. The results, theoretical for now, mean that in a world of choices, retailers and others can offer a small, meaningful set of well-selected items from which consumers are likely to find an acceptable choice even if their first choice is not available. For researchers, it means another tool to better model real-world behavior in ways not possible before.

Given several choices, what option will people choose? From the 1960s this simple question—of interest to urban planners, social scientists, and naturally, retailers—has been studied by economists and statisticians using discrete choice models, which statistically model the probabilities people will choose an option among a set of alternatives. (While an individual’s choice can’t be predicted, it is possible to study groups of people and infer patterns of behavior from sales, survey, and other data.)

In recent years, a type of discrete choice model called multinomial logit models has been commonly used. These models, easy to fit and understand, work by associating regression coefficients to each option based on behavior observed from real-world data. If ridership data shows people choose the subway 50% of the time and the bus 50% of the time, the model’s coefficients are tweaked to assign equal probability to each option.

On the whole, multinomial logit models perform well but fail to easily accommodate the introduction of new options that substitute for existing ones. If a second bus line is added and is similar to the existing one—same route, same frequency, same cost—except that the new bus line has articulated buses, a multinomial logit model would consider all three alternatives independently, splitting the proportion equally and assigning a probability of 0.33 to all three options.

“But that is not what happens,” says Daniel Hsu, a computer science professor and a member of the Data Science Institute who explores new algorithmic approaches to statistical problems. “People don’t care whether a bus is articulated or not. People just want to get to work.” Train riders especially don’t care about a new bus option because a bus is not a substitute for a train, and for this reason, the coefficient for trainer riders should not change.

The bus-train example is small, limited to three choices. In the real world, especially in retailing, choices are so numerous as to be overwhelming. People can’t be shown all options so retailers and others must offer a small set of choices from which people will find a substitute choice they are happy with even if their most preferred choice is not included.

To better model substitution behavior, researchers in Columbia’s Industrial Engineering and Operations Research (IEOR) Department—Jose Blanchet (now at Stanford University), Guillermo Gallego, and Vineet Goyal—two years ago proposed the use of Markov Chain models, which make predictions based on previous behaviors, or states. All options have probabilities as before, but the probability changes based on preceding options. What fraction of people will choose A when the previous states are B and C, or are C and D?  Removing one option, the most preferred one for example, changes the chain of probabilities, providing way for decide the next most preferred option among those remaining.

Switching from multinomial logit models to Markov chain choice models better captured substitution behavior but at the expense of much more complexity; previously, n possible options meant n parameters, but in the Markov chain models, n parameters just describes the initial probabilities; each removal of an option requires recalculating all possible combinations for a total of n squared parameters. Instead of 100 parameters, now it’s 10k parameters. Computers can handle this complexity; a consumer can’t and won’t.

The IEOR researchers showed it was possible to model substitution behavior by analyzing all possible options; left open was the possibility of doing so using less data, that is, some subset of the entire data set.

This was the starting point for Hsu and Arushi Gupta, a master’s student with an operations research background who had previously worked on estimating parameters for older discrete choice models; Gupta relished the opportunity to do the same for a more complex model.

“We looked at it as an algebraic puzzle,” says Hsu. “If you know two-thirds of people choose this option when these three are offered, how do you get there from the original Markov chain choice model? What are the parameters of the model that would give you this?”

Initially they set out to find an approximate solution but, changing tack, tried for the harder thing: getting a single exact solution. “Arushi discovered that all model parameters were related to the choice probabilities via linear equations, where the coefficients of the equations were given by yet other choice probabilities,” says Hsu.  “This is great because it means choice probabilities can be estimated from data. And this gives a way to potentially indirectly estimate all of the model parameters just by solving a system of equations.”

Says Gupta, “It is also quite lucky that it turned out to be just linear equations because even very big systems of linear equations are easy to solve on a computer. If the relationship had turned out to be other polynomial equations, then it would have been much more difficult.”

The final piece of the puzzle was to prove that the linear equations uniquely determined the parameters. “We crafted a new algebraic argument using the theory of a special class of matrices called M-matrices, which naturally arise in the study of Markov chains” says Hsu. “Our proof suggested that assortments as small as two and three item sets could yield linear equations that pin down the model parameters.”

Their results, detailed in Parameter identification in Markov chain choice models, showed a small amount of data suffices to pinpoint consumer choice behavior. The paper, which was presented at last year’s Conference on Algorithmic Learning Theory, is now published in the Proceedings of Machine Learning Research.

The researchers hope their results will lead to better ways of fitting choice models to data while helping understand the strengths and weaknesses of the models used to predict consumer choice behavior.

About the Researchers

Arushi Gupta, who received her bachelors at Columbia in 2016 in computer science and operations research, will earn a master’s degree in machine learning this May. In the fall, she starts her PhD in computer science at Princeton where she will study machine learning. In addition to Parameter identification in Markov chain choice models, she is coauthor of two additional papers, Do dark matter halos explain lensing peaks? and Non-Gaussian information from weak lensing data via deep learning.

Daniel Hsu is associate professor in the Computer Science Department and a member of the Data Science Institute, both at Columbia University, with research interests in algorithmic statistics, machine learning, and privacy. His work has produced the first computationally efficient algorithms for several statistical estimation tasks (including many involving latent variable models such as mixture models, hidden Markov models, and topic models), provided new algorithmic frameworks for solving interactive machine learning problems, and led to the creation of scalable tools for machine learning applications.

Before coming to Columbia in 2013,  Hsu he was a postdoc at Microsoft Research New England, and the Departments of Statistics at Rutgers University and the University of Pennsylvania. He holds a Ph.D. in Computer Science from UC San Diego, and a B.S. in Computer Science and Engineering from UC Berkeley. Hsu has been recognized with a Yahoo ACE Award (2014), selected as one of “AI’s 10 to Watch” in 2015 by IEEE Intelligent Systems, and received a 2016 Sloan Research Fellowship. Just last year, he was made a 2017 Kavli Fellow.

Posted 05/09/18
– Linda Crane

In a new approach to security, Sethumadhavan will work with a team of researchers, many from the Data Science Institute, to build security mechanisms into the well-defined interface between hardware and software.

In a paper presented this week at the Web Conference, authors Ana-Andreea Stoica, Christopher Riederer, and Augustin Chaintreau identify an algorithmic glass ceiling in social networks after analyzing effects of gender, homophily, and growth dynamics.

By imperceptibly changing, or perturbing, the shapes of fonts, Columbia researchers have invented a way to embed hidden information in ordinary text, without the existence of the secret message being perceived. The method, called FontCode, both creates font perturbations, mapping them to a bit string, and later decodes them to recover the message. To ensure robust decoding when font perturbations are obscured, researchers introduced redundancy using the 1700-year-old Chinese Remainder Theorem, and were able to demonstrate that a messages can be fully recovered even with a recognition failure rate of 25% (and theoretically even higher). FontCode works with all fonts and, unlike other text and document methods that hide embedded information, works with all document types, even maintaining the hidden information when the document is printed on paper or converted to another file type. While having obvious advantages for spies, FontCode has perhaps more practical application for companies wanting to prevent document tampering or protect copyrights, and for retailers and artists wanting to embed QR codes and other metadata without altering the look or layout of a document.

Compare these two lines of text. Can you see the difference? One carries a hidden message.

Each character in the second line differs slightly from its counterpart in the top line. (Compare the “d” in the two “looked” instances to see how the bottom instance has slightly thicker strokes.) And in these subtle differences, or perturbations, can be hidden a secret, encoded message without its existence being detected; the secret message is retained when printing a document or photograph or converting it to another file type.

These font perturbations are created and later recognized by FontCode, a text steganographic method created by three Columbia researchers—Chang Xiao, Cheng Zhang, and Changxi Zheng. Described in FontCode: Embedding Information in Text Documents using Glyph Perturbation, the FontCode method embeds text, metadata, a URL, or a digital signature into regular text or a photograph. It works with all common font families (Times Roman, Helvetica, Calibri) and is compatible with most word processing programs (Word, FrameMaker) as well as image-editing and drawing programs (Photoshop, Illustrator). Since each letter can be perturbed, the amount of information conveyed secretly is limited only by the length of the regular text.

“Changing any letter, punctuation mark, or symbol into a slightly different form allows you to change the meaning of the document,” says Chang Xiao, the paper’s lead author. “This hidden information, though not visible to humans, is machine-readable just as bar and QR codes are instantly readable by computers. However, unlike bar and QR codes, FontCode won’t mar the visual aesthetics of the printed material, and its presence can remain secret.”

FontCode is part of a broader research effort by Changxi Zheng, the paper’s senior author, to directly link the physical and digital worlds in a way that is both unobtrusive and not external to the object itself (unlike the highly visible QR and bar codes). Working with others in Columbia’s Computer Graphics Group, which he co-directs, Zheng is instead looking to use an aspect of the physical object to uniquely tag an object and encode information for digital devices to read. Recent projects from the lab include acoustic voxels and aircodes, which use an object’s acoustic properties for tagging and information embedding.

Rather than acoustic properties, FontCode encodes information using minute font perturbations—changing the stroke width, adjusting the height of ascenders and descenders, or tightening or loosening the curves in serifs and the bowls of letters like o, p, and b. Perturbations judged visually similar to the original letter are stored in a codebook. The numbered location in the codebook can be changed, providing FontCode with its own optional built-in encryption scheme.

FontCode is not the first technology to hide a message in text—programs exist to hide messages in PDF and Word files or to resize whitespace to denote a 0 or 1—but it is the first to be document-independent and to retain the secret information even when a document or an image with text (PNG, JPG) is printed or converted to another file type. This means a FrameMaker or Word file can be converted to PDF, or a JPEG can be converted to PNG, all without losing the secret information.

The embedding process

Someone using FontCode would supply a secret message and a carrier text document. FontCode converts the secret message to a bit string (ASCII or Unicode) and then into a sequence of integers. Each integer is assigned to a five-letter block in the regular text where the numbered locations of each letter sum to the integer.

Accurately recovering the message even with recognition errors

Recovering hidden messages is the reverse process. From a digital file or from a photograph taken with a smartphone, FontCode matches each perturbed letter to the original perturbation in the codebook to reconstruct the original message.

Matching is done using convolutional neural networks (CNNs). Recognizing vector-drawn fonts (such as those stored as PDFs or created with programs like Illustrator) is straightforward since shape and path definitions are computer-readable. However, it’s a different story for PNG, IMG, and other rasterized (or pixel) fonts, where lighting changes, differing camera perspectives, or noise or blurriness may mask a part of the letter and prevent an easy recognition.

While CNNs are trained to take into account such distortions, recognition errors will still occur, and a key challenge was ensuring a message could always be recovered in the face of such errors. Redundancy is one obvious way to recover lost information, but it doesn’t work well with text since redundant letters and symbols are easy to spot.

Instead, the researchers turned to the 1700-year-old Chinese Remainder Theorem, which identifies an unknown number from its remainder after it has been divided by several different divisors. The theorem has been used to reconstruct missing information in other domains; in FontCode, researchers use it to recover the original message even when not all letters are correctly recognized.

“Imagine having three unknown variables,” says Zheng. “With three linear equations, you should be able to solve for all three. If you increase the number of equations from three to five, you can solve the three unknowns as long as you know any three out of the five equations.”

Using the Chinese Remainder theory, the researchers demonstrated they could recover messages even when 25% of the letter perturbations were not recognized. Theoretically the error rate could go higher than 25%.

Obscurity not only means of security

Data hidden using FontCode can be extremely difficult to detect. Even if an attacker detects font changes between two texts—highly unlikely given the subtlety of the perturbations—it simply isn’t practical to scan every file going and coming within a company.

Furthermore, FontCode not only embeds but also optionally encrypts messages. This encryption is based on the order in which the perturbations occur in the codebook. Two people wanting to communicate through embedded documents would agree on a private key that specifies locations of perturbations in the codebook.

Encryption however is just a backup level of protection in case an attacker was able to detect the use of font changes to convey secret information. Given how hard it is to perceive those changes, detection is very difficult to do, making FontCode a very powerful technique to get data past existing defenses.

About the Researchers

Chang Xiao is a second-year PhD student at Columbia University working in the Computer Graphics Group and advised by Changxi Zheng. His research interests focus on the principles and applications of computer graphics, with a particular emphasis on computational design. He received his bachelor degree in the College of Computer Science of Zhejiang University.

Cheng Zhang is a first-year PhD student at UC Irvine working in the Interactive Graphics and Visualization Lab advised by Shuang Zhao. His research interests focus on the principles and applications of computer graphics, with a particular emphasis on physically based rendering. He received his master degree in Computer Science in Columbia University.

Changxi Zheng is an Associate Professor in Columbia’s Computer Science Department where he co-directs Columbia’s Computer Graphics Group, working on computational fabrication, computer graphics, acoustic and optical engineering, and scientific computing. He is also a member of the Data Science Institute and collaborates with other researchers across the university to better understand and processing audiovisual information. Zheng received his Ph.D. from Cornell University with the Best Dissertation Award and his B.S. from Shanghai Jiaotong University. He currently serves as an associated editor of ACM Transactions on Graphics. He was a Conference Chair for SCA in 2017, has won a NSF CAREER Award, and was named one of Forbes’ “30 under 30” in science and healthcare in 2013.

FontCode in the News

Helvetica Is Now An Encryption Device, via FastCompany

This algorithm can hide secret messages in regular-looking text, via Digital Trends

Clever Technique Can Hide Secret Messages in the Most Unassuming Text, via Popular Mechanics

Posted 04/20/2018
– Linda Crane

“An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol” (2006) was first paper to use traffic analysis to reverse-engineer an intentionally obscured network application. The other coauthor, Salman Baset, was Schulzrinne’s student at the time.

For their collaborative project “Acceleration of Deep Neural Networks via Heterogeneous Computing for Real-Time Processing of Neutrino and Particle-Trace Imagery,” Luca Carloni of the Computer Science Department and Georgia Karagiorgi of the Department of Physics were among the five teams awarded funding through the Research Initiatives in Science and Engineering (RISE) competition. Created in 2004, RISE is one of the largest internal research grant competitions within the University, and each year provides funds for interdisciplinary faculty teams from the basic sciences, engineering, and medicine to explore paradigm-shifting and high-risk ideas. This year 29 teams presented pre-proposals; of the nine teams asked to submit full proposals, five were selected to receiving funding in the amount of $80,000 per year for up to two years.

Carloni and Karagiorgi were awarded funding to develop machine learning techniques and to explore deep neural network implementations for “listening” to only the most important and rare physics signals while disregarding environmental noise and other accidental background signals. To do so, they will build a data processing system that can facilitate real-time processing and accurate classification of images streamed at rates on the order of terabytes per second. The primary target application is the future Deep Underground Neutrino Experiment (DUNE). This is a major international particle physics experiment that will be operational in the US for more than a decade, beginning in 2024, and will be continually streaming high-resolution 3D images of the active detector region at a total data rate exceeding 5 terabytes per second. The ability to process this data in real time and to efficiently identify and accurately classify interesting activity in the detector would enable the discovery of rare particle interactions that have never been observed before. This ability however requires the development of an advanced data processing system. This RISE project aims to develop a scalable heterogeneous computing system that employs machine learning for identification and classification of interesting activity in the data. The ultimate goal is to leverage recent advancements in computer science to render the DUNE experiment a powerfully sensitive instrument for fundamental particle physics discovery.

“We are in the midst of a Big Data revolution, wherein our capacity to generate data greatly exceeds our ability to analyze and make sense of everything,” says Karagiorgi. “In my own discipline of particle physics, we think that there is a great deal of information hidden in astroparticle data sets, such as those that will be recorded by the DUNE experiment. But we will need advanced methods and powerful systems to scan through those data sets and efficiently and accurately fish out the information we care about. This project requires interdisciplinary collaboration between physics and computer science, and time – afforded by RISE – to explore our early-stage ideas. If we can develop a system for only capturing the most important data, this is a project that can feasibly capture the attention of the National Science Foundation or the Department of Energy.”

The seed money provided by RISE allows teams to more fully develop high-risk, high-reward ideas to better pursue other avenues of funding. Since 2004, RISE has awarded $9.62 million to 72 projects. These 72 teams later secured more than $55.4 million from governments and private foundations: a 600% return on Columbia’s initial investment. These projects have additionally garnered more than 130 peer-reviewed publications and educated more than 130 postdoctoral scholars and graduate, undergraduate, and high school students.

Applications for the 2019 competition run from September to early-October 2018, with five to six awarded teams announced by spring 2019. Beginning in September, visit the RISE website to apply.

Posted 04/10/2018

The National Science Foundation (NSF) has awarded a $1.2M, four-year grant to computer science theorists Christos Papadimitriou and Mihalis Yannakakis for their proposal “Research in Algorithms and Complexity: Total Functions, Games, and the Brain.”

The following is an abstract of the work to be done under the grant.

The ubiquitous information environment around us, which has brought to the world unprecedented connectivity and availability of information, as well as newfound opportunities for individual expression, education, work, production and commerce, entertainment, and interpersonal communication, is the result of decades of research in all fields of computer science; furthermore, our best hope for confronting the many problems this new environment has brought to humanity (privacy and fairness, to mention only two) also lies in new computer science research. Research in theoretical computer science in particular over the past half century has been instrumental in bringing the benefits of Moore’s law to bear – through fundamental clever algorithms – and has made leaps in understanding the capabilities and limitations of computers and their software; in fact, it has articulated one of the most important problems in mathematics and all of science today: is P equal to NP? – that is to say, is exponential exhaustive search for a solution always avoidable?  Papadimitriou and Yannakakis have over the past four decades contributed much to this edifice of mathematical research in computer science, often in close collaboration; in addition, they have successfully applied the kind of incisive mindset known as “algorithmic thinking” to important problems in other sciences, such as economics and biology.

For this project, they will join efforts again in order to attack a new generation of problems: complexity questions in the fringe of the P vs. NP problem, a new genre of algorithms possessing a novel kind of robustness, research at the interface between computer science and economics related to income inequality and market efficiency, as well as research aiming at a better understanding of evolution, and of brain functions as basic as memory and as advanced as language. Papadimitriou and Yannakakis will train PhD and Masters students – and possibly undergraduates as well – on these research topics, and will disseminate the findings of this research to students and researchers, both in computer science and in other disciplines, as well as to the general public, through journal and conference publications, undergraduate and graduate courses, seminars, colloquia, as well as public talks and general interest articles.

In more detail, Papadimitriou and Yannakakis will work on improving our understanding of the complexity of total functions in the class TFNP and its subclasses, in view of recent research progress in that area; they will investigate the complexity of an as yet unexplored, from this point of view, Tarski-like fixed point theorem widely used in economics; they will revisit the approximability of the traveling salesperson problem; and will explore a new kind of algorithmic notion of robustness based on dense nets of algorithms.  In algorithmic game theory, Papadimitriou and Yannakakis will explore a new variant of the price of anarchy inspired by wealth inequality, as well as the complexity of market equilibria in markets with production and economies of scale; they will also research a new game theoretic solution concept based on the topology of dynamical systems; finally, they will pursue the proof of an intriguing new complexity-theoretic conjecture about the inaccessibility of Nash equilibria.  They will also continue their work in certain promising directions at the interface of game theory and learning theory.  In the life sciences, they will explore from the algorithmic point of view the problem of the true nature of mutations, and they will work on extending recent research with collaborators aiming at the computational understanding of how long-term memory, as well as syntax and language, are achieved in the human brain.

Posted 04/06/2018

“Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms” laid the foundation for how to use machine learning methods across a range of natural language processing tasks.

Award cites Yung’s innovative contributions to computer and network security. Yung (CS PhD ’88) is an adjunct and visiting faculty at Columbia and has advised several PhD students including Gödel Prize winner Matthew K. Franklin.

Peter Allen and Eugene Wu of Columbia’s Computer Science Department are each recipients of a Google Faculty Research Award. This highly competitive award (15% acceptance rate) recognizes and financially supports university faculty working on research in fields of interest to Google. The award amount, given as an unrestricted gift, is designed to support the cost of one graduate student for one year. The intent is for projects funded through this award to be made openly available to the research community.

Peter Allen: Visual-Tactile Integration for Reinforcement Learning of Robotic Grasping

To incorporate a visual-tactile learning component into a robotic grasping and manipulation system, Peter Allen will receive $71K. A Professor of Computer Science at Columbia, Allen heads the Columbia University Robotics Group.

In grasping objects, robots for the most part rely on visual feedback to locate an object and guide the grasping movements. But visual information by itself is not sufficient to achieve a stable grasp: it cannot measure how much force or pressure to apply and is of limited value when an object is partially occluded or hidden at the bottom of a gym bag. Humans rely as much or more on touch, easily grasping objects sight unseen and feeling an object to deduce its shape, apply the right amount of pressure and force, and detect when it begins to slip from grasp.

With funding provided by Google, Allen will add simulated rich tactile sensor data (both capacitive and piezoelectric) to robotic hand simulators, capturing and transforming low-level sensor data into high-level information useful for grasping and manipulation. This high-level information can then be used to build reinforcement learning (RL) algorithms that enable an agent to find stable grasps of complex objects using multi-fingered hands. The RL system can learn a grasping control policy and an ability to reason about 3D geometry from both raw depth and tactile sensory observations.

This project builds on previous work by Allen’s group on shape completion—also with a Google research grant—where an occluded object’s complete 3D shape is inferred by comparing it to hundreds of thousands of models contained within a data set. The shape completion work used machine learning with a convolutional neural network (CNN), with simulated 3D vision data on models of hundreds of thousands of views of everyday objects. This allowed the CNN to generalize a full 3D model from a single limited view. With this project, the CNN will now be trained on both visual and tactile information to produce more realistic simulation environments that can be used by Google and others (the project code and datasets will be open source) for more accurate robot grasping.

Eugene Wu: NeuroFlash: System to Inspect, Check, and Monitor Deep Neural Networks

For NeuroFlash, a system to explain, check, and monitor deep neural networks, Eugene Wu will receive $69K. An Assistant Professor of Computer Science at Columbia, Wu heads the WuLab research group and is a member of the Data Science Institute, where he co-chairs the Center for Data, Media and Society.

Deep neural networks, consisting of many layers of interacting neurons, are famously difficult to debug. Unlike traditional software programs, which are structured into modular functions that can be separately interpreted and debugged, deep neural networks are more akin to a single, massive block of code, often described as a black box, where logic is smeared throughout the behavior of thousands of neurons with no clear way of disentangling interactions among neurons. Without an ability to reason about how neural networks make decisions, it is not possible to understand if and how they can fail, for example, when used for self-driving cars or managing critical infrastructure.

To bring modularity to deep neural networks, NeuroFlash aims to identify functional logic components within the network. Using a method similar to MRI in medical diagnosis, which looks for brain neuron activations when humans perform specific tasks, NeuroFlash observes the behavior of neural network neurons to identify which ones are mimicking a user-provided high-level function (e.g., identify sentiment, detect vertical line, parse verb). To verify that the neurons are indeed following the function’s behavior and not spurious, NeuroFlash alters the neural network in systematic ways to examine and compare its behavior with the function.

The ability to attribute high-level logic to portions of a deep neural network forms the basis for being able to introduce “modules” into neural networks; test and debug these modules in isolation in order to ensure they work when deployed; and develop monitoring tools for machine learning pipelines.

Work on the project is driven by Thibault Sellam, Kevin Lin, Ian Huang, and Carl Vondrick and complements recent work from Google on model attribution, where neuron output is attributed to specific input features. With a focus on scalability, NeuroFlash generalizes this idea by attributing logical functions.

Wu will make all code and data open source, hosting it on Github for other researchers to access.

Posted 03/05/2018
– Linda Crane

A study published in Science describes how researchers created, from 86M genealogy profiles, population-scale family trees to reassess longevity and marriage and migration patterns. Yaniv Erlich is the study’s senior author.

For his proposal “Interactive Matcher Debugging via Adversarial Generation,” Eugene Wu has been awarded an Amazon Research Award. This unrestricted gift, open to institutions of higher learning in North America and Europe, is intended to support one or two graduate students or post-doc researchers doing research under the guidance of the faculty member receiving the award.

An Assistant Professor of Computer Science at Columbia, Wu heads the WuLab research group and is a member of the Data Science Institute, where he co-chairs the Center for Data, Media and Society.

Wu will use the award to fund research that will extend existing techniques for entity matching, a data cleaning task that locates duplicate data entries referencing the same real-world entity (to learn, for example, that “M. S. Smith” and “Mike S. Smith” refer to the same person).

“Finding these duplicate records is crucial for integrating different data sources, and current methods rely on machine learning,” says Wu. “The problem is that machine learning is not perfect and it is hard to even anticipate where it is matching incorrectly. We are very pleased that Amazon has selected to fund this project where we will work toward two goals: help users identify cases likely to result in matching errors, and identify realistic data examples to use to improve the machine learning model.”

Online retailers and services collect their data from a huge number of different data sources that may use different spellings or naming conventions and provide different images or descriptions for the same item. Amazon might have hundreds of vendors listing and selling iPhones or iPhone-related products. If all of this data is uploaded to Amazon without being matched, customers might see 100 product pages for “iPhone,” “iPhone 6X Large,” “IPhONE 6 Best,” or even worse, a product search might come up empty if the search string doesn’t exactly match the product name as it is assigned by the vendor. Entity matching helps prevent these types of problems but entity matching is a deeply challenging problem.

Entity matching is a classification problem, with ensemble trees often used to label entity pairs as matching or non-matching. Errors in classification are a perennial problem, but if users understand why such errors occur, they can adjust the classification process to reduce errors.

Much of Wu’s research, and the focus of WuLab, has centered on creating interactive visualizations that make it easier for users to spot anomalous patterns and other problems while also providing explanations of why certain problems occur. Wu will do the same for entity matching by developing new algorithms and software components that, once inserted into existing entity-matching pipelines, will automatically generate high-level, easy-to-understand explanations so developers can readily understand what matching errors exist.

Once errors have been identified, the second direction of the research is to address the error. Wu will do so by generating training samples to feed back into the machine learning model and ultimately improve its accuracy. As with all classification tasks, entity matching requires huge amounts of training data, and it is often necessary to synthetically create additional data to train a classification model. One such data-generation technique is adversarial generation, which creates new data by taking a supplied, real-world string of values and changing one or two values to produce a new data string similar to real-world ones.

Widely used for images, adversarial generation has drawbacks for text since perturbing a single value often produces non-semantic text samples that wouldn’t actually occur in the real world; such data, inserted into the training set, could contribute to matching errors. Here, Wu proposes constraints that will consider the entire data record (not just individual string values) when perturbing transformations, thereby ensuring synthetic data is less arbitrary, more representative of real-world cases, and in the case of text, more semantically meaningful.

As part of the award, which totals $80K with an additional $20K in Amazon Web Services (AWS) Cloud Credits, Wu and his research group will meet and collaborate with Amazon research groups. The resulting paper will be published and the code written for the project will be made open source for other research groups.

Posted 02/01/2018
– Linda Crane

The Eighth Symposium on Educational Advances in Artificial Intelligence 2018 (EAAI-18) has selected Ansaf Salleb-Aouissi as one of the EAAI 2018 New and Future AI Educators. Funded through a grant from the National Science Foundation, the award covers registration and travel, lodging, and participation in EAAI-18, where researchers and educators meet to discuss pedagogical issues related to teaching and using AI in education. The symposium, which is co-located with the 32st Association for the Advancement of Artificial Intelligence (AAAI-18) Conference, will be held in New Orleans February 3 and 4.

A Lecturer-in-Discipline at Columbia since 2015, Salleb-Aouissi teaches courses in the fundamentals of artificial intelligence both in front of Columbia’s classrooms and as part of the online graduate-level MicroMasters program in Artificial Intelligence, a popular edX course with over 160,000 enrollments.

Salleb-Aouissi’s research interests lie in machine learning and data science. She has done research on frequent patterns mining, rule learning, and action recommendation and has worked on data science projects including geographic information systems and machine learning for the power grid. Her current research interest includes crowd sourcing, medical informatics and educational data mining.

Salleb-Aouissi received her PhD in computer science from
University of Orleans (France) in 2003

Posted 01/31/18