Year: 2017

As curiosity and enthusiasm grow around both augmented reality and virtual reality, Feiner and other panelists discuss what is new in these rapidly maturing fields and what most excites them.

In this PRI interview, Vishal Misra, who helped shape India’s strong net neutrality regulations, uses analogies to explain net neutrality while discussing how the diverging paths taken by the US and India will affect innovation.

Computer Graphics and User Interfaces Lab is one of two academic labs selected to participate in Verizon’s newly-opened Open Innovation lab, which co-locates startups and academics to promote new concepts and use cases for pre-commercial 5G.

Monday she took questions on how she overcame hating math to being a CS professor at Columbia, a children’s book author, and a quantitative researcher at IEX. Her students got into the act also.

Henning Schulzrinne, former CTO of the FCC, answers questions about the likely repeal of the Open Internet Report and Order, and how it removes essentially all regulatory oversight from broadband Internet access.

Last Friday, with less than a week remaining before the FCC’s expected repeal of the Open Internet Rules, a panel of four experts convened before an audience in Davis Auditorium to discuss what such a repeal is likely to mean for the Internet. Though all four spoke from different perspectives—three were technology experts and one an Internet consumer advocate and lawyer—all expressed concerns about the repeal. (Though proponents of the repeal had been invited, none were able to attend.)

The panel was moderated by Ethan Katz-Bassett, a professor of electrical engineering at Columbia, who is an expert on Internet services and content delivery, and by Brittney Gallagher, Digital Culture Correspondent for Digital Village, the oldest running radio program in Los Angeles that covers the Internet.

The discussion started with a rundown of the three bright lines that cannot be crossed under current rules—no throttling, no blocking, no paid prioritization. It is these rules (as well as other general-conduct rules) that, according to Sarah Morris ensure that Comcast doesn’t prioritize its streaming platform over Netflix or that a company can’t pay AT&T to favor its traffic over the traffic of a competitor.

While much attention has been focused on how the order will remove protections that prevent internet service providers (ISPs) like Comcast and Verizon from restricting or prioritizing traffic, Henning Schulzrinne, whose second term as CTO at the FCC just ended in October, pointed out the order also removes the FCC’s power to regulate Internet service, handing over this responsibility to the FTC. Given that the FTC has no authority to issue blanket rules to ban blocking or prevent other discriminatory practices, the US will effectively have no Internet regulation at all, a situation Schulzrinne calls unprecedented.

Another topic discussed was the lack of competition among the last-mile providers, that is, the ISPs that control the cables that run from the Internet’s main transit cables to smaller, neighborhood-scale cables that go to each individual house. Expensive as it is to lay these cables, no one was advocating for replicating last-mile cables, but under current conditions, the company that builds the last-mile cable controls access to customers.

Without competition and soon without any regulation, there is nothing to prevent AT&T, Verizon, or Comcast from monetizing their access to customers. In fact, in a market economy, there is every incentive to exploit one’s stranglehold on consumer eyeballs to extract access fees from content providers. While large rich companies like Amazon, Apple, Facebook, Microsoft, and Alphabet (Google)—the “frightful five”—can afford to pay for access to customers, many other companies cannot. It’s especially difficult for fledging startups and for not-for-profit sites and services.

For Vishal Misra, the solution is to switch from the “infrastructure-based competition” the US has currently to a model where service is based on competition between ISPs, with all ISPs having access to a common last mile everywhere and competing for customers by providing better services. It is a solution, however, that requires telecommunications oversight.

The potential downsides for innovation and new services of the FCC’s expected action was another of the topics covered. While FCC chairman Ajit Pai has argued that repeal of net neutrality is necessary for investments and to make the internet better through faster internet speeds, Peter Boothe said his analysis of M-Lab measurements over time suggests that Internet performance in the US improved at least as fast—and probably faster—since February 2015 (when the current regulations went into effect) than it was improving before the regulations.

The panel discussion in its entirety can be seen here.

Posted 12/11/2017
– Linda Crane

Amir Baradaran, an art-based researcher in Steven Feiner’s Computer Graphics and User Interfaces Lab (CGUI), has been awarded two grants totaling $220K to create two augmented reality installations, Facing the Cloud + (RE)storing Po{AI}try. Both will be created at Columbia within the CGUI lab.

A winner of the Canada Council for the Arts’ New Chapter Grant (for $120K) and a recipient of the Knight Arts Challenge (for $100K) from the prestigious John S. and James L. Knight Foundation, Baradaran has long been incorporating augmented reality (AR), artificial intelligence (AI), and other technologies into performance art pieces. Even while these technologies were in their early stages, Baradaran saw the potential in AR as a platform for creating immersive, participatory art, where audiences can augment or change an artist’s work.

AR’s implications for storytelling are explored in Facing the Cloud, where audience participants will don headsets to enter into a large-scale immersive installation. Through movements and gestures, they can interact and change the content of what the artist initially created.

“For over 100 years, cinema has conditioned audiences to passively observe a story told in linear time, with every scene tightly scripted and framed by the director and sometimes with input from the actors and other collaborators,” says Baradaran. “AR and AI fundamentally change this equation by allowing the audience to become a co-creator with the artist.”

How AR changes the relationship between art and artist doesn’t necessarily enter into the thinking of the computer scientists and programmers focused on technical aspects of AR. Says Feiner, a pioneer in developing AR technology, “Having Amir here in the lab provides a chance for cross-pollination with artists and others who bring different perspectives. We become better engineers when we’re more cognizant of how these technologies will change the way people interact with the world.”

Facing the Cloud was funded in part by the Knight Arts Challenge matching grant, which according to Victoria Rogers, VP of Arts at the Knight Foundation, “funds the best ideas for engaging and enriching Miami through the arts.” Facing the Cloud will be exhibited in late Spring 2018 in collaboration with the City of Miami’s Little Haiti Cultural Center and with the support of the Smithsonian Affiliate History Miami Museum and the Perez Art Museum Miami (PAMM).

The second project, (RE)storing Po{AI}try, is a large-scale public art project that examines the creative process of code-writing while critically exposing the notion of the presumptive neutrality of code. “Like poetry, code has syntax, symbols, punctuation, spacing, and words,” says Baradaran. “By conceptualizing the language of the machine—that is, code—as Po{AI}try, we can unsettle the disciplinary boundaries between the technologists and artists. Additionally, it helps us question the objective nature of programming as a neutral language. Like poets writing verse, engineers bring their own assumptions, value systems, and lived experiences when they write code.”

(RE)storing Po{AI}try is being funded by the Canada Council for the Arts’ New Chapter project, which was chosen for Canada’s 150th Anniversary Celebrations. Honoring the tradition of oral storytelling and its role in preserving diverse histories of Canada’s First Nations, Baradaran will collaborate with the Awkasasne Mohawk Community in Cornwall, Ontario. Canada 
Po{AI}try will be installed at Montreal’s Place des Arts Complex in Fall 2018.

Both Facing the Cloud and (RE)storing Po{AI}try a critical story about the evolving role of augmented reality and artificial intelligence technology. “If AR is to become a new medium for artistic creation, it will require a set of visual and conceptual vocabularies along with technical toolsets for artists to design and implement within this new field,” says Baradaran. “Just as painters have tools like brushes and pigments to express ideas, artists working in AR/AI need theirs.”  As the art-based researcher within Feiner’s lab, Baradaran is working directly with engineers and others to provide a common frame of reference and set of functionalities that artists and engineers can use to communicate and co-create.

“It’s really exciting to see the creativity of the arts in collaboration with the creativity of computer science here at Columbia,” says David K Park, Dean of Strategic Initiatives at Columbia University. “The excitement isn’t just about how these fields are working together to push, inform and illuminate the boundaries of virtual reality, AR, and AI as well as other technologies, but how the collaboration creates a richer conversation about how technology is shaping society and just as importantly how society is shaping technologies that we use. I know Amir’s project will engage a broad range of disciplines beyond just the arts and computer science and am excited to see what additional collaborations his work will spark here at Columbia.”

Baradaran is seeking further faculty and student collaborations in 2018. “We are looking for folks interested in mobile application development, Unity/game development, robotics, machine learning and natural language processing,” says Baradaran. He is reaching across campus to form partnerships with faculty members and their students in 2D-3D design, storytelling, journalism, architecture, film, animation, theater performance, acting, and sound production, as well as more theoretical fields such as (art) history, policy, law, and communications.

Those interested interested in learning more can contact amir.baradaran@columbia.edu.

Posted 12/08/17

Modeled on the Aviation Safety Reporting System, such an agency would investigate major cyberattacks and “near misses,” publishing results so others could better understand—and avoid—the threats. Reporting would be voluntary, anonymous, and nonpunitive.

Columbia Spectator gives Adam Cannon high marks for his humor, direct interaction with students, easygoing demeanor, and, most importantly, for making computer science make sense.

Peter Allen and Matei Ciocarlie were among the robotics researchers making presentations. Held October 19, the event was attended by academics and executives from venture capital firms and technology companies.

Paper published in eLife describes a method for using $1000 DNA sequencers to quickly and accurately identify cells lines from DNA. Lead author Yaniv Erlich sees a huge potential to improve cell-authentication in cancer research.

This year’s IEEE International Symposium on Mixed and Augmented Reality (ISMAR) recognized Steven Feiner with the Career Impact Award for “significant impact over his career to the ISMAR community.” ISMAR is the premier international conference for research in mixed and augmented reality.

A Professor of Computer Science at Columbia University, Feiner has been working in the field of augmented reality for more than 25 years and published some of the earliest scholarly papers on the subject.

At Columbia he directs the Computer Graphics and User Interfaces Lab, which in 1996 created the first outdoor mobile augmented reality system using a see-through display, paving the way for current smartphone outdoor augmented reality applications; the paper describing the system received the Early Innovator Award from the International Symposium on Wearable Computers (ISWC) just this year. His lab also pioneered experimental applications of augmented reality in tourism, journalism, maintenance, construction, and other fields.

Beyond augmented reality, Feiner’s research interests extend to human-computer interaction, 3D user interfaces, virtual environments, knowledge-based design of graphics and multimedia, mobile and wearable computing, computer games, healthcare, information visualization, and he co-directs the Columbia Vision and Graphics Center.

Feiner is coauthor of three textbooks, two editions of the well-known textbook Computer Graphics: Principles and Practice (the two editions were written twenty years apart and with different authors) as well as Introduction to Computer Graphics.

Among his awards, Feiner is a recipient of the IEEE VGTC 2014 Virtual Reality Career Award, and he was elected to the SIGCHI Academy (2011). Together with his students, he has won the ACM UIST 2010 Lasting Impact Award for early work on supporting 2D windows in augmented reality, and best paper awards at ACM UIST, ACM CHI, ACM VRST, IEEE ISMAR, and IEEE 3DUI.

Throughout the years, he has served as general chair (or cochair) and program chair (or cochair) for the premier research conferences in augmented reality and virtual reality: both ISMR and IEEE ISAR (the forerunners of IEEE ISMAR), IEEE VR, and ACM VRST, along with the leading research conference on innovations in human-computer interfaces, ACM UIST.

Feiner did his undergraduate degree at Brown in 1973 and received his PhD in Computer Science also from Brown in 1987

Posted 11/28/17

Writing to the Department of Homeland Security, 54 computer scientists and academic researchers criticized a proposed plan to use AI methods to screen immigrants and visa applicants. In this interview, Bellovin specifies some technology concerns.

Henning Schulzrinne, the Julian Clarence Levi Professor of Mathematical Methods and Computer Science at Columbia University, has been appointed to the North American Numbering Council (NANC), a federal committee advising the Federal Communications Committee (FCC) on the efficient and impartial administration of telephone numbering resources in North America. Among other responsibilities, the NANC recommends the creation of new area codes when the supply of numbers diminishes due to demand, and it advises on policy and technical issues involving numbering resources. On the Committee, he hopes to accelerate the transition to a more Internet-based and capable system for assigning and managing telephone numbers, adding the ability to prevent the spoofing of caller ID and to port numbers nationwide.

Schulzrinne, who last month completed his second term as Chief Technology Officer at the FCC, has worked with the FCC in a number of positions over the past seven years, helping shape public policy and providing guidance on technology and engineering issues. Schulzrinne played a major role in the FCC’s decision to require mobile carriers to enable customers to contact 911 using text messages. He is active also in technology solutions to limit phone spam (“robocalls”) and enable relay services for people who are deaf or hard of hearing.

As a researcher in applied networking, Schulzrinne 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. Each is now an Internet standard and together VoIP and SIP have had an immense impact on telecommunications, both by greatly reducing consumer costs and by providing a flexible alternative to the traditional and expensive public-switched telephone network.

Last year Schulzrinne received the 2016 IEEE Internet Award for “formative contributions to the design and standardization of Internet multimedia protocols and applications.” Previously he was named an ACM Fellow (2015), receiving also in 2015 an Outstanding Service Award by the Internet Technical Committee (ITC), of which he was the founding chair. In 2013, Schulzrinne was inducted into the Internet Hall of Fame. Other notable awards include the New York City Mayor’s Award for Excellence in Science and Technology and the VON Pioneer Award. Active in serving the broader technology community, Schulzrinne is a past member of the Board of Governors of the IEEE Communications Society and a former vice chair of ACM SIGCOMM. He has served on the editorial board of several key publications, chaired important conferences, and published more than 250 journal and conference papers and more than 86 Internet Requests for Comment. He was recently appointed to the Intelligent Infrastructure Task Force of the Computing Community Consortium.

Schulzrinne continues to work on VoIP and other multimedia and networking applications and is currently investigating an overall architecture for the Internet of Things, including new user-friendly means of authentication, and how to protect the electric grid against cyberattacks.

Schulzrinne received his undergraduate degree in economics and electrical engineering from the Darmstadt University of Technology, Germany, his MSEE degree as a Fulbright scholar from the University of Cincinnati, Ohio, and his PhD from the University of Massachusetts in Amherst, Massachusetts.

Posted 11/20/2017

Interdisciplinary collaborations are needed today because the hard problems—in medicine, environmental science, biology, security and privacy, and software engineering—are interdisciplinary. Too complex to fit within one or even two disciplines, they require the collective efforts of those with different types of expertise and different perspectives.

Computer scientists are in high demand as collaborators, and not just because the computer is indispensable in virtually all fields today. The computational, or algorithmic, approach—where a task is systematically decomposed into its component parts—is itself a powerful problem-solving technique that transfers across disciplines. New techniques in machine learning, natural language processing, robotics, computer graphics, visualization, and augmented reality make it possible to present and think about information in ways not possible before.

The benefits flow both ways. Collaborations offer computer scientists the chance to work on new problems they might not otherwise consider. In some cases, collaborations can change the direction of their own research.

“The most successful collaborations revolve around problems that interest everyone involved,” says Julia Hirschberg, chair of Columbia’s Computer Science Department. She adds that collaborations often require time and negotiating. “It might take a while to find out what’s interesting to you, what’s interesting to them, but in the end you figure out how to make the collaboration relevant to both of you.”

In higher education, more efforts are being put into promoting faculty-faculty collaborations across departments while also preparing students to reach across disciplinary boundaries. At Columbia, the Data Science Institute (DSI) brings together researchers from 11 of Columbia’s 20 schools—including the School of International and Public Affairs, the Columbia Medical Center, the Columbia Law School—to work on problems in smart cities, new media, health analytics, financial analytics, and cybersecurity. Fully 80% of Columbia’s computer science faculty are DSI members.

Other interdisciplinary efforts are supported by provost awards intended to encourage collaborations among schools and departments.

The Computer Science Department plays its role also, whether it’s individuals informally connecting people together or through more structured programs like the NSF-funded IGERT Data to Solutions program, which trains PhD students on taking a multi-disciplinary approach for integrating data collections. As part of its mission, IGERT sponsors talks where researchers outside the department present interesting problems from their own fields.

In spring 2015, one of those speakers was Pamela Smith, a professor specializing in the history of science and early modern European history, with particular attention to historical crafts and techniques. Her talk was on the Making and Knowing Project, which seeks to replicate 16th-century methods for constructing pigments, colored metals, coins, jewelry, guns, and decorative objects.

After the talk, Hirschberg suggested Smith contact Steven Feiner, director of the Computer Graphics and User Interfaces Lab.

Updating the reading experience

For the Making and Knowing Project, Smith and her students recreate historical techniques by following recipes contained in a one-of-a-kind, 340-page, 16^th-century French manuscript. (The original, BnF Ms. Fr. 640, is housed in the Bibliothèque Nationale in Paris. Selected entries of the present, ongoing English translation are here.) It’s trial and error; the recipes have no precise measurements and often skip certain details so it can take several iterations to get a recipe right. Since even early attempts that “fail” can be highly informative, Smith has her students document and record every step and any objects that are produced.

The result is a substantial collection of artifacts, including photos, videos, texts, translations, and objects recreated using 16^th century technology. The challenge for Smith is making this content easily available to others.

Steven Feiner works in the decidedly 21st century areas of augmented reality, virtual reality, and 3D user interfaces. Together he and Smith are collaborating on how to use the technologies from Feiner’s lab to effectively present historical content in a way that is dynamic and convincing to people without access to the original manuscript.

Their joint solution is to make virtual representations of the content viewable in 3D space and, when available, in context of physical copies of artifacts from Smith’s lab, all seen through a smart device with the appropriate software. The content—texts, images, videos, and 3D simulations of objects—is naturally organized around the recipes.

The devices used by Feiner’s lab range from ordinary smartphones and tablets through devices specifically designed to support augmented reality, in which virtual content can be experienced as if it were physically present in the real world. These higher-end devices include smartphones with Google’s Tango technology and the Microsoft HoloLens stereoscopic headworn computer, both of which have sensors that are used to model the surrounding world. To view the combination of virtual and physical content, a user looks through a smart device, viewing the physical world through the device camera in the case of a smartphone or tablet. Software installed on the device blends the virtual content with the user’s physical environment, taking into account the current position and the orientation of the device’s location in space, giving the impression that the virtual content actually exists in the real environment. If the virtual content includes a 3D object, the user can move relative to the object to see it from any perspective. Virtual content can be attached to physical objects, such as a printed photo or even to Smith’s lab—either the physical room or a virtual model that the researchers are creating.

The two labs are working together to convert Smith’s artifacts into digital content that can be linked together and arranged in 3D in ways that elucidate their interrelationships. Both sides benefit as learning occurs in the two labs: Smith and her students gain new tools and the digital proficiency to use them in a way to better study their own field; Feiner and his students get the chance to work on a problem they might never have previously considered and to better understand how to present and interact with information effectively in 3D—one of their lab’s themes. As the project progresses, Feiner and his students will take what they are learning from working with Smith’s students to further improve the tools and make them more general-purpose so others can adapt them for completely different projects.

More information about the collaboration can be found on the Making and Knowing Project’s Digital page while an extensive photo repository on the project’s Flicker account shows lab reconstruction experiments. Latest project and class updates are posted to Twitter.

It’s just one collaboration in Feiner’s lab; in another, the new media artist Amir Baradaran is incorporating augmented reality technology into two art pieces, one exploring the parallels between code and poetry, and the other looking at the implications to authorship when audience members are able to immerse themselves into an artwork and affect the content. Such issues don’t necessarily enter into the thinking of the computer scientists focused on technical aspects of augmented reality. Says Feiner, “Having Baradaran here in the lab is a chance for us to work with others who bring different perspectives. It makes us better engineers if we’re more cognizant of how these technologies will change the way people interact with the world.”

This project in particular points to another reason for computer scientists to seek collaborations: With technology so ingrained in modern life, others from outside computer science, especially those focused on aesthetic, ethical, and communication issues, can contribute to making technology more human-oriented and easier to use in everyday life.

A robotic grasping system to assist people with severe upper extremity disabilities

Robotics by nature is interdisciplinary, requiring expertise in computer science and electrical and mechanical engineering. Peter Allen, director of Columbia’s Robotics Group, is often approached for collaborations by people who come to him for technical solutions; over the years, he has worked on a broad range of projects in different disciplines, from art and archaeology—where he helped construct 3D models of archeological sites from 2D images—to biology and medicine, where he works with colleagues at the medical school to develop surgical robots.

One particularly fruitful collaboration came after a colleague encouraged Allen to attend a talk in which Sanjay Joshi (Professor of Mechanical and Aerospace Engineering at UC, Davis) spoke about a noninvasive brain-muscle-computer interface he could use to control two dimensions of space.

That struck a bell for Allen. In robotic grasping, one difficulty is constraining choices. Jointed digits can fold and bend in almost unlimited number of positions to grasp an object, meaning an almost unfathomable number of micro decisions: Which fingers to use, how to bend and position each one, where on an object should digits grasp? After much research into simplifying robotic motions, Allen was eventually able to break the task down into two motions—two parameters—that could be combined to achieve 80% of grasps.

Joshi could also control two parameters—two dimensions of space. Out of this overlap, and working also with Joel Stein of Columbia’s Medical Center, who specializes in physical medicine and rehabilitation, the three are now developing a robotic grasping system to assist people with severe upper extremity disabilities to pick up and manipulate objects. (A video of the system is here.)

The system interprets and acts on an intent to grasp. Intent is signaled by the user activating a small muscle (posterior auricular) behind the ear. (This muscle, which most people can be trained to control, responds to nerves that come directly from the brain stem, not from spine nerves; even individuals with the most severe spinal cord paralysis can still access the posterior auricular.)

A noninvasive sensor (for sEMG, or surface electromyography) placed behind a patient’s ear detects activation of the posterior auricular, and from there the robotic system carries out a series of automated tasks, culminating in selecting the most appropriate grasp from a collection of preplanned grasps to pick up the desired object.

The whole purpose of the project is to restore the ability to carry out simple daily tasks to people with the most limited motor control function, including those with tetraplegia, multiple sclerosis, stroke, amyotrophic lateral sclerosis (ALS).

“Interdisciplinary work is so important for the future of robotics, especially for human-robot interfaces,” says Allen. “If robots are capable and ubiquitous, humans have to figure out how to interact with them, whether through voice or gestures or brain interfaces—it’s an extremely complex issue. But the rewards can be very high. It’s exciting to see your technology in real clinical use where it can impact and help others.”

In this case, the complexity requires the collective efforts of researchers with expertise in signal processing, robotic grasping, and rehabilitative medicine.

Each collaboration is different, of course, but common to all successful collaborations is a shared purpose in solving a problem while at the same time having the challenge of extending knowledge in one’s own field. In the best cases, the benefits extend far beyond those working in the collaboration.

Posted 11/16/2017
– Linda Crane

“NEZHA: Efficient Domain-Independent Differential Testing” won a 2^nd place prize at the 14th Cyber Security Awareness Week (CSAW). Put on by NYU, CSAW is world’s largest student-run cybersecurity event, featuring competitions, workshops, and industry events.

Researchers create an algorithm that computes a reflector shape that boosts signals for desired indoor areas while weakening them elsewhere. The reflector can be 3D-printed for $35. Limiting signal coverage also helps prevent nearby cyberattacks.

The symposium, to be held in Rio de Janeiro, November 8-10, examines the enormous promise of AI technologies as well as the risk that uneven access to AI may amplify digital inequalities across the world.

The Early Innovator Award conferred at this year’s  International Symposium on Wearable Computers (ISWC) recognizes “A touring machine: Prototyping 3D mobile augmented reality systems for exploring the urban environment” (1997) as the paper from the first ISWC (1997) having the most impact in the intervening 20 years.

The paper presented the first outdoor augmented reality system using GPS position
tracking with a see-through head-worn display. Before the era of smartphones,
ubiquitous GPS, and Wi-Fi, the Touring Machine, which included a backpack stuffed
with electronics, let users navigate Columbia’s campus, overlaying names of buildings
and academic departments on buildings viewed through the user’s head-worn display,
and allowing users to select a department to explore its website on a hand-held display
wirelessly connected to the internet.

Cited 1257 times as of November 2017, the paper was authored by Professor Steven Feiner, Blair MacIntyre (PhD ’99, and now Professor in the School of Interactive Computing, Georgia Tech), Tobias Höllerer (PhD ’04 and now Professor of CS, UC Santa Barbara), and Tony Webster (now Lecturer in Finance, SEAS and Clinical Associate Professor of Real Estate, NYU). Both MacIntyre and Höllerer were Feiner’s PhD students at the time of the paper.

Posted 11/02/17

The paper, widely covered in the press, describes an automatic method for error-checking thousands to millions of neurons in a deep-learning neural network. Authors are Kexin Pei, Yinzhi Cao (Lehigh), Junfeng Yang, Suman Jana.

Developed by Kexin Pei, Yinzhi Cao (Lehigh), Junfeng Yang, and Suman Jana, DeepXplore error-checks thousands to millions of neurons in deep learning neural networks. In tests, DeepXplore found thousands of bugs missed by previous methods.

To uniquely identify and encode information in printed objects, Columbia researchers Dingzeyu Li, Avinash S. Nair, Shree K. Nayar, and Changxi Zheng have invented a process that embeds carefully designed air pockets, or AirCode tags, just below the surface of an object. By manipulating the size and configuration of these air pockets, the researchers cause light to scatter below the object surface in a distinctive profile they can exploit to encode information. Information encoded using this method allows 3D-fabricated objects to be tracked, linked to online content, tagged with metadata, and embedded with copyright or licensing information. Under an object’s surface, AirCode tags are invisible to human eyes but easily readable using off-the-shelf digital cameras and projectors.

The AirCode system has several advantages over existing tagging methods, including the highly visible barcodes, QR codes, and RFID circuits: AirCode tags can be generated during the 3D printing process, removing the need for post-processing steps to apply tags. Being built into a printed object, the tags cannot be removed, either inadvertently or intentionally; nor do they obscure any part of the object or detract from its visual appearance. Invisibility of the tags also means that the presence of information can remain hidden.

“With the increasing popularity of 3D printing, it’s more important than ever to personalize and identify objects,” says Changxi Zheng, who helped develop the method. “We were motivated to find an easy, unobtrusive way to link digital information to physical objects. Among their many uses, AirCode tags provide a way for artists to authenticate their work and for companies to protect their branded products.”

One additional use for AirCode tags is robotic grasping. By encoding both an object’s 3D model and its orientation into an AirCode tag, a robot would just need to read the tag rather than rely on visual or other sensors to locate the graspable part of an object (such as the handle of a mug), which might be occluded depending on the object’s orientation.

AirCode tags, which work with existing 3D printers and with almost every 3D printing material, are easy to incorporate into 3D object fabrication. A user would install the AirCode software and supply a bitstring of the information to be encoded. From this bitstring, AirCode software automatically generates air pockets of the right size and configuration to encode the supplied information, inserting the air pockets at the precise depth to be invisible but still readable using a conventional camera-projector setup.

How the AirCode system works

The AirCode system takes advantage of the scattering of light that occurs when light penetrates an object. Subsurface scattering in 3D materials, which is not normally noticeable to people, will be different depending on whether the light hits an air pocket or hits solid material.

Computational imaging techniques are able to differentiate reflective light from scattered light and decompose a photo into two separate components: a direct component produced by reflected light, and a global component produced from the scattered light waves that first penetrate an object. It’s this global component that AirCode tags manipulate to encode information.

AirCode represents the first use of subsurface light scattering to relay information, and the paper detailing the method, AirCode: Unobtrusive Physical Tags for Digital Fabrication, was named Best Paper at this year’s User Interface Software and Technology (UIST), the premier forum for innovations in Human-Computer Interfaces.

Other innovations are algorithmic, falling into three main steps:

Analyzing the density and optical properties of a material. Most plastic 3D printer materials exhibit strong subsurface scattering, which will be different for each printing material and will thus affect the ideal depth, size, and geometry of an AirCode structure. For each printing material, the researchers analyze the optical properties to model how light penetrates the surface and its interactions with air pockets.

“The technical difficulty here was to create a physics-based model that can predict the light scattering properties of 3D printed materials especially when air pockets are present inside of the materials,” says PhD student Dingzeyu Li, a coauthor on the paper. “It’s only by doing these analyses were we able to determine the size and depth of individual air pockets.”

Analyzing the optical properties of a material is done once with results stored in a database.

Constructing the AirCode tag for a given material. Like QR codes, AirCode tags are made up of cells arranged on a grid, with each cell representing either a 1 (air-filled) or a 0 (filled with printing material), according to the user-supplied bitstring. Circular-shaped markers, easily detected by computer vision algorithms, help orient the tag and locate different cell regions.

Unlike QR codes, which are clearly visible with sharp distinctions between white and black, AirCode tags are often noisy and blurred, with many levels of gray. To overcome these problems, the researchers insert predefined bits to serve as training data for calibrating in real time the threshold for classifying cells as 0s or 1s.

Detecting and decoding the AirCode tag. To read the tag, a projector shines light on the object (multiple tags might be used to ensure the projector easily finds a tag) and a camera captures images of the object. A computer vision algorithm previously created by coauthor Shree Nayar and adapted for AirCode tags separates each image into its direct component and global component, making the AirCode tag clearly visible so it can be decoded.

While the AirCode system has certain limitations—it requires materials to be homogeneous and semitransparent (though most 3D printer materials fit this description) and the tags become unreadable when covered by opaque paint—tagging printed objects during fabrication has substantial benefits in cost, aesthetics, and function.

Posted 10/24/2017
– Linda Crane

Interviewed by Columbia Technology Ventures (CTV), Allen discusses his recent work on surgical robots and how incorporating big data, machine learning, and computer vision is contributing to smarter robots able to cope with the unexpected.

To end his talk “Can we store all of world’s data on a pickup truck,” Erlich makes bold prediction that DNA storage could be cheaper than magnetic storage within a decade.

With the national average slightly below 20%, Columbia’s relatively high percentage of women CS majors in the 2016-2017 academic year ranks it among the top US universities in attracting women to computer science.

“Travel in Large-Scale Head-Worn VR” teleports users through virtual environments by allowing them to determine orientation in advance. Another project from Feiner’s lab, “Remote Collaboration in AR and VR Using Virtual Replicas” won a third place finish.

The paper describes the aircode technique to physically tag 3D-printed objects with information using carefully designed air pockets inserted beneath an object’s surface. UIST, a top venue for HCI, will be held October 22-25.

The claim aroused concerns about genomic privacy. But in a paper posted to BioRxiv, Erlich matched people to their genomes using easily accessible demographic data, showing Venter’s warning about serious privacy risks to be overstated.

A faculty affiliate of the CS Department, Venkatasubramanian synthesizes concepts from economics, political philosophy, game theory, statistical mechanics, and systems engineering into a quantitative theory for maximizing fairness in free-market capitalism.

“The Role of Conversation Context for Sarcasm Detection in Online Interactions” considers the larger context of online conversations to accurately detect sarcasm while also identifying what triggered a sarcastic reply.

For decades, devicemakers, engineers, and others have been able to count on a new generation of chips coming to market, each more powerful than the previous—all courtesy of shrinking transistors that allow engineers to fit more on a chip. This is the famous Moore’s law. While a boon for technical innovation and a catalyst for entire new industries, the reliability of always having more powerful chips has had the opposite effect on chip architecture, deterring rather than spurring innovation. Why bother designing a whole new chip architecture when in two years a better chip using the traditional mold will be out? But as the expense vastly increases for each increase in transistor density, Moore’s law—more an objective than an actual law—is beginning to bump against physical limits, creating an opportunity and incentive for engineering researchers to again focus time and effort on new varieties of chips. In this interview, Luca Carloni discusses where he sees chip design to be heading, how his lab hopes to contribute to that redesign, and the changes he is making in the courses he teaches to train students for this new reality.

Jensen Huang, CEO of Nvidia, said earlier this summer that Moore’s law is dead. Is it?

Luca Carloni: You won’t ever get me to say that Moore’s law is dead—that’s something I first heard 20 years ago when still a student. Many years passed and every two years or so we have seen the arrival of a new generation of semiconductor technology. Sometime this year Intel is expected to ship advanced processors based on the company’s 10nm process technology.

What is over, however, is the economics aspect of Moore’s Law. Doubling the density of transistors can’t be done anymore without vastly increasing costs. Every jump in technology requires building a new fab [semiconductor fabrication facility], which can cost $5-10B. When there’s a ready market to buy up the newest chips—as there was when people first started buying laptops and smart phones—investing in a new fab makes sense. But it is not always easy to find a new product, or a new market, that brings billions of new chip sales. Still, I believe that these markets will continue to be discovered. There is a need for faster and better computers for autonomous cars, cloud computing, security, cognitive computing, robotics, etc.

We can’t get there just by shrinking transistors into tighter spaces and increasing their densities on chip because we can no longer dissipate the resulting power densities and heat. Now we have this fundamental tradeoff between two opposing forces: more computational performance versus higher power/energy dissipation.

How do you see this tradeoff being resolved?

By building specialized chips for different applications. One type of chip is not going to work for all applications. The system that’s best for the smart phone is going to be different than what’s best for the autonomous car, or cloud servers, or IoT [Internet-of-Things] devices. The performance-energy tradeoff is going to be different in each case.

Because of these conflicting demands, we are already seeing a migration from a homogeneous multicore architecture to heterogeneous SoCs [systems-on-chip] that contain specialized hardware. This consists of accelerators that perform a single function or algorithm much faster and more efficiently than software. Here the processor becomes just another component within a system of components. And the SoC becomes a more heterogeneous multicore architecture as it integrates many different components. Indeed, I expect that no single SoC architecture will dominate all markets. The set of heterogeneous SoCs in production in any given year will be itself heterogeneous!

We’re also seeing the rise of the field-programmable gate array, or FPGA, which can be programmed for different purposes. You’ll get better performance from an FPGA than from software and an FPGA is a much cheaper proposition that building a chip from scratch, but between an FPGA and a specialized chip there are orders of magnitude difference in energy efficiency and performance. So the demand for specialized chips will remain strong, but we need to design them faster and more cheaply while considering the target application: What algorithms or software will it run? Can it be done in parallel? How much energy-efficiency is required? There is no one right way to build a system anymore.

Heterogeneity is the emerging solution but heterogeneity increases the complexity of designing and programming chips. What you decide to put on a chip is just the beginning of a very complex engineering effort that spans both hardware and software.

What does this heterogeneity mean for computer engineering?

We need a new way of thinking about engineering chips. For too long, chip architects have been mostly on the sidelines as new faster chips based on traditional architectures continued to arrive every two years or so. But now there’s this chance to go back to design, to be creative again and come up with innovative architectures. It’s time for a renaissance in computer engineering, if you will, to think about things differently, to move, for example, from a processor-centric perspective to a system-centric perspective, where it’s necessary to think about how a change in one component affects the other components on the chip. Any change must benefit the whole system.

For handling complexity, we need to raise the level of abstraction in hardware design, similar to how it’s done in software. Instead of thinking in terms of bytes and clock cycles, we should think in terms of the behavior we’re aiming for and in terms of the corresponding data structures and tasks. As we do so, we need to reevaluate continuously the benefits and costs of doing things in hardware instead of software and vice versa. Which is the best design? It depends. Do you care more about speed? Or do you care more about power dissipation?

But it’s just not one thing. We need to think in terms of the entire infrastructure, from design and programming to fabrication. You think you have a better chip design, but can you program it and validate it—in conjunction with a system of heterogeneous components—before committing to the expensive manufacturing stage? This system-level design approach motivates the research in our lab here at Columbia.

We have developed the idea of Embedded Scalable Platforms, or ESP, that addresses the challenges of SoC design by combining a new template architecture and a companion system-level design methodology. With ESP, we are now able to realize complete prototypes of heterogeneous SoCs on FPGAs very rapidly. These prototypes have a very high degree of complexity for an academic laboratory.

To support the ESP methodology, we are developing some innovative tools. We have a new emulator for multicore architectures, which we presented at a conference last February—and we released the software as well—so we can describe a new machine and then run this emulator software on top of an existing multicore computer to see how the new architecture behaves when running complex applications. While this type of emulation has been done before—and across the different instruction sets such as Intel’s x86 and the ARM ISA—we have increased scalability so we can emulate a multicore machine on top of another multicore machine. And we made it possible to take advantage of the parallelism of the machines of today.

How have these changes affected how you teach chip architecture?

In my class on System-on-Chip Platforms, students learn to design complex hardware-software systems at a high level of abstraction. This means to design hardware with description languages that are closer to software, thus enabling faster full-system simulation and more effective optimization with high-level synthesis tools. During the first half of the semester students learn how to design accelerators with these methods. They also learn how to integrate heterogeneous components—accelerators and processors—into a given SoC, how to evaluate trade-off decisions in a multi-objective optimization space, and how to design components that are reusable across different systems and product generations.

In the second half of the semester, the students do a project that is structured as a design contest. They compete in teams to design an accelerator specialized for a certain function—one year it might be a computer vision algorithm, another year a machine learning task. They are given some vanilla code to start. They must optimize the code in different ways to design three competitive versions of the accelerator and write software to integrate them in the system and show that each runs correctly in our emulator. High-level synthesis allows each team to quickly evaluate many alternative design decisions. For example, if the algorithm requires that a multiplication is performed on two arrays of many elements, the students can decide to instance more multipliers to do many multiplications in parallel or, instead, to use fewer multipliers by performing these multiplications in time sharing. Basically, they experiment with the trade-offs of “computing in space” versus “computing in time.”

The main goal for each team is to obtain three distinct designs of the accelerator that correspond to three distinct trade-off points in terms of performance versus area occupation. The quality of each final implementation is evaluated in the context of the work done by the entire class. Throughout the one-month duration of the project, a live Pareto-efficiency plot reporting the current position of the three best design implementations for each team in the bi-objective design space is made available on the course webpage. This allows students to continuously assess their own performance with respect to the rest of the class.

Do you foresee further changes to your class?

Yes, always. Course content will never be static when the need for innovation is so great.

Last year we started complementing the competitive aspect with a collaborative aspect. We now partition the student teams in subsets. The teams in each subset compete on designing a given component but are now also asked to pair up their three designs with those designed by the teams in other subsets to get the final system. This further promotes the goal of designing components that are reusable under different scenarios and under different constraints. This is collaborative engineering, and increasingly how engineering is done in the real world today.

Every year, we change up the class by adding something new—different algorithms to implement, for example. Students love this, and in the process they learn one of the most beautiful ideas of engineering: evaluating situational complexity from multiple viewpoints and balancing multiple tradeoffs. It’s exactly what’s needed today in chip design if we are to sustain the level of innovation that we have seen over the past few decades.

Posted September 6, 2017

Last week in Stockholm, Columbia researchers presented three papers at Interspeech, the largest and most comprehensive conference on the science and technology of spoken language processing. A fourth paper was presented at the *SEM, a conference on lexical and computational semantics held August 3-4 in Vancouver, Canada. High-level descriptions of each of the four papers are given in the following summaries and interviews with lead authors.

Hybrid Acoustic-Lexical Deep Learning Approach for Deception Detection
Gideon Mendels, Sarah Ita Levitan, Kai-Zhan Lee, and Julia Hirschberg

Interview with lead author Gideon Mendels.

What was the motivation for the work?

The deception project is an ongoing effort led by Sarah Ita Levitan under the supervision of Professor Julia Hirschberg.

In this work, our motivation was to see if we could use deep learning to improve our results since previous experiments were mostly based on traditional machine learning methods.

How prevalent is deep learning becoming for speech-related research? How is it changing speech research?

Deep learning is very popular these days and in fact has been for the past few years. In speech recognition, researchers originally substituted traditional machine learning models with deep learning models and gained impressive improvements. While these systems had deep learning components they were still mostly based on the traditional architecture.

Recent developments allowed researchers to design deep learning end-to-end systems that completely replace traditional methods while still obtaining state-of-the-art results. In other subfields of speech research, deep learning has not been as successful, whether it’s because simpler models suffice or the lack of big datasets.

In your view, will deep learning replace traditional machine learning approaches?

I see deep learning as just another tool in the researcher’s toolbox. The choice of algorithm requires an understanding of the underlying problem and constraints. In many cases, traditional machine learning approaches are better, faster, and easier to train. I doubt traditional methods would be completely replaced by deep learning.

You investigated four deep learning approaches to detecting deception in speech. How did you decide on these particular approaches?

We chose these methods based on previous work on deception detection, similar tasks such as emotion detection, and running thousands of experiments to develop intuition for what works.

Nonetheless there’s a lot more to be done! There are different model architectures to explore and different ways to arrange the data. I’m mostly excited about application of end-to-end models that learn to extract useful information directly from the recording without any feature engineering.

Your best performing model was a hybrid approach that combined two models. Is this what you would have expected?

Our original experiments focused on detecting deception either from lexical features (the choice of words) or acoustic features from the speaker’s voice. While both proved valuable for detecting deception we were interested to see whether they complement or overlap. By combining the two we got a better result compared to each one individually. I can’t say this was a huge surprise since humans, when trying to detect lies, utilize as many signals as possible: voice, words, body language, etc. Overall our best model achieved a score of 63.9% [F1] which is about 7.5% better than previous work on the same dataset.

Is this hybrid model adaptable to identifying other speech features other than deception?

Definitely. Now that our work is published we’re excited to see how other researchers will use it for other tasks. The hybrid model could be especially useful in tasks such as emotion detection and intent classification.

Utterance Selection for Optimizing Intelligibility of TTS Voices Trained on ASR Data
Erica Cooper, Xinyue Wang, Alison Chang, Yocheved Levitan, Julia Hirschberg

Creating a text-to-speech (TTS), or synthetic, voice—such as those used by Siri, Alexa, Microsoft’s Cortana—is a major undertaking that typically requires many hours of recorded speech, preferably made in a soundproof room by having a professional speaker reading in a prescribed fashion. It is time-consuming, labor-intensive, expensive, and almost wholly reserved for English, Spanish, German, Mandarin, Japanese, and few other languages; it is almost never used for the other 6900 or so languages in the world, leaving these languages without the resources required for building speech interfaces.

Repurposing existing, or “found,” speech from TV or radio broadcasts, audio books, or scraped from websites, may provide a less expensive alternative. In a process called parametric synthesis, many different voices are aggregated to create an entirely new one, with speaking characteristics averaged across all utterances. Columbia researchers see it as a possible way to address the lack of resources common to most languages.

Found speech utterances however have their own challenges. They contain noise, and people have varying speaking rates, pitches, and levels of articulation, some of which may hinder intelligibility. While low articulation, somewhat fast speaking rates, and low variation in pitch are known to aid naturalness, it wasn’t clear these same characteristics would aid intelligibility. More articulation and slower speaking rates might actually make voices easier to understand.

“We wanted to discover what would produce a nice, clean voice that was easy to understand,” says Erica Cooper, the paper’s lead author. “If we could identify utterances that were introducing noise or hindering intelligibility in some way, we could filter out those utterances and work only with good ones. We wanted also to understand whether a principled approach to utterance selection meant we could work with less data.”

Though the goal is to create voices for low-resource languages, the researchers focused on English initially to identify the best filtering techniques. Using the MACROPHONE corpus, an 83-hour collection of short utterances taken from telephone-based dialog systems, the researchers removed noise, including transcribed utterances labeled as noise as well as clipped utterances (where the waveform was abruptly cut off), and spelled out words.

Using the open-source HTS Toolkit, the researchers created 34 voices from utterances spoken by adult female speakers. Each voice was selected according to different acoustic and prosodic characteristics, and drawn from different subsets of the corpus; some adult female voices were from the first 10 hours of the corpus, and some from 2- and 4-hour subsets.

Each voice was used to synthesize the same 10 sentences, and each set of sentences was evaluated by five Mechanical Turk workers who transcribed the words as they were spoken. Word error rates associated with a voice were used to judge intelligibility.

Workers could listen to only one question set to ensure they were not transcribing words from memory; the task thus required a relatively high number of workers. The rate at which workers signed up quickly become a bottleneck, adding weeks to the project and prompting the researchers to consider using automatic speech recognition (ASR) as a proxy for human evaluations. ASR evaluations would speed things, but would they agree with human evaluations when assessing intelligibility?

Extending the scope of the experiment, the researchers employed three off-the-shelf ASR APIs—Google Cloud Speech, wit.ai (owned by Facebook), IBM’s Watson—to study using ASR to evaluate intelligibility. ASR did in fact correlate closely with Mechanical Turk workers; for all voices humans rated better than baseline, all three ASRs did the same, showing the future promise of ASR in assessing intelligibility of spoken speech. There was one notable caveat. Sending the same audio clip multiple times to one of the APIs (wit.ai) did not necessarily return the same transcription, so variability might be expected in some ASR systems. But then again, humans were themselves even more variable in evaluating intelligibility. (Google and Watson showed no variability, always returning the same transcription.)

The most intelligible voices for both humans and the ASR methods were those with a faster speaking rate, a low level of articulation, and a middle variation in pitch. (For naturalness, the researchers had previously found the best features to be also a low-level of articulation but a low, not middle, mean pitch.) Removing transcriptions labeled as noise produced noticeable improvement, but removing clipped utterances or spelled out words did not.

More training data wasn’t necessarily better if the data was chosen in a principled way. Using the first 10-hour subset of female adult speech as a baseline with 67.7% accuracy, some two-hour subsets with carefully chosen utterances did better, validating the hypothesis that better voices can be trained by identifying the best training utterances in a noisy corpus, even with less training data.

Crowdsourcing Universal Part-of-Speech Tags for Code Switching
Victor Soto, Julia Hirschberg

Almost all bilingual and multilingual people code-switch, that is, they naturally switch between languages when talking and writing. People code-switch for many reasons; one language might better convey the intended meaning, a speaker might lack technical vocabulary in one language, or a speaker wants to match a listener’s speech. Worldwide, code-switchers are thought to outnumber those who speak a single language. Even in the US, famously monolingual, it is estimated that 40M people code-switch between English and Spanish.

People code-switch, but speech and natural language interfaces for the most part do not; their underlying statistical models are almost always trained for a single language, forcing people to adjust their speaking style and refrain from code-switching. To eventually enable more natural and seamless natural language interfaces so people can freely switch between languages, Columbia researchers Victor Soto and Julia Hirschberg have begun building natural language models specifically for code-switching in English and Spanish settings; the overall goal, however, is for a workable paradigm for other language pairs.

Simply combining two monolingual models was not seen as a viable solution. “Code-switching follows certain patterns and syntactic rules,” says Soto, lead author of the paper. “These rules can’t be understood from monolingual settings. Inserting code-switching intelligence into a natural language understanding system—which is our eventual aim—requires that we start with a bilingual corpus annotated with high-quality labels.”

The necessary labels include part-of-speech (POS) tags that define a word’s function within a sentence (verb, noun, adjective, and other categories). Manually annotating a corpus is time-consuming and expensive, so Soto and Hirschberg want to build an automatic POS tagger. The first step in this process is collecting training data.

The researchers start with an existing English-Spanish code-switching corpus, the Miami Bangor Corpus, compiled from 35 hours of conversational speech containing 242,475 words, two-thirds in English and one third in Spanish. While the corpus had the required size, the existing part-of-speech tags were often inaccurate or ambiguous, having been applied automatically using software that did not consider the multilingual context.

The researchers decided to redo the annotations, using tags from the Universal Part-of-Speech tag set, which would make it easier to map to tags used by other languages.

Fully half the corpus (56%) consisted of words always labeled with the same part of speech; these words were labeled automatically. Frequent words that were hard to annotate (slightly less than 2% of the corpus) were tagged by a computational linguist (Soto).

For the remaining 42% of the corpus, the researchers turned to crowdsourcing, a method used successfully in monolingual settings with untrained Mechanical Turk and Crowdflower workers. In this case, tagging tasks are structured in a way that does not require knowing grammar and linguistic rules. Workers simply answer a single question or are led through a series of prompts that converge to a single tag; in both cases, instructions and examples assist workers in choosing a tag.

To adapt this crowdsourcing approach to a bilingual setting, the Columbia researchers required workers to be bilingual, and they wrote separate prompts for the Spanish and English portions of the corpus, taking into account syntactic properties of each language (such as prompting for the infinitival verb form in Spanish, or the gerund form in English, to disambiguate between verb and nouns, among others).

Each crowdsourced word was assigned three intermediate judgments—two from crowdsourcing and one carried over from the Miami Bangor corpus—with majority vote to decide the tag. The voting considered judgments only from workers who demonstrated a tagging accuracy of at least 85% when compared to a hidden test set of tags. In 95-99% of the time, at least two votes agreed.

Over the entire corpus, Soto and Hirschberg estimate an accuracy of between 92% and 94%, close to what a trained linguist can do.

With an accurately labeled corpus, the researchers’ next step is building an automatic part-of-speech tagging model for code-switching between English and Spanish.

Earlier in August, Columbia researchers presented Comparing Approaches for Automatic Question Identification at *SEM 2017: The Sixth Joint Conference on Lexical and Computational Semantics, held in Vancouver, Canada. The authors are Angel Maredia, Kara Schechtman, Sarah Ita Levitan, and Julia Hirschberg.

Interview with lead author Angel Maredia.

Why is it important to automatically identify questions?

Many applications follow a question-and-answer format where people have the flexibility to speak naturally and choose their own words but within the confines of the topic set up by the question. Often it’s often important to know how much speech goes into answering a particular question or when there is a change in topic. Our goal with this project was to develop automatic approaches to organizing and analyzing a large corpus of spontaneous speech at the topic level. 

Your paper describes labeling two deceptive speech corpora, the Columbia X-Cultural Deception (CXD) corpus and the Columbia-SRI-Colorado (CSC) corpus. Why did you choose these two corpora to label?

Both corpora are part of our larger effort in identifying deception in speech, something we’ve been working at here at Columbia for a number of years. The CXD corpus contains 122 hours of speech in the form of dialogs between subject pairs who played a lying game with each other. They took turns playing the role of interviewer and interviewee, and asked each other questions from a 24-item biographical questionnaire that they filled out, lying for a random half of the questions. Given this setup, we wanted to identify which question a given interviewee was answering.

With 122 hours of speech, it’s just not possible to do this manually—as we had done with the smaller CSC corpus. We needed an automatic approach, and for this we compared three different techniques for question identification to see which one was best for identifying which question a given interviewee was answering.

While we needed topic labels for the CXD corpus, the CSC corpus was chosen because it had similar topical distinctions that were hand-labeled, which we could use to test and verify that the approach that worked on CXD corpus was viable.

How do the three methods you tried—ROUGE, word embeddings, document embeddings—differ from one another?

We compared these methods because they capture similarity of language in different ways. ROUGE—which is a software package for evaluating automatic summarization, was selected to do comparison with n-grams. We selected the word embeddings and document embeddings approaches because they accounted for semantic similarity. The word embeddings approach used the Word2Vec model, which represents words as vectors, and words that were similar semantically had higher cosine similarity between the vectors, and the document embeddings approach used the Doc2Vec model, which we hoped would capture additional context.

The word embedding approach had the highest accuracy. Are these the results you expected?

It makes sense that the word embeddings approach would have higher accuracy because it also accounts for true negatives, and in any given interviewer turn, there are more true negatives than true positives.

While we weren’t surprised that word embeddings was the best method, we were nonetheless amazed at how well it worked. It matched very closely with the manually applied labels.

Your work was on labeling deceptive speech corpora. Would you expect similar results on other types of corpora?

Yes. This work applies at any type of speech that has a conversational structure. We happened to use deceptive speech corpora, but the method is unsupervised and should generalize well to other domains.

Posted August 31, 2017

– Linda Crane

Interactive Robogami, an MIT CSAIL project, lets anyone design a robot in minutes, and 3D-print and assemble it in as little as four hours. A key feature is controlling a robot’s gait and geometry.

The paper, by three Columbia researchers, describes CLKSCREW, a new class of fault attacks that exploit the security-obliviousness of energy management mechanisms. The attack does not require physical access to devices or fault injection equipment.

In a paper published in PNAS, they call for a holistic approach to data science, one that weaves statistics and computer science into a larger framework while considering context and responsibilities when using data. Subscription.

The Winner’s Curse—where newly discovered genetic effects are consistently overestimated and fail consistently to replicate in subsequent studies—afflicts every genome-wide association study (GWAS). This failure to replicate calls into doubt the credibility of these studies that otherwise show promise in establishing the genetic basis for both quantitative (height, obesity) and disease traits. But how much of the failure to replicate is due to the Winner’s Curse? Are other factors involved? To find out, two Columbia University researchers analyzed 332 GWAS quantitative papers to de-bias the effects of the Winner’s Curse across a broad set of traits. Their first finding? Fully 70% of GWAS did not report enough information to independently verify replication rates. Digging deeper into papers that did fully report, the researchers identified two main issues preventing replication—use of populations with different ancestry, and not reporting a cohort size for each variant. Papers without these problems did in fact replicate at expected rates. Reporting deficiencies, not the paradigm of GWAS, are to blame for the failure to replicate. The researchers’ method and the code to implement the method are made available to other researchers in the field.

Large-scale genome-wide association studies (GWAS) scan the genomes of hundreds of thousands of individuals for genetic variations common to an entire population, allowing scientists to associate traits (height, risk of diabetes) to specific genetic variations, specifically single nucleotide polymorphisms, or SNPs (pronounced “snips”).

It’s a statistical approach that looks across a very large sampling of human genomes to discover what SNPs occur more frequently in individuals exhibiting the same traits, to see for instance, what SNPs are common in tall people or in those who are obese. That GWAS cost a fraction of full DNA sequencing have made GWAS especially attractive.

But are GWAS reliable? Associations found in a GWAS often do not replicate in subsequent studies assembled to corroborate such findings. GWAS are susceptible to the Winner’s Curse, where initial discoveries are too optimistic and fail to replicate more than expected. High failure rates in GWAS call into question the credibility of the GWAS paradigm.

Itsik Pe’er, a computational geneticist and computer scientist at Columbia University, explains the term Winner’s Curse this way: “The millions of variants in the genome are all going through a statistical test. This is analogous to athletes competing in a time trial. The winner is very likely to be better than the average participant, but also likely to have been lucky, having had a particularly good day at the race. The time set by the winner therefore overestimates how good the winner is. Similarly, the statistical score of the winning variants overestimates the effect a winner has on the examined trait.”

A single GWAS can uncover thousands of SNPs; without the resources to investigate them all, scientists select the most promising SNPs based on how they perform against a threshold. Causal SNPs may exceed the threshold, but due to noise, so will a number of noncausal SNPs. The lower the threshold, the more SNPs of both types.

The problems surrounding GWAS have long been known, and individual GWAS papers have attempted to correct for the Winner’s Curse to achieve the true rate of replication—but only for the studied traits. To look broadly across GWAS to de-bias the effect of the Winner’s Curse no matter the trait, Pe’er and graduate student Cameron Palmer, who is part of The Integrated Program in Cellular, Molecular and Biomedical Studies, manually examined the 332 quantitative GWAS papers within the NHGRI-EBI GWAS Catalog (a collection of peer-reviewed GWAS papers published in scientific journals) that (1) found a significant SNP-trait association and (2) where there was an attempt to replicate it. (A quantitative trait is one measured on a scale. Height and BMI are quantitative traits; disease-risk traits studied in case controls are not. The researchers did not at this time look at case-control studies, which have previously been evaluated in terms of the Winner’s Curse.)

De-biasing the effect of the Winner’s Curse across GWAS required going through all 332 papers and obtaining certain information, including the sample size (the number of individual genomes studied), along with the replication threshold and SNP frequency needed to calculate bias in effect sizes.

In 70% of the papers, Pe’er and Palmer did not find this information. The omissions for the most part were inadvertent—Palmer was surprised to find seven papers he previously worked on to be missing needed information—nor was reporting this information required by peer-reviewed publication venues.

This left 100 papers. By applying a Winner’s Curse correction previously used in disease studies, Pe’er and Palmer came fifteen-fold closer to the true rate of replication, a vast improvement but still a statistically significant failure to replicate.

Digging deeper into each these 100 papers, they identified two main issues: replication studies sometimes used populations with a different ancestry from the original, and they failed to report sample sizes on the basis of the individual variant.

Ancestry is especially important in a GWAS because, for populations in different continents, variation in correlation between SNPs makes a study in one population less relevant to the other.

Not reporting a sample size for each variant was often a function of the way replication studies are pulled together from several existing studies, each one focused on one or more of the variants of the original GWAS. The sample sizes of these studies may all be different, perhaps 50,000 in one, 20,000 in another; rather than reporting separate sample sizes, the studies often reported only a single sample size, which was usually the total number of individuals across all studies (in this case, 70,000).

Binning papers by problem, the two researchers ended up with one bin of 39 papers that did use populations with the same ancestry and did report sample sizes for each variant. And in this bin, replication rates matched expectation.

“When we looked at papers with correct ancestries and that reported cohort sizes per variant, the replication rate improved substantially,” says Palmer, “and this improvement was seen in all 39 papers, so the effect is strong and it is broad. The deviation we saw before in the 100 papers is being fixed by filtering out papers that exhibit problems. So we can say that if a replicated study uses the same ancestry of the original study, and if it reports individual cohort sizes for each variant, no matter the trait, GWAS do replicate at expected rates.”

The methodology employed by Pe’er and Palmer is detailed in Statistical Correction of the Winner’s Curse Explains Replication Variability in Quantitative Trait Genome-Wide Association Studies, which provides the first systematic, broad-based evidence that quantitative trait association studies as a whole are replicable at expected rates.

The fault for failing to replicate lies with reporting deficiencies, not with the paradigm of GWAS.

While this news should be reassuring to those who see in GWAS a promising, low-cost way to link genetic variation to traits, especially those associated with complex diseases, the study does point to community-wide deficiencies in reporting, something that is not easily resolved without a central standards board. One concrete suggestion is for the NHGRI-EBI GWAS Catalog to upload only papers meeting certain minimum reporting criteria. Individual journals could also require minimum reporting standards.

Individual authors may have the most incentive to report all pertinent information, for it is only by doing so is it possible to claim replication does occur.

The code for the correction tool is available on Github.

– Linda Crane
Posted 08/01/2017

Eitan Grinspun and Changxi Zheng worked with MIT researchers to create InstantCAD, a plugin providing real-time feedback on how design changes affect performance. A paper describing InstantCAD will be presented at SIGGRAPH in August.

When 108,000 students enrolled in her inaugural online edX artificial intelligence course, Ansaf Salleb-Aouissi and two assistants divided up among them the task of handling student questions. There was frustration on both sides; students sometimes had to wait up to 48 hours for a reply, and Salleb-Aouissi and her small team found themselves answering the same questions multiple times, many of them logistical in nature (“what materials can I use for the final”), leaving less time for those related directly to course content.

Even after putting together a FAQ, the volume of questions remained high.

With $20K in funding provided through a Provost Award for Hybrid Learning, enough to fund at least two graduate students, Salleb-Aouissi will now begin investigating building a chatbot to automatically answer student questions. Collaborating closely with Columbia Video Network (CVN), which produces Columbia Engineering edX courses, the goal will be a chatbot intelligent enough to “converse” with students in real time.

“We will first look at the state-of-the-art chatbots that are out there now,” says Salleb-Aouissi. “If there is open-source software that can work on our data, it makes sense to begin there.”

Though chatbots are currently in use—including by some MOOCs—machine question and answering is far from solved; it is in fact a hard problem and an active area of research. Many speech interfaces, including Siri and Alexa, involve relatively simple tasks—scheduling meetings, setting alarms, searching the web—with little back-and-forth conversation. These systems work by transcribing speech to text and then attempting to understand and classify the meaning. The answer, once retrieved, is transcribed back to speech. Some of the more difficult questions may be handled through hand-coding or automated to some extent using AI.

But true conversation, where an answer begets another question, will require much more intelligence and more automation, which Salleb-Aouissi hopes to achieve using methods borrowed from AI and machine learning.

“There is research now into using deep-learning models for text, and while we know they work well with images, text is a much, much harder problem than images. Text has many layers—lexical, semantic, contextual, metaphorical. There is ambiguity and intentional double-meaning in words, and understanding what is meant often requires considering the specific context or employing real-world knowledge. Conversation with all its stops and starts and disfluencies adds to the complexity. We will be looking to put together an interdisciplinary team with expertise in machine learning, in psychology, and of course natural language processing, which is necessary to build a language model for predicting, in the context of our class, the next word in a sentence.”

Predicting the probability of the next word will require data, the more the better. In Salleb-Aouissi’s case, the data will consist of questions taken from her MOOC supplemented with others from discussion forums (e.g., Piazza) of her on-campus AI courses, as well as from text-mining the course material. One requirement is for the chatbot to be trainable on new data so it can be used in other MOOCs (such as the three other Columbia classes that are part of the edX AI series).

The chatbot represents an ambitious project; still she hopes to have a proof of concept in a year. “You can accomplish a lot working with two or three students, especially when they are excited about artificial intelligence, and always willing to try new ideas, new avenues. It’s an inspiration to work with them.”

Posted 7/17/2017
– Linda Crane

In a DARPA project, researchers are looking to build a less invasive implant device at the scale of 1M channels. Such a device would dramatically expand ways artificial systems can support brain functions.

“Settling the query complexity of non-adaptive junta testing” was named best paper at last week’s 32nd Computational Complexity Conference (CCC), the top venue for research in computational complexity theory, the branch of theoretical computer science that aims at understanding what makes certain problems computationally hard. The authors are five Columbia University researchers: Xi Chen, Rocco A. Servedio, Li-Yang Tan (now at Toyota Technological Institute in Chicago), Erik Waingarten, and Jinyu Xie. The last two authors are PhD students.

The paper gives the final answer to a well-studied question in property testing, an area of theoretical computer science: given an unknown Boolean function, how many nonadaptive queries are required to determine whether it is a k-junta versus far from every k-junta?

A k-junta is a function whose value is determined by a subset of at most k relevant variables, out of a potentially huge number of input variables. For example, a decision rule for determining whether a movie is a box office bomb or not (as a Boolean function) would ignore most input attributes—title, director, leading actor, genre, release date, running length, rating, etc.—to consider maybe only two: budget and box office receipts. A simple function such as this, depending on only two variables, is a 2-junta function; a function that looked at 100 attributes would be a 100-junta function.

A function that is a k-junta is relatively simple because it relies on only a small number (k) of variables; in such cases, dimension reduction techniques could potentially be used to remove extraneous variables. A function that is far from every k-junta, on the other hand, is determined by more than k variables and is in fact different from any k-junta on a large fraction of inputs; dimension reduction will not do much to simplify such a problem because the output depends on many variables.

Testing for the k-junta property, which is a helpful first step in exploratory data analysis, works by querying values of the function on inputs chosen by the testing algorithm. The smallest number of such queries required for nonadaptive algorithms—where queries are sent all in one simultaneous batch (as opposed to being sent one after the other, as occurs in adaptive algorithms where subsequent queries can depend on the answers obtained in response to earlier queries)—had been an open question until this paper, which now establishes that at least k^1.5 nonadaptive queries are required. This result represents a dramatic improvement over previous lower bounds, and matches the upper bound of k^1.5 given by Eric Blais in his 2008 paper Improved bounds for testing juntas.

The new lower bound was achieved by constructing a pair of hard-to-distinguish probability distributions supported on k-juntas and functions that are far from k-juntas, respectively. It is based on an idea of random indexing that the Columbia researchers have started exploring for a range of problems, applying it in particular to make progress in monotonicity testing (see Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness). For k-juntas, the functions used in the paper are illustrated in the following figure:

This figure shows how an input x in {0,1}ⁿ is evaluated by a function f used in the paper. Two disjoint subsets of randomly sampled variables, M and A, determine f(x) in the following way. Given x, one first interprets the variables in M as the index i of a function h_i from a sequence of random functions, each of which depends only on a small subset of variables in A. Then f(x) is set to the value of h_i evaluated on the relevant variables in the small subset of A (depicted by the four narrow shaded bands). By adjusting the size of A, f becomes either a k-junta or far from every k-junta, for some appropriate parameter k.

“Once we had the initial idea, the work went quickly; in less than a month, we had the result,” says Chen. “The surprise is that we could push it all the way to get the lower bound to match the upper bound, which has been known since 2008. This result has two implications. We know the exact number of queries needed for nonadaptive junta testing. And we know that adaptive algorithms not only do better than nonadaptive ones, they do a lot better, with k queries instead of k^1.5.”

Adds Servedio, “Junta testing is one of the best-known problems in property testing of Boolean functions. It’s nice to have a thorough understanding of what is and isn’t possible for this basic problem. Hopefully the techniques we used for this result will find further applications for other problems in property testing and query complexity.”

In this video talk, Erik Waingarten gives more technical detail about the method used in the paper.

Posted 7/11/2017

– Linda Crane

Hirschberg’s subject was entrainment, the tendency of speakers to align their speaking style with that of a conversation partner. Joint work with Štefan Beňuš, Nishmar Cestero, Agustín Gravano,  Rivka Levitan, Sarah Ita Levitan, Zhihua Xia.

When data can be anywhere, what country has jurisdiction? In a case involving an Outlook user—whose data was stored in Ireland by a US company (Microsoft)—a US court will rule on what country’s laws apply.

How best to efficiently search for similar items in a large dataset? In this Simons Foundation talk, Alexandr Andoni describes using the tools and perspectives of high-dimensional geometry to benefit search algorithms.

Co-invented by Peter Belhumeur, this free app uses facial recognition technology to identify plant species from a photograph taken of their leaves.

Funville Adventures tells the story of 9-year old Emmy and her 5-year old brother Leo who find themselves transported to Funville, a magical land whose ordinary-looking inhabitants have unique powers to transform objects and people. It’s an adventure book that has children anticipating the action as characters apply their powers to shrink or double the size of objects, replicate things, and turn things into elephants, lots of elephants. That these powers derive from mathematical functions is beside the point and in no way interferes with the telling of a good story. (For those wanting to dive more deeply into the explicit character-function connection, an addendum is provided for the purpose.) The authors, Allison Bishop and Sasha Fradkin, who met at Princeton when both were undergrad math students, are using story-telling to introduce mathematical concepts to children, and in so doing are pioneering a new genre: math-based fantasy.

How is math incorporated into the story?

The math is the characters. Each character personifies a mathematical function, and the power each character has derives from a different function: one can double an object’s size (f(x) = 2x), another can make copies (f(x) = (x,x)), and another can rotate (f(x) = π x) objects. Other characters have other powers. Some powers—but not all—are reversible, and part of the action is driven by Emmy and Leo having to figure out how to counteract the powers of one character with the powers of another.

At one point, a character accidentally applies his power an unknown number of times to shrink Leo, and Emmy has to find someone whose power is to double the size of something so Leo can be restored to normal.

How explicit is the math?

It’s not explicit at all, or very little, and that was in keeping with our goal of writing math-based fiction that could stand on its own merits as a story that kids would want to read; we didn’t want the math to take the reader out of the moment. Math drives the action, but it’s under the hood. For those who want an explicit explanation of the function embodied by a character, we provide an addendum, but we don’t want parents or others feeling obligated to lead a math exercise.

The whole point is for kids to pick up the math organically, not through exercises, but by applying their natural problem-solving and pattern-detecting skills and having fun doing so, similar to someone reading Sherlock Holmes and trying to think ahead to solve the crime. We have this scene with characters preparing for a party. They have to take one balloon and make many. Someone is blowing up balloons and someone else can make copies of things. We go through the thought process: if you copy the balloon not blown up, then you have to blow up all the 100 balloons whereas if you copy it after it’s blown up, you don’t have to go through this step all those times.

Why write for 5- and 10-year olds?

This age group has a great capacity to learn more mathematical concepts than they are learning in school, and to learn them in a more abstract and generalizable way.

Most kids don’t formally encounter a function until pre-algebra which is usually around 8^th grade; so all of the sudden they are presented with f(x). That x is such a struggle when all you’ve ever seen is arithmetic where there is no x. We think functions belong so much earlier in the curriculum. And really, 5-10 is old enough. Children of this age love patterns; they love organizing their thinking that way.

Why did you turn to storytelling to help teach math?

The initial idea was my coauthor’s. She is a curriculum developer and teaches math for kids, so she’s around kids in the classroom and she sees first hand what motivates kids, what gets them excited. She also has two kids of her own, including a daughter who loves stories, just as I did when I was young. In fact, I hated math all through high school; I found formulas boring.

Mathematicians and scientists need to think about storytelling as a way to get broader scientific literacy across to others.

What really got me interested in math as an adult was the creative side of science research, and the human stories of how different people make different discoveries. Why them? Why that idea? What was it about that context and that time that sparked an insight?

Storytelling is fundamental to everything. Mathematicians and scientists need to think about storytelling as a way to get broader scientific literacy across to others. We as scientists don’t optimize the communication part; we spend so much time on the research. But we need to be able to explain science to someone who hasn’t spent years delving into scientific questions. People should be able to more easily see the creativity and beauty in science. So many people don’t get there.

But storytelling can provide a jumping-off point by breaking things down into pieces that people can individually follow and then fit into a larger framework. It’s how stories are told. Take Game of Thrones, an immense world with so many interweaving relationships. We as an audience are never told that there is a world and there are five houses and there are a hundred people in each house; we don’t see in the beginning the huge, overwhelming thing. We start with a single character and by observing what that character is doing, we begin to care about what happens next. As this character interacts with others, we learn about these new characters and piece by piece we begin to understand the larger world they inhabit. We could explain science in that way; we should explain science in that way.

What was the hard part in putting together the book?

Trying to get an agent and a publisher. Funville Adventures is not a typical kids book, it’s not a typical activity book so it doesn’t fit existing categories. It didn’t help that we are new authors trying to pioneer this new genre of math-based fantasy.

While everyone said that a math-based fantasy book sounded interesting, no one knew if there was a market for it. Our publisher, Natural Math, focuses more on activity books but was willing to take a leap of faith with us and try this direct-to-kids fiction format. The publisher—we never did get an agent—worked with us on a Kickstarter campaign to both validate the model and to connect with others seeking innovative approaches to math education. Money raised will help cover the costs of producing the book, which will come out in August.

What has been the response so far to the book?

It’s been good. In beta-testing the book, we’ve seen kids carry forward ideas taken from the book by inventing their own function characters. It gives support to this idea of using storytelling to convey mathematical concepts.

Ideally we want to pioneer not just this one book, but a whole genre of math-based fantasy. We’re thinking of doing a follow-up with coded messages and using encryption to keep secrets. Kids love secrets. We’re even thinking of eventually doing a book with modular arithmetic, like rhythm and periodicity; the mathematical concepts will be different, but the use of storytelling to make the concepts compelling and understandable will the same. It’s a formula we think will work for young and older children, too. Maybe even adults.

Posted June 1, 2017
Illustrations by Mark Gonyea

Schulzrinne, who co-developed key VoIP and other multimedia protocols, takes a look back at what was learned from deploying the land line, 2G, 3G, and 4G.

“A Multi-Scale Model for Simulating Liquid-Hair Interactions,” a paper being presented this summer at SIGGRAPH, describes innovations for capturing liquid onto hairs, modeling the flow along hairs, inducing cohesion, and enabling dripping.