Skip to main content

Rajalakshmi Nandakumar wins SIGMOBILE Doctoral Dissertation Award for advancing wireless sensing technologies that address societal challenges

Rajalakshmi Nandakumar

Allen School alumna Rajalakshmi Nandakumar (Ph.D., ‘20), now a faculty member at Cornell University, received the SIGMOBILE Doctoral Dissertation Award from the Association for Computing Machinery’s Special Interest Group on Mobility of Systems Users, Data, and Computing “for creating an easily-deployed technique for low-cost millimeter-accuracy sensing on commodity hardware, and its bold and high-impact applications to important societal problems.” Nandakumar completed her dissertation, “Computational Wireless Sensing at Scale,” working with Allen School professor Shyam Gollakota in the University of Washington’s Networks & Mobile Systems Lab.

In celebrating Nandakumar’s achievements, the SIGMOBILE award committee highlighted “the elegance and simplicity” of her approach, which turns wireless devices such as smartphones into active sonar systems capable of accurately sensing minute changes in a person’s movements. The committee also heralded her “courage and strong follow-through” in demonstrating how her technique can be applied to real-world challenges — including significant public health issues affecting millions of people around the world.

Among the contributions Nandakumar presented as part of her dissertation was ApneaApp, a smartphone-based system for detecting a potentially life-threatening condition, obstructive sleep apnea, that affects an estimated 20 million people just in the United States alone. Unlike the conventional approach to diagnosing apnea, which involves an overnight stay in a specialized lab, the contactless solution devised by Nandakumar and her Allen School and UW Medicine collaborators could be deployed in the comfort of people’s homes. ApneaApp employs the phone’s speaker and microphone to detect changes in a person’s breathing during sleep, without requiring any specialized hardware. It works by emitting inaudible acoustic signals that are then reflected back to the device and analyzed for deviations in the person’s chest and abdominal movements. ResMed subsequently licensed the technology and made it available to the public for analyzing sleep quality via its SleepScore app.

Her early work on contactless sleep monitoring opened Nandakumar’s eyes to the potential for expanding the use of smartphone-based sonar to support early detection and intervention in the case of another burgeoning public health concern: preventable deaths via accidental opioid overdose. This led to the development of Second Chance, an app that a person activates on their smartphone to unobtrusively monitor changes in their breathing and posture that may indicate the onset of an overdose. Catching these early warning signs as soon as they occur would enable the timely administration of life-saving naloxone. Nandakumar’s colleagues created a startup, Sound Life Sciences, to commercialize this and related work that employs sonar to detect and monitor a variety of medical conditions via smart devices. 

The SIGMOBILE Dissertation Award is the latest in a string of honors recognizing Nandakumar for her groundbreaking contributions in wireless systems research. She previously earned a Paul Baran Young Scholar Award from the Marconi Society, a Graduate Innovator Award from UW CoMotion, and a Best Paper Award at SenSys 2018.

“Rajalakshmi is brilliant, creative and fearless in her research. She repeatedly questions conventional wisdom and takes a different path from the rest of the community,” said Allen School professor Ed Lazowska, who supported Nandakumar’s nomination. “Her work points to the future — a future in which advances in computer science and computer engineering will have a direct bearing on our capacity to tackle societal challenges such as health and the environment. Rajalakshmi is a game-changer.”

Way to go, Rajalakshmi!

Photo credit: Sarah McQuate/University of Washington

July 23, 2021

Gray sheep, golden cows, and everything in between: Yejin Choi earns Longuet-Higgins Prize in computer vision for enabling more precise image captions via natural language generation

Sheep standing in glass and metal bus shelter by road
“The gray sheep is by the gray road”

Allen School professor Yejin Choi is among a team of researchers recognized by the Computer Vision Foundation with its 2021 Longuet-Higgins Prize for their paper “Baby talk: Understanding and generating simple image descriptions.” The paper was among the first to explore the new task of generating image captions in natural language by bridging two fields of artificial intelligence: computer vision and natural language processing. Choi, who is also a senior research manager at the Allen Institute for AI (AI2), completed this work while a faculty member at Stony Brook University. She and her co-authors originally presented the paper at the 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR).

Baby talk is the process by which adults assist infants in acquiring language and building their understanding of the world that is characterized in part by the use of grammatically simplified speech. Drawing upon this concept, Choi and her collaborators set out to teach machines to generate simple yet original sentences describing what they “see” in a given image. This was a significant departure from conventional approaches grounded in the retrieval and summarization of pre-existing content. To move past the existing paradigm, the researchers constructed statistical models for visually descriptive language by mining and parsing the large quantities of text available online and paired them with the latest recognition algorithms. Their strategy enabled the new system to describe the content of an image by generating sentences specific to that particular image, as opposed to requiring it to shoehorn content drawn from a limited document corpus into a suitable description. The resulting captions, the team noted, had greater relevance and precision in the way they describe the visual content.

Yejin Choi
Yejin Choi

“At the time we did this work, the question of how to align the semantic correspondences or alignments across different modalities, such as language and vision, was relatively unstudied. Image captioning is an emblematic task to bridge the longstanding gap between NLP research with computer vision,” explained Choi. “By bridging this divide, we were able to generate richer visual descriptions that were more in line with how a person might describe visual content — such as their tendency to include not just information on what objects are pictured, but also where they are in relation to each other.” 

This incorporation of spatial relationships into their language generator was key in producing more natural-sounding descriptions. Up to that point, computer vision researchers who focused on text generation from visual content relied on spatial relationships between labeled regions of an image solely to improve labeling accuracy; they did not consider them outputs in their own right on a par with objects and modifiers. By contrast, Choi and her colleagues considered the relative positioning of individual objects as integral to developing the computer vision aspect of their system, to the point of using these relationships to drive sentence generation in conjunction with the depicted objects and their modifiers.

Some of the results were deemed to be “astonishingly good” by the human evaluators. In one example presented in the paper, the system accurately described a “gray sheep” as being positioned “by the gray road”; the “gray sky,” it noted, was above said road. For another image, the system correctly pegged that the “wooden dining table” was located “against the first window.” The system also accurately described the attributes and relative proximity of rectangular buses, shiny airplanes, furry dogs, and a golden cow — among other examples.

Cow with curved horns and shaggy, golden-brown hair standing in a field with trees in the background
The golden cow

The Longuet-Higgins Prize is an annual “test of time” award presented during CVPR by the IEEE Pattern Analysis and Machine Intelligence (PAMI) Technical Committee to recognize fundamental contributions that have had a significant impact in the field of computer vision. Choi’s co-authors on this year’s award-winning paper include then-master’s students Girish Kulkarni, Visruth Premraj and Sagnik Dhar; Ph.D. student SiMing Li; and professors Alexander C. Berg and Tamara L. Berg, both now on the faculty at University of North Carolina Chapel Hill.

Read the full paper here.

Congratulations to Yejin and the entire team!

July 22, 2021

Hand it over! Allen School and NVIDIA researchers earn Best Paper Award at ICRA for enabling smooth human-to-robot handoff of arbitrary objects

Person's arm and hand transferring banana to table-mounted robot arm and hand

Allen School professors Maya Cakmak and Dieter Fox, along with their collaborators at NVIDIA’s AI Robotics Research Lab, earned the award for Best Paper in Human-Robot Interaction at the IEEE International Conference on Robotics and Automation (ICRA 2021) for introducing a new vision-based system for the smooth transfer of objects between human and robot. In “Reactive Human-to-Robot Handovers of Arbitrary Objects,” the team employs visual object and hand detection, automatic grasp selection, closed-loop motion planning, and real-time manipulator control to enable the successful handoff of previously unknown objects of various sizes, shapes and rigidity. It’s a development that could put more robust human-robot collaboration within reach.

“Dynamic human-robot handovers present a unique set of research challenges compared to grasping static objects from a recognizable, stationary surface,” explained Fox, director of the Allen School’s Robotics and State Estimation Lab and senior director of robotics research at NVIDIA. “In this case, we needed to account for variations not just in the objects themselves, but in how the human moves the object, how much of it is covered by their fingers, and how their pose might constrain the direction of the robot’s approach. Our work combines recent progress in robot perception and grasping of static objects with new techniques that enable the robot to respond to those variables.”

The system devised by Fox, Cakmak, and NVIDIA researchers Wei Yang, Chris Paxton, Arsalan Mousavian and Yu-Wei Chao does not require objects to be part of a pre-trained dataset. Instead, it relies on a novel segmentation module that enables accurate, real-time hand and object segmentation, including objects the robot is encountering for the very first time. Rather than attempting to directly segment objects in the hand, which would not provide the flexibility and adaptability they sought, the researchers trained a fully convolutional network for hand segmentation given an RGB image, and then inferred object segmentation based on depth information. To ensure temporal consistency and stability of the robot’s grasps in response to changes in the user’s motion, the team extended the GraspNet grasp planner to refine the robot’s grasps over consecutive frames over time. This enables the system to react to a user’s movements, even after the robot has begun moving, while consistently generating grasps and motions that would be regarded as smooth and safe from a human perspective.

Portraits of Maya Cakmak and Dieter Fox
Maya Cakmak (left) and Dieter Fox

Crucially, the researchers’ approach places zero constraints on the user regarding how they may present an object to the robot; as long as the object is graspable by the robot, the system can accommodate its presentation in different positions and orientations. The team tested the system on more than two dozen common household objects, including a coffee mug, a remote control, a pair of scissors, a toothbrush and a tube of toothpaste, to demonstrate how it generalizes across a variety of items. That variety goes beyond differences between categories of object, as the objects within a single category can also differ significantly in their appearance, dimensions and deformability. According to Cakmak, this is particularly true in the context of people’s homes, which are likely to reflect an array of human needs and preferences to which a robot would need to adapt. To ensure their approach would have the highest utility in the home for users who need assistance with fetching and returning objects, the researchers evaluated their system using a set of everyday objects prioritized by people with amyotrophic lateral sclerosis (ALS).

“We may be able to pass someone a longer pair of scissors or a fuller plate of food without thinking about it — and without causing an injury or making a mess — but robots don’t possess that intuition,” said Cakmak, director of the Allen School’s Human-Centered Robotics Lab. “To effectively assist humans with everyday tasks, robots need the ability to adapt their handling of a variety of objects, including variability among objects of the same type, in line with the human user. This work brings us closer to giving robots that ability so they can safely and seamlessly interact with us, whether that’s in our homes or on the factory floor.”

ICRA is the IEEE’s flagship conference in robotics. The 2021 conference, which followed a hybrid model combining virtual and in-person sessions in Xi’an, China, received more than 4,000 paper submissions spanning all areas of the field.

Visit the project page for the full text of the research paper, demonstration videos and more.

Let’s give a big hand to Maya, Dieter and the entire team!

July 13, 2021

Twice as nice: Allen School researchers earn dual Best Paper Awards at STOC

Members of the Allen School’s Theory of Computation group earned two Best Paper Awards at the 53rd annual Symposium on Theory of Computing (STOC 2021) last week for achieving a pair of “firsts” that advanced the state of the art in approximation algorithms and cryptography, respectively. One of the winning papers, co-authored by Allen School Ph.D. student Nathan Klein and professors Anna Karlin and Shayan Oveis Gharan, produced the first improvement on the Traveling Salesperson Problem in more than 40 years. The other, which Allen School professor Rachel Lin co-authored with Aayush Jain, a Ph.D. student at the University of California Los Angeles and intern at NTT Research, and UCLA professor Amit Sahai, answered a decades-old question by providing the first-ever proof of the security of indistinguishability obfuscation based on well-founded assumptions.

Portraits of Anna Karlin, Nathan Klein, and Shayan Oveis Gharan
Left to right: Anna Karlin, Nathan Klein and Shayan Oveis Gharan

One of the core problems underpinning the theory and practice of computer science that extends to multiple other domains, the Traveling Salesperson Problem (TSP) seeks to find the most efficient route over multiple destinations and back to the starting point. Short of finding the optimum, computer scientists have relied on approximation algorithms to chip away at the problem by finding an answer that is, as Klein described in a piece he wrote for The Conversation, “good enough.” As the name suggests, TSP has obvious applications in transportation and logistics. But, Klein explained, a solution will have implications for multiple other domains, from genomics to circuit board design.

“This is important for more than just planning routes,” Klein wrote. “Any of these hard problems can be encoded in the Traveling Salesperson Problem, and vice versa: Solve one and you’ve solved them all.”

Klein and his colleagues may not have completely solved the problem, but they brought the field an important — and hugely symbolic — step closer. Their algorithm, which they revealed to the world last summer, is the first to break the elusive 50% threshold for TSP — meaning the cost of its result will always be less than 50% above the optimum. While their result represents only a marginal improvement over the previous state of the art in real terms, at roughly 49.99999%, the team’s achievement offers a foundation on which they and their fellow researchers can build in future work. And build they most assuredly will; according to Karlin, once a researcher encounters TSP, it is very difficult to set it aside. 

“One of my favorite theoretical computer scientists, Christos Papadimitriou, summed it up perfectly,” observed Karlin. “He said, ‘TSP is not a problem. It is an addiction.’”

Her faculty colleague Oveis Gharan knows the feeling well, having spent the past 10 years tackling various elements of TSP. For him, this milestone is another step forward on an open-ended journey — and one he is keen to delve into more deeply now that the dust has settled and the proof has checked out.

“A natural follow-up to our result would be to find a simpler proof with a significantly bigger improvement over the 50%, but to be honest, that is not really what interests me,” said Oveis Gharan. “Often, when someone breaks a long-standing barrier, they develop or employ several new tools or ideas in the process. These typically are not well understood in their full generality, because they are mainly specialized for that specific application. So, what I want to do after such a result is to better understand these new tools and ideas. Why do they work? What other applications can they possibly have? Can we generalize them further? Is there any other open problem that they can help us address? We’re exploring these questions now with regard to some of the tools that we used in this TSP paper.”

Portraits of Rachel Lin, Aayush Jain, and Amit Sahai
Left to right: Rachel Lin, Aayush Jain and Amit Sahai

Lin’s work with Jain and Sahai on indistinguishability obfuscation (iO) also represents a discovery that was decades in the making. In this case, the researchers proved the security of a potentially powerful cryptographic scheme for protecting computer programs from would-be hackers by making them unintelligible to adversaries while retaining their functionality. 

The team’s breakthrough paper demonstrates that provably secure iO is constructed from subexponential hardness of four well-founded assumptions: Symmetric External Diffie-Hellman (SXDH) on pairing groups, Learning with Errors (LWE), Learning Parity with Noise (LPN) over large fields, and a Boolean Pseudo-Random Generator (PRG) that is very simple to compute. All four have a long history of study that is well-rooted in complexity, coding and number theory — enabling Lin and her collaborators to finally put a cryptographic approach that was first described in 1976, and mathematically formalized 20 years ago, on a firm footing. The researchers also devised a simple new method for leveraging LPN over fields and PRG in NC0  — a simple model of computation in which every output bit depends on a constant number of input bits — to build a structured-seed PRG (sPRG). The seed, which comprises both a public and private part, maintains the scheme’s pseudo-randomness in cases where an adversary is able to see the public seed and the sPRG output.

Now that they have verified the security of iO based on well-founded assumptions, Lin and her collaborators are already working to extend their results — and they are eager to see others expand upon them, as well. 

“The next step is further pushing the envelope and constructing iO from weaker assumptions,” Lin said when the team announced its results. “At the same time, we shall try to improve the efficiency of the solutions, which at the moment is very far from being practical. These are ambitious goals that will need the joint effort from the entire cryptography community.”

STOC is organized by the Association for Computing Machinery’s Special Interest Group on Algorithms and Computation Theory (ACM SIGACT).

Read Quanta Magazine’s past coverage of the TSP result here and the iO result here.

Congratulations to all!

June 28, 2021

Q&A with Tadayoshi Kohno: In his new novella ‘Our Reality,’ Allen School professor invites readers to consider who benefits (and who doesn’t) from technology

Book cover art: water and horizon in a grid with silhouettes of people and text Our Reality: A novella, Tadayoshi Kohno

What if you could engage with the world — go to class, do your job, meet up with friends, get a workout in — without leaving the comfort of your bedroom thanks to mixed-reality technology? 

What if you could customize your avatar in many ways, but you couldn’t make it reflect your true racial or cultural identity? What if the best way to get a high-paying job was based on your access to this technology, only you are blind and the technology was not designed for you?

And what if notions of equity and justice manufactured in that virtual world — at least, for some users — still don’t carry over into the real one?

These and many other questions come to mind as one reads “Our Reality,” a new science-fiction novella authored by Tadayoshi (Yoshi) Kohno, a professor in the University of Washington’s Paul G. Allen School of Computer Science & Engineering. Kohno, who co-directs the UW’s Security and Privacy Research Lab and Tech Policy Lab, has long regarded science fiction as a powerful means through which to critically examine the relationship between technology and society. He even dealt previously with the issue in a short piece he contributed to the Tech Policy Lab’s recent anthology, “Telling Stories,” which explores culturally-responsive artificial intelligence (AI).

“Our Reality,” so named for the mixed-reality technology he imagines taking hold in the post-pandemic world circa 2034, is Kohno’s first foray into long-form fiction. The Allen School recently sat down with Kohno with the help of another virtual technology — Zoom — to discuss his inspiration for the story, his personal as well as professional journey to examining matters of racism, equity and justice, and how technology meant to help may also do harm.

First of all, congratulations on the publication of your first novella! As a professor of computer science and a well-known cybersecurity researcher, did you ever expect to be writing a work of science fiction?

Yoshi Kohno: I’ve always been interested in science fiction, ever since I was a kid. I’ve carried that fascination into my career as a computer science educator and researcher. Around 10 years ago, I published a paper on science fiction prototyping and computer security education that talked about my experiences asking students in my undergraduate computer security course to write science fiction as part of the syllabus. Writing science fiction means creating a fictional world and then putting technology inside that world. Doing so forces the writer — the students, in my course — to explore the relationship between society and technology. It has been a dream of mine to write science fiction of my own. In fact, when conducting my research — on automotive security, or cell phone surveillance, or anything else — I have often discussed with my students and colleagues how our results would make good plot elements for a science fiction story! The teenage me would be excited that I finally did it. 

What was the inspiration for “Our Reality,” and what made you decide now was the right time to realize that childhood dream?

YK: Recently, many people experienced a significant awakening to the harms that technology can bring and to the injustices in society. We, as a society and as computer scientists, have a responsibility to address these injustices. I have written a number of scientific, scholarly papers. But I realized that some of the most important works in history are fiction. Think about the book “1984,” for example, and how often people quote from it. Now, I know my book will not be nearly as transformative as “1984,” but the impact of that book and others inspired me.

I was particularly disturbed by how racism can manifest in technologies. As an educator, I believe that it is our responsibility to help students understand how to create technologies that are just, and certainly that are not racist. I wrote my story with the hope that it would inform the reader’s understanding of racism and racism in technology. At the same time, I also want to explicitly acknowledge that there are already amazing books on the topic of racism and technology. Consider, for example, Dr. Ruha Benjamin’s book “Race After Technology,” or Dr. Safiya Umoja Noble’s book “Algorithms of Oppression.” I hope that readers committed to addressing injustices in society and in technology read these books, as well as the other books I cite in the “Suggested Readings” section of my novella. 

In addition to racism in technology, my story also tries to surface a number of other important issues. I sometimes intentionally added flaws to the technologies featured in “Our Reality” — flaws that can serve as starting points for conversations.

Portrait of Yoshi Kohno
Yoshi Kohno (Dennis Wise/University of Washington)

How did your role as the Allen School’s Associate Director for Diversity, Equity, Inclusion and Access inform your approach to the story?

YK: I view diversity, equity, inclusion, and access as important to me as an individual, important for our school, and important for society. I’ve thought about the connection between society and technology throughout my career. As a security researcher and educator, I have to think about the harms that technologies could bring. But when I took on the role of Associate Director, I realized that I had a lot more learning to do. I devoured as many resources as I could, I talked with many other people with expertise far greater than my own, I read many books, I enrolled in the Cultural Competence in Computing (3C) Fellows Program, and so on. This is one of the things that we as a computer science community need to always be doing. We should always be open to learning more, to questioning our assumptions, and to realizing that we are not the experts.

One of the things that I’ve always cared about as an educator was helping students understand not only the relationship between society and technology, but to recognize how technologies can do harm. I’m motivated to get people thinking about these issues and proactively working to mitigate those harmful impacts. If people are not already thinking about the injustices that technologies can create, then I hope that “Our Reality” can help them start. 

One of the main characters in “Our Reality,” Emma, is a teenage Black girl. How did you approach writing a character whose identity and experiences would be so different from your own?

YK: Your question is very good. I have several answers that I want to give. First, this question connects to one of the teaching goals of “Our Reality” and, in particular, to Question 6 in the “Questions for Readers” section of the novella. Essentially, how should those who design technologies approach their work when the users or affected stakeholders might have identities very different from their own? And how do they ensure that they don’t rely on stereotypes or somehow create an injustice for those users or affected stakeholders? Similarly, in writing “Our Reality,” and with my goal of contributing to a discussion about racism in technology, I found myself in the position of centering Emma, a teenage girl who is Black. This was a huge responsibility, and I knew that I needed to approach this responsibility respectfully and mindfully. My own identity is that of a cisgender man who is Japanese and white. 

The first thing I did towards writing Emma was to buy the book “Writing the Other“ by Nisi Shawl and Cynthia Ward. It is an amazing book, and I’d recommend it for anyone else who wishes to either write stories that include characters with identities other than their own. I read their book last summer. I then discovered that Shawl was teaching a year-long course in science fiction writing through the Hugo House here in Seattle, so I enrolled. That taught me a significant amount about writing science fiction and writing about diverse characters.

I should acknowledge that while I tried the best I could, I might have made mistakes. While I have written many versions of this story, and while I’ve received amazingly useful feedback along the way, any mistakes that remain are mine and mine alone.

In your story, Our Reality is also the name of a technology that allows users to experience a virtual, mixed-reality world. One of the other themes that stood out is who has access to technologies like Our Reality — the name implies a shared reality, but it’s only really shared by those who can afford it. There are the “haves” like Emma and her family, and the “have nots” like Liam and his family. How worried are you that unequal access to technology will exacerbate societal divides?

YK: I’m quite worried that technology will exacerbate inequity along many dimensions. In the context of mixed-reality technology like Our Reality, I think there are three reasons that a group of people might not access it. One is financial; people may not be able to afford the mixed-reality Goggles, the subscription, the in-app purchases, and so on. They either can’t access it at all or will have unequal access to its features, like Liam discovered when he tried to customize his avatar beyond the basic free settings. The second reason is because the technology was not designed for them. I alluded to this in the story when I brought up Liam’s classmate Mathias, who is blind. Finally, some people will elect not to access the technology for ideological reasons. When I think about the future of mixed-reality technologies, like Our Reality, I worry that society will further fracture into different groups, the “haves” or “designed fors” and the “have nots” or “not designed fors.”

Emma’s mother is a Black woman who holds a leadership position in the company that makes Our Reality, but her influence is still limited. For example, Emma objects to the company’s decision to make avatars generic and “raceless,” which means she can’t fully be herself in the virtual world. What did you hope people would take away from that aspect of the story?

YK: First, this is an example of one of the faults that I intentionally included in the technologies in “Our Reality.” I also want to point the reader to the companion document that I prepared, which describes in more detail some of the educational content that I tried to include in Our Reality. Your question connects to so many important topics, such as the notion of “the unmarked state” — the default persona that one envisions if they are not provided with additional information — as well as colorblind racism. This also connects to something that Dr. Noble discusses in the book “Algorithms of Oppression” and which I tried to surface in “Our Reality” — that not only do we need to increase the diversity within the field, but we need to overcome systemic issues that stand in the way of fully considering the needs of all people, and systemic inequities, in the design of technologies.

Stepping back, I am hoping that readers start to think about some of these issues as they read “Our Reality.” I hope that they realize that the situation described in “Our Reality” is unjust and inequitable. I hope they read the companion document, to understand the educational content that I incorporated into “Our Reality.” And then I hope that readers are inspired to read more authoritative works, like “Algorithms of Oppression” and the other books that I reference in the novella and in the companion document.

You and professor Franziska Roesner, also in the Allen School, have done some very interesting research with your students in the UW Security and Privacy Research Lab. Your novella incorporates several references to issues raised in that research, such as tracking people via online advertising and how to safeguard users of mixed-reality technologies from undesirable or dangerous content. It almost feels uncomfortably close to your version of 2034 already. So how can we as a society, along with our regulatory frameworks, catch up and keep up with the pace of innovation?

YK: Rather than having society and our regulatory frameworks catch up to the pace of innovation, we should consider slowing the pace of innovation. Often there is a tendency to think that technology will solve our problems; if we just build the next technology, things will be great, or so it seems like people often think. Instead of perpetuating that mentality, maybe we should slow down and be more thoughtful about the long-term implications of technologies before we build them — and before we need to put any regulatory framework in place. 

Franziska Roesner and Yoshi Kohno wearing augmented-reality goggles
Kohno and colleague Franziska Roesner have explored the privacy and security of mixed reality technologies with students in the Security and Privacy Research Lab

As part of changing the pace of innovation, we need to make sure that the innovators of technology understand the broader society and global context in which technologies exist. This is one of the reasons why I appreciate the Cultural Competence in Computing (3C) Fellows Program coming out of Duke so much, and why I encourage other educators to apply. That program was created by Dr. Nicki Washington, Dr. Shaundra B. Daily, and graduate assistant Cecilé Sadler at Duke University. The program’s goal is to help empower computer science educators, throughout the world, with the knowledge and skills necessary to help students understand the broader societal context in which technologies sit.

As an aside, one of the reasons that my colleagues Ryan Calo in the School of Law and Batya Friedman in the iSchool and I co-founded the Tech Policy Lab at the University of Washington is that we understood the need for policymakers and technologists to also come together and explore issues at the intersection between society, technology, and policy.

Speaking of understanding context, in the companion document to “Our Reality” you note “Computing systems can make the world a far better place for some, but a far worse one for others.” Can you elaborate? 

YK: There are numerous examples of how technologies, when one looks at them from a 50,000 foot perspective, might seem to be beneficial to individuals or society. But when one looks more closely at the specific case of specific individuals, you find that they’re not providing a benefit; in fact, they have the potential to actively cause harm. Consider, for example, an app that helps a user find the location of their family or friends. Such an app might seem generally beneficial — it could help a parent or guardian find their child if they get separated at a park. But now consider situations of domestic abuse. Someone could use that same technology to track and harm their victim.

Another example, which I explored in “Our Reality” through Emma’s encounter with the police drones, is inequity across different races. Face detection and recognition systems are now widely understood to be inequitable because they have decreased accuracy with Black people compared to white people. This is incredibly inequitable and unjust. I encourage readers to learn more about the inequities with face detection and face recognition. One great place to start is the film “Coded Bias” directed and produced by Shalini Kantayya, which centers MIT Media Lab researcher Joy Buolamwini.

At one point, Emma admonishes her mother, a technologist, that she can’t solve everything with technology. How do we determine what is the best use of technology, and what is the responsibility of your colleagues who are the ones inventing it?

YK: I think that it is absolutely critical for those who are driving innovation to understand how the technology that they create sits within a broader society and interacts with people, many of whom are different from themselves. I referred earlier to this notion of a default persona, also called the “unmarked state.” Drawing from Nisi Shawl and Cynthia Ward’s book “Writing the Other,” this is more often than not someone who is white, male, heterosexual, single, young, and with no disabilities. Not only should one be thinking about how a technology would fit in the context of society, but also consider it in the context of the many people who do not identify with this default persona. 

On top of that, when designing technologies for someone “not like me,” people need to be sure they are not invoking stereotypes or false assumptions about those who are not like themselves. There’s a book called “Design Justice” by Dr. Sasha Costanza-Chock about centering the communities for whom we are designing. As technologists, we ought to be working with those stakeholders to understand what technologies they need. And we shouldn’t presume that any specific technology is needed. It could be that a new technology is not needed.

Kohno drew inspiration from an academic-industry summit on mixed reality that he and Roesner co-organized in exploring the potential pitfalls of the technology in “Our Reality”

Some aspects of Our Reality sound like fun — for example, when Emma and Liam played around with zero gravity in the science lab. If you had the opportunity and the means to use Our Reality, would you?

YK: I think it is an open research question about what augmented reality and mixed-reality technologies will be like in the next 15 years. I do think that technologies like Our Reality will exist in the not-too-distant future. But I hope that the people developing these technologies will have addressed the access questions and societal implications that I raised in the story. As written, I think I would enjoy aspects of the technology, but I would not feel comfortable using it if the equity issues surrounding Our Reality aren’t addressed.

Stepping even further back, there are a whole class of risks with mixed-reality technologies that are not deeply surfaced in this story: computer security risks. This is a topic that Franziska Roesner and I have been studying at UW for about 10 years, along with our colleagues and students. There are a lot of challenges to securing future mixed-reality platforms and applications.

So you would be one of those ideological objectors you mentioned earlier.

YK: I would, yes. And, in addition to issues of access and equity and the various security risks, I used to also be a yoga instructor. I like to see and experience the world through my real senses. I fear that mixed-reality technologies are coming. But for me, personally, I don’t want to lose the ability to experience the world for real, rather than through Goggles.

Who did you have in mind as the primary audience for “Our Reality”?

YK: I had several primary audiences, actually. In a dream world, I would love to see middle school students reading and discussing “Our Reality” in their social studies classes. I would love for the next generation to start discussing issues at the intersection of society and technology before they become technologists. If students discuss these issues in middle school, then maybe it will become second nature for them to always consider the relationship between society and technology, and how technologies can create or perpetuate injustices and inequities.

I would also love for high school and first- and second-year college students to read this story. And, of course, I would love for more senior computer scientists — advanced undergraduate students and people in industry — to read this story, too. I also hope that people read the books that I reference in the Suggested Readings section of my novella and the companion document. Those references are excellent. My novella scratches the surface of important issues, and provides a starting point for deeper considerations; the books that I reference provide much greater detail and depth.

As an educator, I wanted the story to be as accessible as possible, to the broadest audience possible. That’s why I put a free PDF of the novella on my website. I also put a PDF of the companion document on my web page. I wrote the companion document in such a way that I hope it will be useful and educational to people even if they never read the “Our Reality” novella.

What are the main lessons you hope readers will take away from “Our Reality”?

YK: I hope that readers will understand the importance of considering the relationship between society and technology. I hope that readers will understand that it is not inevitable that technologies be created. I hope that readers realize that when we do create a technology, we should do so in a responsible way that fully acknowledges and considers the full range of stakeholders and the present and future relationships between that technology and society.

Also, I tried to be somewhat overt about the flaws in the technologies featured in “Our Reality.” As I said earlier, I intentionally included flaws in the technologies in “Our Reality,” for educational purposes. But when one interacts with a brand new technology in the real world, sometimes there are flaws, but those flaws are not as obvious. I would like to encourage both users and designers of technology to be critical in their consideration of new technologies, so that they can proactively spot those flaws from an equity and justice perspective. 

If my story reaches people who have not been thinking about the relationship between society, racism, and technology already, I hope “Our Reality” starts them down the path of learning more. I encourage these readers to look at the “Our Reality” companion document, and explore some of the other resources that I reference. I would like to also thank these readers for caring about such an important topic.

Readers may purchase the paperback or Kindle version of “Our Reality” on, and access a free downloadable PDF of the novella, the companion document, and a full list of resources on the “Our Reality” webpage.

June 24, 2021

Allen School professor and “SIGACT oracle” Paul Beame recognized with ACM SIGACT Distinguished Service Award

Portrait of Paul Beame with sunlit trees and foliage in the background

Paul Beame, an associate director of the Allen School and a professor in the Theory of Computation group, has been honored with the 2021 ACM SIGACT Distinguished Service Award for his more than 20 years of dedicated and effective support to the theoretical computer science community. Each year, the Association for Computing Machinery’s Special Interest Group on Algorithms and Computation Theory presents the award to an individual or group who has gone above and beyond in service to their colleagues even as they work to advance the foundations of computing. 

Since joining the University of Washington faculty in 1987, Beame has devoted much of his research career to exploring pure and applied complexity to address a range of computational problems in multiple domains. Beyond his research contributions, Beame has dedicated significant time and effort to promoting knowledge-sharing and collaboration within the theoretical computer science community through various leadership roles in ACM, SIGACT, and its sibling organization within the IEEE Computer Society, the Technical Committee on Mathematical Foundations (TCMF). He is also credited with advancing two of the field’s flagship conferences, the ACM Symposium on the Theory of Computing (STOC) and the IEEE Symposium on Foundations of Computer Science (FOCS), through a combination of formal and informal leadership and service. 

FOCS 1999 marked Beame’s first foray into conference leadership, when he took on the role of program committee chair and served informally as a local co-organizer. He subsequently went on to serve as general chair, finance chair, and/or local co-organizer for no fewer than half a dozen more FOCS and STOC conferences between 2006 and 2011. Beyond fulfilling his official leadership duties, over the years Beame has provided organizers of numerous successive conferences with unofficial assistance ranging from identifying potential venues, to recruiting local volunteers, to addressing issues with the online registration system. 

“Paul’s tireless service, in both official and unofficial roles, has been highly instrumental in ensuring the smooth running and continued vitality of the flagship STOC and FOCS conferences and of SIGACT itself,” said ACM SIGACT Chair Samir Khuller, the Peter and Adrienne Barris Professor and Chair of the Computer Science Department at Northwestern University. “In addition to his many official roles, Paul’s influence is also felt, equally significantly, through his unofficial roles as ‘SIGACT oracle’ and advisor to those responsible for running our main conferences every year.”

Following the completion of his term as chair of IEEE’s TCMF in 2012, Beame began his tenure as chair of ACM SIGACT. During the next six years, as he served out his term as chair and immediate past chair of the group, Beame is credited with promoting greater cooperation between the two groups that represented the theoretical computer science community in parallel. He was also instrumental in revitalizing STOC through the introduction of TheoryFest, for which he co-planned and co-organized the first two events in 2017 and 2018. 

As a leader, Beame is known for building in mechanisms for ensuring good management practices will carry forward while building up the infrastructure for running conferences and committees that enables his successors to seamlessly take the reins. And he hasn’t been shy about challenging the conventional wisdom along the way.

“There are typically two distinct types of exceptional leaders for professional organizations,” observed David Shmoys, Laibe/Acheson Professor at Cornell University. “First, there are the people who are detail-focused and excel at making sure that the myriad of lower-level processes work with the precision of a well-engineered system — in a pre-digital world, the standard metaphor would be a Swiss watch. Second are the ‘out-of-the-box’ thinkers who aren’t content with making things run as well as possible within the framework of the status quo, but instead push the organization to improve upon itself by inventing new ways that the systems can run. Paul excels in both dimensions, and this is what makes his service extraordinarily remarkable.”

Even after officially passing the baton to the next slate of leaders and volunteers, Beame continues to be generous with his time and advice to help sustain the community’s momentum.

“Whereas many people who have served in leadership roles view stepping down as a chance to leave obligations behind,” Khuller noted, “Paul has repeatedly viewed it as an opportunity to smooth the path for future incumbents.”

In addition to laying the groundwork for future leaders, Beame was also a vocal champion of open access to SIGACT and other ACM conference proceedings during his time representing SIGACT and the SIG Board. Despite entrenched opposition from some quarters, his position ultimately prevailed. Beginning in 2015, all SIGACT and many other SIG conference proceedings were made open-access in perpetuity via their respective conference websites — including the STOC website, which Beame himself initially built and maintained along with the FOCS website to provide an online history of past conferences and their proceedings. 

“This award is a well-earned honor for Paul, who has been tireless in helping SIGACT move forward,” said Allen School professor emeritus Richard Ladner.

Ladner’s faculty colleague Anna Karlin agreed. “For two decades, Paul has repeatedly stepped up to provide every manner of service to the SIGACT community,” she said. “He is an exemplary recipient of this award.”

Read the award committee’s full citation here, and learn more about the SIGACT Distinguished Service Award here.

Congratulations, Paul!

June 21, 2021

“Every single one of you has what it takes to do great things”: A tribute to the Allen School Class of 2021

Katherine Turner

Last week marked the end of an academic year unlike any other — and the culmination of all of the hard work, hopes and dreams of a graduating class unlike any other. With the resumption of in-person pomp and circumstance precluded due to ongoing pandemic-related restrictions at the University of Washington, the Allen School marked this important milestone with a virtual tribute highlighting the Class of 2021’s commitment to excellence and service — and acknowledging their perseverance in the face of multiple, significant challenges over the past year.

Professor Magdalena Balazinska, director of the Allen School, led the tribute with a video message congratulating the graduates on rising to the occasion and completing their degrees under difficult circumstances. And now that they had, she urged them to use what they have learned to make the world a better place — and continue working to make computing a more inclusive field.

“As you graduate, you have the opportunity to make an impact in a variety of ways. Take it. Be bold,” Balazinska said. “Find ways to help the community and the world around you. Work on addressing humanity’s greatest challenges. Develop technology that serves everyone, not just those who look like you or share the same background or abilities. Strive to have diverse teams where everyone feels welcome and included.

“Making the world better is not only your opportunity, but it is your responsibility,” she continued. “Because if you don’t do it, then who will?”

Balazinska’s remarks were followed by a series of congratulatory messages to the graduates from her fellow faculty members, many of whom also contributed to a Class of 2021 Kudoboard that included messages from friends, family and classmates to the newly minted graduates. The Allen School also took the opportunity to recognize members of the graduating class who had particularly distinguished themselves through their academic achievements, leadership, and service contributions with its annual student awards

Portraits of Skyler Hallinan, Joy He-Yueya, Parker Ruth
From left: Skyler Hallinan, Joy He-Yueya and Parker Ruth

Skyler Hallinan is one of three graduates to receive the Allen School’s Outstanding Senior Award, which honors students with exceptional academic performance who exemplify leadership, good citizenship, and the pursuit of knowledge. Hallinan, who majored in computer science, applied & computational mathematical sciences, and bioengineering, was recognized for his undergraduate research in natural language processing under the guidance of Allen School professors Yejin Choi and Noah Smith, including techniques for analyzing misinformation and media bias and advancing commonsense reasoning. He also worked on the development of an orally ingestible hydrogel that would act as a substitute for a functional kidney in patients with chronic kidney disease and served as a teaching assistant (TA) in the Allen School for multiple quarters.

Joy He-Yueya and Parker Ruth each earned an Outstanding Senior Award and the Allen School’s Best Senior Thesis Award. He-Yueya, who earned her bachelor’s in computer science, worked with Allen School professor Tim Althoff in the Behavioral Data Science Group on research that led to her award-winning thesis, “Assessing the Relationship Between Routine and Schizophrenia Symptoms with Passively Sensed Measures of Behavioral Stability.” She also contributed to a project at the Max Planck Institute for Software Systems that used reinforcement learning to generate personalized curriculum for students learning to program. He-Yueya has served in multiple tutoring and peer mentoring roles — including helping other undergraduates to get their start in research. 

Portraits of Eric Fan and Eunia Lee
Eric Fan (left) and Eunia Lee

Ruth — who previously received the Dean’s Medal for Academic Excellence from the College of Engineering — was recognized by the Allen School for his many contributions in undergraduate research as a member of the UbiComp Lab, where he advanced mobile health tools that screen for conditions such as osteoporosis and stroke; enable continuous physiological sensing; and monitor threats to public health. That work formed the basis of his award-winning senior thesis, “Design Principles for Mobile and Wearable Health Technologies,” advised by professor Shwetak Patel.

The Allen School honored two other graduating seniors — Eric Fan and Eunia Lee — with Undergraduate Service Awards. This award recognizes students who have gone above and beyond in supporting the many events and activities that contribute to a vibrant school community. Fan has helped build that sense of community both in and out of the classroom, whether in person or remote. He served as TA coordinator for the Allen School’s introductory programming series, the entré into computer science for many students in and outside of the major. He also served as an officer of the UW chapter of the Association for Computing Machinery (ACM) and a member-at-large of the Allen School’s Student Advisory Council. After earning his bachelor’s in computer engineering, Fan is continuing his studies in the Allen School’s combined B.S./M.S. program.

Lee, who earned her degree in computer science, has taken on multiple leadership roles in the Allen School’s K-12 and campus-level outreach, with a focus on strengthening diversity and inclusion. Her contributions have included service as a lead Ambassador to high schools and lead TA for the direct-to-major seminar that assists freshmen entering the Allen School. She also chaired the UW chapter of ACM and was instrumental in the formation of the Allen School’s Diversity & Access team.

Portraits of Taylor Ka and Andrew Wei
Taylor Ka (left) and Andrew Wei

In addition to the awards to graduating students, the Allen School also commended half a dozen students who served as TAs in the past year with its Bob Bandes Memorial Awards for Excellence in Teaching. Service Award winner Eric Fan was among the Bandes Award recipients. Students appreciated Fan, who was a TA nine times, for being approachable and open to communication, including with those who took the course asynchronously: “Eric was a TA that contributed to my learning greatly, especially in a quarter that didn’t have the best circumstances surrounding it.”

One of Fan’s fellow Bandes Award winners, Taylor Ka, served as a TA for eight quarters of one of the courses in the introductory series, Computer Programming II. A faculty member called Ka, who earned her bachelor’s in computer science on the way to enrolling in the Allen School’s combined B.S./M.S. program,  “easily the best TA I have had across all courses at UW” and highlighted her knowledge, kindness, and approachability. A student recommended another award recipient, Andrew Wei, for his generosity and patience, and recalled how Wei would stay up late multiple nights per week to work with students who were struggling with assignments. Wei, who graduated from the B.S./M.S. program, assisted with no fewer than eight courses over 12 quarters.

The Allen School bestowed Bandes Award Honorable Mentions on three TAs: undergraduate Kyrie Dowling, and Ph.D. students Liang He and Edward Misback. Dowling, who has assisted with Systems Programming and The Hardware/Software Interface, stood out for her high energy, skillful explanation of concepts, and the fact that “it is very evident she cares about the learning of all of her students.” Meanwhile, He was recognized for his “positivity and creative encouragement” in supporting students in studio-oriented courses that typically feature physically-oriented lectures and coursework in the remote learning environment — including soldering, preparing and packaging more than 50 kits for delivery to students wherever they happened to be. Last but not least, Misback was recognized for guiding students through the “numerous technical pitfalls” of networking and web serving while encouraging them to discover solutions for themselves. As one faculty nominator suggested, “He will make an excellent teacher if he chooses that path.”

Portraits of Kyrie Dowling, Liang He, and Edward Misback
Left to right: Kyrie Dowling, Liang He and Edward Misback

This year’s Bandes Award honorees were selected from among 185 TAs nominated by faculty and students. A total of 670 students served as TAs during the academic year, assisting faculty and their fellow students to make the most of remote learning. Thanks in part to their efforts, an estimated 635 Allen School students earned their degrees in 2020-2021.

As she commended the graduates for achieving their educational goals, Balazinska noted this was not the end of their journey, but rather the beginning.

“Whatever your next steps are, an Allen School degree opens so many opportunities for you. I encourage you to be courageous. Continue to reach for the stars,” said Balazinska. “Go out and make your mark on the world. Every single one of you has what it takes to do great things.”

Congratulations to all of our graduates! We look forward to seeing what you do next — and to welcoming you back as alumni!

Editor’s note: Although the Allen School will award an estimated 635 degrees for the 2020-2021 academic year, only those students who opted into having their information displayed publicly are included in the online tribute.

June 18, 2021

Allen School’s Richard Anderson receives ACM Eugene L. Lawler Award for humanitarian contributions through computing

Portrait of Richard Anderson
Credit: Dana Brooks/University of Washington

Allen School professor Richard Anderson earned the ACM Eugene L. Lawler Award for Humanitarian Contributions within Computer Science and Informatics from the Association for Computing Machinery for his work bridging computer science, education and global health. Anderson, who co-directs the Information and Communication Technology for Development (ICTD) Lab, has devoted himself over the past two decades to advancing computing innovations that improve quality of life for people in rural and low-income communities around the globe.

After beginning his research and teaching career focused on theoretical computer science, Anderson embraced the opportunity to generate a tangible impact on underserved populations by helping to build up the emerging field of ICTD beginning in the early 2000s. One of his earliest contributions was to community-led education via the Digital StudyHall project, which brought high-quality teaching and interactive content to rural classrooms in India via facilitated video instruction. He subsequently teamed up with Seattle-based global health organization PATH on Projecting Health, an initiative aimed at using digital communications to help people in low-resource areas, including those with low literacy, to learn about and practice health-oriented behaviors to support maternal and child health. To date, Projecting Health has reached an estimated 190,000 people across 180 villages through local-produced videos addressing topics such as nutrition, immunization, and family planning.

“Through empowering community teams with this novel simplified filming and editing process to develop messaging for their own communities, Richard and our team achieved what rarely is achieved in global health — full ownership of a process by the very communities who would then use the output,” said Dr. Kiersten Israel-Ballard, the team lead for Maternal, Newborn, Child Health and Nutrition at PATH and an affiliate professor in the UW Department of Global Health. “As a global health specialist, it is rare to work with a visionary like Richard, who bridges fields and cultures to create innovative solutions. Our work is better having learned from him and his team.”

For the past six years, Anderson has led the development and deployment of open-source software tools for mobile data collection and analysis known as the Open Data Kit (ODK). Initially the brainchild of Anderson’s late friend and colleague Gaetano Borriello, ODK started out as a customizable survey tool designed to be “easy to try, easy to use, easy to modify and easy to scale.” Governments and non-profit organizations in more than 130 countries have relied on successive versions of ODK — including a second-generation version of the toolkit developed under Anderson’s leadership that enabled non-linear workflows and longitudinal surveys — to advance public health, wildlife conservation, election monitoring, essential infrastructure, and more. 

Shortly after taking the helm, Anderson and his collaborators managed the successful transition of ODK from a UW initiative to a stand-alone enterprise. Anderson and his team subsequently extended the original software’s capabilities with the release of ODK-X, which enables users such as PATH, the World Mosquito Program and the International Federation of Red Cross and Red Crescent Societies to build customized Javascript-based apps for managing and visualizing data in the field in addition to the traditional survey forms. Recent applications of ODK-X include vaccine cold-chain management, vector-borne disease monitoring, and humanitarian response.

Anderson has also led the charge to bring secure digital financial services to areas that lack access to traditional banking. In 2016, Anderson and other members of the ICTD Lab joined forces with the Allen School’s Security and Privacy Research Lab to launch the Digital Financial Services Research Group (DFSRG) with the goal of making financial products such as mobile payments and savings accounts more accessible to underserved communities. With funding from the Bill & Melinda Gates Foundation, the DFSRG addresses fundamental challenges to the development and large-scale adoption of digital financial products to benefit some of the lowest-income people in the world to enable them to participate in digital commerce and ensure that, in Anderson’s own words, “an event like an accident or a pregnancy doesn’t send them over the edge.” 

As one of the founding champions of the ICTD movement, Anderson has been instrumental in uniting various communities under the umbrella of ACM COMPASS — short for Computing and Sustainable Societies — and organizing conferences, workshops, and tutorials to engage more researchers, practitioners and students in this work. He has also been a vocal proponent of diversifying host countries to include conference sites such as Ecuador, Ghana and Pakistan. In conjunction with his research and community leadership, Anderson has been credited with demonstrating how to build effective collaborations between computer scientists and non-governmental organizations (NGOs). By combining the former’s technical expertise with the latter’s geographical and domain expertise, Anderson has forged partnerships that ensure solutions developed in the lab can be effectively deployed in the field by people without computing experience — and that they actually address the real-world problems of the people they aim to serve.

“Richard is a top-notch computer scientist and a more than capable teacher, but his real contribution is creating an environment in which CS innovation can be brought to bear on the real problems of real people in developing regions,” said Eric Brewer, a professor of computer science at the University of California, Berkeley who is also Fellow and VP Infrastructure at Google. “His work is inspiring to students across many disciplines, especially when they see the impact of his work on others.”

Anderson joined the Allen School faculty in 1986 after completing a postdoc at the Mathematical Sciences Research Institution in Berkeley, California. He earned his Ph.D. in computer science from Stanford University and his bachelor’s in mathematics from Reed College. Anderson is the first Allen School faculty member to receive the ACM Eugene L. Lawler Award, which is typically given once every two years in honor of an individual or group who has made a significant humanitarian contribution through the application of computing technology.

Read the ACM citation here, and learn more about the Eugene L. Lawler Award here.

Congratulations, Richard!

June 9, 2021

Allen School researchers discover medical AI models rely on “shortcuts” that could lead to misdiagnosis of COVID-19 and other diseases

Chest x-ray
Source: National Institutes of Health Clinical Center*

Artificial intelligence promises to be a powerful tool for improving the speed and accuracy of medical decision-making to improve patient outcomes. From diagnosing disease, to personalizing treatment, to predicting complications from surgery, AI could become as integral to patient care in the future as imaging and laboratory tests are today. 

But as Allen School researchers discovered, AI models — like humans — have a tendency to look for shortcuts. In the case of AI-assisted disease detection, such shortcuts could lead to diagnostic errors if deployed in clinical settings.

In a new paper published in the journal Nature Machine Intelligence, a team of researchers in the AIMS Lab led by Allen School professor Su-In Lee examined multiple models recently put forward as potential tools for accurately detecting COVID-19 from chest radiography (x-ray). They found that, rather than learning genuine medical pathology, these models rely instead on shortcut learning to draw spurious associations between medically irrelevant factors and disease status. In this case, the models ignored clinically significant indicators in favor of characteristics such as text markers or patient positioning that were specific to each dataset in predicting whether an individual had COVID-19. 

According to graduate student and co-lead author Alex DeGrave, shortcut learning is less robust than genuine medical pathology and usually means the model will not generalize well outside of the original setting.

Portrait of Alex Degrave
Alex DeGrave

“A model that relies on shortcuts will often only work in the hospital in which it was developed, so when you take the system to a new hospital, it fails — and that failure can point doctors toward the wrong diagnosis and improper treatment,” explained DeGrave, who is pursuing his Ph.D. in Computer Science & Engineering along with his M.D. as part of the University of Washington’s Medical Scientist Training Program (MSTP). 

Combine that lack of robustness with the typical opacity of AI decision-making, and such a tool could go from potential life-saver to liability.  

“A physician would generally expect a finding of COVID-19 from an x-ray to be based on specific patterns in the image that reflect disease processes,” he noted. “But rather than relying on those patterns, a system using shortcut learning might, for example, judge that someone is elderly and thus infer that they are more likely to have the disease because it is more common in older patients. The shortcut is not wrong per se, but the association is unexpected and not transparent. And that could lead to an inappropriate diagnosis.”

The lack of transparency is one of the factors that led DeGrave and his colleagues in the AIMS Lab to focus on explainable AI techniques for medicine and science. Most AI is regarded as a “black box” — the model is trained on massive data sets and spits out predictions without anyone really knowing precisely how the model came up with a given result. With explainable AI, researchers and practitioners are able to understand, in detail, how various inputs and their weights contributed to a model’s output.

Portrait of Joseph Janizek
Joseph Janizek

The team decided to use these same techniques to evaluate the trustworthiness of models that had recently been touted for what appeared to be their ability to accurately identify cases of COVID-19 from chest radiography. Despite a number of published papers heralding the results, the researchers suspected that something else may be happening inside the black box that led to the models’ predictions. Specifically, they reasoned that such models would be prone to a condition known as worst-case confounding, owing to the paucity of training data available for such a new disease. Such a scenario increased the likelihood that the models would rely on shortcuts rather than learning the underlying pathology of the disease from the training data.

“Worst-case confounding is what allows an AI system to just learn to recognize datasets instead of learning any true disease pathology,” explained co-lead author Joseph Janizek, who, like DeGrave, is pursuing a Ph.D. in the Allen School in addition to earning his M.D. “It’s what happens when all of the COVID-19 positive cases come from a single dataset while all of the negative cases are in another.

“And while researchers have come up with techniques to mitigate associations like this in cases where those associations are less severe,” Janizek continued, “these techniques don’t work in situations you have a perfect association between an outcome such as COVID-19 status and a factor like the data source.” 

The team trained multiple deep convolutional neural networks on radiography images from a dataset that replicated the approach used in the published papers. They tested each model’s performance on an internal set of images from that initial dataset that had been withheld from the training data and on a second, external dataset meant to represent new hospital systems. The found that, while the models maintained their high performance when tested on images from the internal dataset, their accuracy was reduced by half on the second, external set — what the researchers referred to as a generalization gap and cited as strong evidence that confounding factors were responsible for the models’ predictive success on the initial dataset. The team then applied explainable AI techniques, including generative adversarial networks (GANs) and saliency maps, to identify which image features were most important in determining the models’ predictions. 

Figure from paper showing three x-ray images paired with color-coded saliency maps indicating weight of factors in model prediction
The team used explainable AI to visualize the image factors that influenced neural network models’ predictions of COVID-19 status based on chest radiography. Here, saliency maps reveal the models’ tendency to emphasize diagnostically irrelevant features such as laterality tokens, image corners or the patient’s diaphragm in addition to — or instead of — the lung fields when making their predictions.^

When the researchers trained the models on the second dataset, which contained images drawn from a single region and was therefore presumed to be less prone to confounding, this turned out to not be the case; even those models exhibited a corresponding drop in performance when tested on external data. These results upend the conventional wisdom that confounding poses less of an issue when datasets are derived from similar sources — and reveal the extent to which so-called high-performance medical AI systems could exploit undesirable shortcuts rather than the desired signals.

Despite the concerns raised by the team’s findings, DeGrave said it is unlikely that the models they studied have been deployed widely in the clinical setting. While there is evidence that at least one of the faulty models – COVID-Net – was deployed in multiple hospitals, it is unclear whether it was used for clinical purposes or solely for research.

“Complete information about where and how these models have been deployed is unavailable, but it’s safe to assume that clinical use of these models is rare or nonexistent,” he noted. “Most of the time, healthcare providers diagnose COVID-19 using a laboratory test (PCR) rather than relying on chest radiographs. And hospitals are averse to liability, making it even less likely that they would rely on a relatively untested AI system.”

Janizek believes researchers looking to apply AI to disease detection will need to revamp their approach before such models can be used to make actual treatment decisions for patients.

“Our findings point to the importance of applying explainable AI techniques to rigorously audit medical AI systems,” Janizek said. “If you look at a handful of x-rays, the AI system might appear to behave well. Problems only become clear once you look at many images. Until we have methods to more efficiently audit these systems using a greater sample size, a more systematic application of explainable AI could help researchers avoid some of the pitfalls we identified with the COVID-19 models,” he concluded.

Janizek, DeGrave and their AIMS Lab colleagues have already demonstrated the value of explainable AI for a range of medical applications beyond imaging. These include tools for assessing patient risk factors for complications during surgery, which appeared on the cover of Nature Biomedical Engineering, and targeting cancer therapies based on an individual’s molecular profile, as described in a paper published in Nature Communications.

Su-In Lee holding pen with coffee mug and laptop
Su-In Lee

“My team and I are still optimistic about the clinical viability of AI for medical imaging. I believe we will eventually have reliable ways to prevent AI from learning shortcuts, but it’s going to take some more work to get there,” Lee said. “Going forward, explainable AI is going to be an essential tool for ensuring these models can be used safely and effectively to augment medical decision-making and achieve better outcomes for patients.”

The team’s paper, “AI for radiographic COVID-19 detection selects shortcuts over signal,” is one of two from the AIMS Lab to appear in the current issue of Nature Machine Intelligence. Lee is also the senior and corresponding author on the second paper, “Improving performance of deep learning models with axiomatic attribution priors and expected gradients,” for which she teamed up with Janizek, his fellow M.D.–Ph.D. student Gabriel Erion, Ph.D. student Pascal Sturmfels, and affiliate professor Scott Lundberg (Ph.D., ‘19) of Microsoft Research to develop a robust and flexible set of tools for encoding domain-specific knowledge into explainable AI models through the use of attribution priors. Their framework supports the widespread adoption of techniques that will improve model performance and increase computational efficiency in AI for medicine and other areas of applied machine learning. 

Also see a related GeekWire article here.

* Image sourced from the National Institutes of Health (NIH) Clinical Center and used with permission: Wang, X. et al. “ChestX-ray8: Hospital-scale chest X-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2017.

^ Figure 2a (bottom) adapted with permission from Winther, H. et al. COVID-19 image repository. figshare.

June 1, 2021

Anna Karlin receives ACM Paris Kanellakis Theory and Practice Award

Collage of award recipients' portraits with ACM logo
Top, from left: Yossi Azar, Andrei Broder and Anna Karlin; bottom, from left: Michael Mitzenmacher and Eli Upfal

Professor Anna Karlin and a team of collaborators have received the ACM Paris Kanellakis Theory and Practice Award from the Association for Computing Machinery for their work on balanced allocations, also known as the “power of two choices.” Karlin, a member of the Allen School’s Theory of Computation group, first introduced the balanced allocations paradigm with co-authors Yossi Azar of Tel Aviv University, Andrei Broder of Google Research, and Eli Upfal of Brown University at the 1994 ACM Symposium on Theory of Computing (STOC) in what the ACM has described as “elegant theoretical results” that continue to have a demonstrable impact on the practice of computing. 

The team’s paper considers a basic “balls-in-bins” problem: It has long been known that when n balls are tossed one at a time into n bins, independently and uniformly at random, the expected value of the maximum load is about log(n)/loglog(n). Karlin and her colleagues showed that balancing the allocation of the balls by first selecting not one, but two bins at random, and then placing the ball in the bin that has the lesser load between the two reduces the expected maximum load across all the bins to loglog(n) — an exponential improvement.

Fellow honoree Michael Mitzenmacher of Harvard University later significantly extended these initial results.

“Since bins and balls are the basic model for analyzing data structures, such as hashing or processes like load balancing of jobs in servers, it is not surprising that the power of two choices that requires only a local decision rather than global coordination has led to a wide range of practical applications,” the ACM observed in a press release. “These include i-Google’s web index, Akamai’s overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox, which are all based on variants of the power of two choices paradigm.”

Karlin’s Allen School colleague, Paul Beame, recalls that it was “stunning and unexpected” that such a simple change in the algorithm would yield such a dramatic improvement — one that has proven to have an enduring impact within the field.

“One can easily ensure balanced allocations if one has prior knowledge about the pattern of requests or some form of centralized control but, without that, finding good balance becomes difficult. The typical solution before the work of Anna and her co-authors allocated each request based on a single random choice of a resource. However, unless the system is vastly over-provisioned, this will result in a somewhat bad overall imbalance,” explained Beame. “What Anna and the team showed is that a simple adjustment — making two random choices rather than just one, and keeping the better of the two — results in an exponential improvement in the overall balance, effectively at most a small constant for all reasonable data sizes.

“In the last couple of decades, their paper has led to much follow-on research,” Beame noted. “The ‘power of two choices’ has since become one of the essential new paradigms in the design of dynamic data structures and algorithms and is regularly taught in graduate courses worldwide.”

Prior to winning the ACM Paris Kanellakis Award, Karlin recently became the first Allen School faculty member to be elected to the National Academy of Sciences for career contributions to algorithms and algorithmic game theory. She is one of two Allen School faculty members to be recognized with ACM technical awards this week, as Shyam Gollakota received the ACM Grace Murray Hopper Award for his work on wireless sensing and communication. 

Read the ACM announcement here, and learn more about the Paris Kanellakis Theory and Practice Award here.

Congratulations, Anna!

May 26, 2021

Older Posts »