Henry Kautz - US grants

Principles of Efficient Inference



This is the first year funding of a three year continuing award. This project seeks to uncover fundamental principles for the construction of real-time AI systems that employ declarative knowledge representations and general reasoning engines. To achieve this goal, the PI will (a) study the "fine grained" structure of problem hardness based on notions coming out of work on phase transitions in random problem distributions; (b) develop faster complete and incomplete reasoning engines, including systems that employ decision-theoretic control of reasoning; and (c) apply and test the new algorithms to planning problems in a robotics testbed. This research will lead to the creation of useful new algorithms for solving hard combinatorial problems in areas such as knowledge-based expert systems, autonomous systems, and operations research. The results will also promote interdisciplinary work on logic and reasoning in the AI, theory, OR, robotics, and verification communities.

The problem of developing efficient automated systems of logical
inference is a key step toward the dream of creating verifiable,
reliable, and secure hardware and software systems. This research is
aimed at developing a well-founded, unified theory of practical
logical inference, that combines complementary ideas and powerful
approaches for propositional inference developed in AI, formal
verification, and theoretical computer science.

This unified theory will focus on (ii) combining the different
representations used in the various approaches to propositional
inference, such as Boolean decision diagrams and conjunctive normal
form, in order to take advantage of the diverse algorithmic techniques
associated with each; (ii) developing new and improved inference
algorithms using the combined representation; (iii) precisely
characterizing the power of various heuristic inference techniques,
such as clause learning and randomized search; and (iv) developing a
rigorous understanding of how problem structure indicates the
potential effectiveness of particular inference strategies.

The research will involve theoretical work using methods of proof
complexity as well as experimental work on logical encodings of both
real-world verification problems and AI planning problems. The
ultimate goal research is to significantly expand the size and
complexity of software and hardware systems that are amenable to
formal analysis.

This small grant for exploratory research will support development of novel computer systems that will enhance the quality of life of people suffering from Alzheimer's Disease and similar cognitive disorders. Assisted Cognition systems use ubiquitous computing and artificial intelligence technology to replace some of the memory and problem-solving abilities that have been lost by an Alzheimer's patient. Assisted Cognition systems: sense aspects of an individual's location and environment, both outdoors and at home, relying on a wide range of sensors such as Global Positioning Systems (GPS), active badges, motion detectors, and other ubiquitous computing infrastructure; learn to interpret patterns of everyday behavior, and recognize signs of distress, disorientation, or confusion, using techniques from state estimation, plan recognition, and machine learning; offer help to patients through various kinds of interventions including speech and natural language processing; and alert human care-givers in case of danger.

Two concrete examples of the Assisted Cognition systems that will be developed are an activity compass that helps reduce spatial disorientation both inside and outside the home, and an adaptive prompter that helps patients carry out multi-step everyday tasks. This project will explore an emerging area that could be of great humanitarian, commercial, social, and scientific importance in the coming decades.

This project will develop a hybrid method for rigorously observing structures of social interaction over time, and validate this method by comparison with conventional survey and observation designs. It will use both wearable and fixed computer devices to collect streaming data on research participants' physical location, speech, and motion, and then will develop computational models to infer structures of social interaction from these data. This suite of tools will thus allow direct automated measurement of networks of face-to-face interaction over time. Having demonstrated and validated this approach, the project will illuminate a set of classic theoretical problems that have eluded rigorous analysis under conventional methods. Substantial advances in modeling the dynamics of social networks have been frustrated by the paucity of appropriate data for empirical investigation, as scholars must often address dynamic theories using cross-sectional or sparse panel data.

The team of investigators includes experts from both Computer Science and Sociology, integrates tools from both fields, and addresses questions that would be intractable without this interdisciplinary lens. For example, the precise measurement of interaction in time and space allows researchers to observe the co-evolution of social roles (as performed by individuals in day-to-day interaction) and structural positions in a social network. The streaming measures of social interaction allow a detailed analysis of conversations, analyzing how styles of communication change within social relationships over time, including the effect of structural position on styles of interaction and the effect of interaction style on position in the network.

The research will examine the simple evolution of social networks over short (weeks) and long (month and/or years) time scales. Using Global Positioning Systems and various other location sensor technologies, the work will contribute an explicitly spatial investigation of network dynamics, modeling the interplay of the physical environment and social networks. For example, particular locations may serve as hubs or bridges, connecting otherwise disparate network components. Results may refine scientific understanding of the co-evolution of social networks and physical locations.

The project will develop a set of methods for social network observation and analysis, generate datasets of unprecedented breadth and depth, and provide an independent standard for comparison of conventional tools, all of which will be invaluable resources for the broader scientific community. The resulting longitudinal network datasets are likely to be mined for insights into social network dynamics by many other researchers, while the team of graduate students working under this project will benefit from unique interdisciplinary training. Beyond basic research, the novel application of sensor-based and machine learning methods to understanding human communication has broad applicability to real-world social problems. As a simple example, a refined understanding of the co-evolution of networks and physical locations may provide insight into macro-level processes of community integration and disintegration, informing social architects and urban planners. The project will promote teaching, training and understanding among researchers in computer science and social science.

Proposal 0535126
"Learning High-level Models of Human Behavior from Low-level Sensor Data"
PI: Henry Kautz
University of Washington

ABSTRACT

The goal of this project is to create systems that can interpret and understand day to day human experience. Achieving this goal will support many practical applications with broad social impact, including developing assistive technology for the disabled, creating models of patterns of human interaction for use in the social sciences, and creating new kinds of just-in-time information systems for business and personal use. There are three main themes to this research. First is work in knowledge representation on the structure of goals, plans, and actions. This project is concerned not just with plan synthesis, but also with supporting reasoning about the intentional basis of human action. Second is work on probabilistic reasoning, because any method for interpreting human behavior is necessarily fraught with uncertainty. This work draws upon and extends recent approaches on using model-counting algorithms for probabilistic inference, and methods for combining probability theory with first-order logic. Third is work on ubiquitous sensing: the idea that data from large numbers of simple, inexpensive sensors that directly measure properties of the world can be used to replace or augment complex input modalities such as machine vision or natural language understanding.

DESCRIPTION (provided by applicant): We propose to develop a general task prompting and reminding system that runs on an ordinary cell phone for persons with cognitive disabilities. The system will use information from a variety of sensors to determine the user's activity and context, so that prompts are less disruptive and more appropriate. The proposed development builds up research at the University of Rochester on human activity recognition from sensor data, commercial development at Attention Control Systems on handheld prompting systems for individuals with impaired executive function, and work at the University of Washington on technology supports for persons with cognitive disabilities. The system will be the first general task prompting and reminding system that can provide context- dependent prompts, assistance with task re-scheduling, and be adaptable to a variety of different activities of daily living. In our preliminary work, we created a proof-of-concept prototype that demonstrated that sensor information from touch and motion sensors could be communicated to the handheld system and used to infer when the user performs common activities such as meal preparation, and that this activity information can be used to modify scheduled prompts. For example, the system would suppress the prompt for the user to begin meal preparation if the system recognizes that the user has already begun that activity. Our proposed development will make the system so robust, general, and easy to use that it could be evaluated in trials with real users in ordinary home environments. Our proposed effort includes a needs assessment with potential users and caregivers, development of the system interfaces for the users and caregivers as well as making the system's reasoning software more general and robust, and initial short and longer term small group evaluations of usability and effectiveness. The final system will provide a tool for investigating many research questions on the ability of technology to support independence by persons with cognitive disabilities. PUBLIC HEALTH RELEVANCE: We propose to develop a general task prompting and reminding system that runs on an ordinary cell phone for persons with cognitive disabilities. The system will use information from a variety of sensors to determine the user's activity and context, so that prompts are less disruptive and more appropriate. This system will provide a tool for investigating many research questions on the ability of technology to support independence by persons with cognitive disabilities.

This project addresses a key problem in advancing the state of the art in cognitive assistant systems that can interact naturally with humans in order to help them perform everyday tasks more effectively. Such a system would help not only people with cognitive disabilities but all individuals as they perform complex tasks they are unfamiliar with. The research focuses on structured activities of daily living that lend themselves to practical experimentation, such as meal preparation and other kitchen activities.

Specifically, the core focus of the research is activity recognition, i.e., systems that can identify the goals and individual actions a person is performing as they work on a task. Key innovations of this work are 1) that the activity models are learned from the user via intuitive natural demonstration, and 2) that the system is able to reason over activity models to generalize and adapt them. In contrast, current practice requires specialized training supervised by the researchers and supports no reasoning over the models. This advance is accomplished by integrating capabilities that are typically studied separately, including activity recognition, knowledge representation and reasoning, natural language understanding and machine learning. The work addresses a significant step towards the goal of building practical and flexible in-home automated assistants.

Current techniques for answering questions about the influence of behaviorial and environmental factors on public health are based on surveys, which are costly and subject to response bias, or simulations, which rely on possibly incorrect or simplistic assumptions. The TwitterHealth project is developing techniques to extract reliable public health information from social media. In essence, the online population becauses a vast organic sensor network. Statistical natural language processing techniques are employed to classify tweets (or other social media postings) as self-reports of disease or particular behaviors of interest. GPS information included in postings made from cell phones allow a variety of behavioral information to be inferred about each user, such as the venues visited and the other individuals from the data set who are encountered.

Major technical challenges for using social media in this manner are the highly noisy nature of the information channel, scaling to a large number of different health conditions, and the need to discover causal influences as well as correlations between behavioral and environmental factors and health. The challenge of noise is approached by learning dynamic relational models of health states, which generalize classical epidemiological models but support individual as well as aggregate predictions. The scaling challenge is dealt with by knowledge transfer techniques, which reduce data and computational requirements by transfering information between models for different health conditions. Specific knowledge transfer techniques are cascaded training of a target classifier starting with a given classifier for a related but different disease, and the use of ensembles of general and specific classifiers. The challenge of inferring casuality is addressed by temporal-lag methods, which identify changes in behaviorial or environmental conditions that consistently precede changes in health. For example, the inference that a venue is a cause (vector) of disease spread is accomplished by tracing backward in time the GPS trails of users who post social media reports of illness. TwitterHealth employs two approaches for validating its results: first, comparing the aggregate predictions of the model against CDC statistics; second, comparing individuals' behavior in reporting or not reporting disease symptoms in status updates against the behavior predicted by the models. The project also includes planning for clinic based evaluations, in which subjects identified by their social media postings would provide swabs that would be tested for disease agents.

The TwitterHealth approach to collecting and analyzing health information has the potential to improve public health, by making detailed data about health, behavior, social structure, and geographic influences available in real time and at almost no cost. While it will not completely replace traditional methods of gathering health information, it provides an important complementary information channel, which emphases speed, reach, and scale. The project includes outreach expert medical professionals in order to plan future clinical validation. The outreach interaction provides a forum for exchange of computer science and medical expertise between researchers and students in the two fields. Information about the project is available online at http://www.cs.rochester.edu/u/kautz/twitterhealth.

In West African countries, cell phone penetration can range from 40 to 80% and upwards, with over 2 million Android devices in Sierra Leone, Guinea, and Liberia alone. The investigators propose the delivery of a smartphone application that will improve care-seeking, epidemiology, and prevention by monitoring civilian location patterns, habits (e.g. walking, sleeping), and resource needs (e.g. hand sanitizers or gloves). This project addresses three key problems. First, how well can smartphones sensors support real-time monitoring and prediction of the scale of an infectious disease (in this case Ebola) compared to stochastic epidemiology models? Second, how can smartphone communications be used to educate a population about prophylactic behaviors and change such behaviors? Third, is mHealth (mobile health) sustainable in West Africa, or is the infrastructure too underdeveloped to support such innovations over the long term? Our project is novel in that it uses passively obtained location information, sensor data, and dynamic surveys to understand the health and potential for infection among the population in real time to supplement CDC, WHO and UN efforts.

This RAPID proposes to seek to use machine learning to classify data obtained from phone sensors (e.g. location in a village with high disease rate, reduced movement, self-photo of rashes) along with survey questions to determine if users are developing symptoms that may be similar to Ebola. The project will also look at human mobility patterns compared to stochastic epidemiological models to determine the efficacy of real-time cell phone tracking. The coupling of these sensor modalities will be used to model users as a noisy sensor and compare how this information agrees or predicts historical trends. Finally, the project will use features of behavioral science to explore what feedback does to affect user behavior, such as, knowing about their risk for Ebola.

Understanding the cognitive and neural basis of human behavior is one of the most fundamental areas of scientific inquiry for the 21st Century. It will impact almost every facet of human existence, including commerce, education, health care, and national security, as well as basic science. This National Science Foundation Research Traineeship (NRT) award prepares Ph.D. students at the University of Rochester to advance discoveries at the intersection of computer science, brain and cognitive sciences, and neuroscience. Trainees will be prepared to harness the burgeoning power of data science to make novel inroads into understanding the neural foundations of human behavior. Trainees will learn to be equally comfortable applying these skills in industrial and academic settings. By emphasizing both practical applications and basic science, this program will prepare trainees to develop research solutions relevant to today?s societal needs as well as develop research approaches of critical importance to future needs.

Focusing on understanding the nature of intelligence, this program will provide students with skills to blend expertise in data science and computer science with a deep understanding of experimental approaches to collecting and analyzing neural and behavioral data. The program will use theories and methods from data science including machine learning and statistics to provide students with a foundation for theory development, computational modeling, and data analysis. This foundation will serve as a conceptual and methodological framework unifying their studies of artificial and biological intelligence. The hands-on, project-oriented nature of this program will provide students with the capabilities needed to conceptualize, design, and implement large-scale research projects from beginning to end. This traineeship provides a novel model for structuring interdisciplinary education, based on a modular cross-training course followed by an interdisciplinary practicum course, which can be replicated in many fields and universities.

How can a computer learn to read an ancient musical score? What can methods from signal processing and natural language analysis tell us about the history of popular music? Can a computer system teach a person to better use prosody (the musical pattern of speech) in order to become a more effective public speaker? These are some of the questions that students will investigate in the University of Rochester's Research Experience for Undergraduates (REU) site. Students will explore an exciting, interdisciplinary research area that combines computer science, electrical engineering, cognitive science, and music. Each student will be mentored by two or more faculty members from the University's schools of engineering and music. Other activities of the REU site include workshops on career development; scholarship community colloquiums; Python programming for machine learning; and music-focused activities. The goals of this REU are to increase the diversity and broaden the horizons of students engaged in computer science research. The themes of music, digital media, and cognitive science will attract many students from groups under-represented in computer science. Students who are already majoring in computer science will discover that the research in the field is not limited to traditional engineering applications, but can address questions of art, culture, and human psychology. Students with experience in combining computer science with humanistic research are already in great demand in industry and academia, and will help define what it means to be a computer scientist in the 21st century.

Students in the University's REU will engage in interdisciplinary research that combines machine learning, audio engineering, music theory, and cognitive science. These disciplines are united by their use of a common set of formal representations and computational methods; in particular, probabilistic models and machine learning. In the research activity, REU students will work on topics such as using machine learning and wide-spectrum imaging to recover lost ancient musical scores; working with cognitive scientists to understand how prosody makes a person a convincing public speaker; and developing algorithms for synchronizing hundreds of audio and video streams of an event to reconstruct the experience of live music performances. The University of Rochester's Department of Computer Science has a long history of contributions in machine learning, natural language processing, and computer vision, and the Department of Brain and Cognitive Science is in the top three nationally. The University's recently-founded audio engineering program is growing rapidly, and the Eastman School of Music is the nation's premiere music conservatory. Although the major objective of the REU is to encourage students to enter STEM graduate programs, many of the projects can be expected to lead to novel and publishable research in machine learning and audio processing.