Tom Michael Mitchell - US grants

This project covers research activities in two areas of Artificial Intelligence: knowledge-based expert systems and machine learning. One research thrust focusses on developing a knowledge-based consultant system to aid in the design of digital VLSI circuits. This research involves extending current methods for developing rule-baszed expert systems, by applying them to design tasks, and by integrating rule- based methods with algorithmic methods for dealing with different aspects of the design task. The second research area, machine learning, has focussed on developing the LEX system which learns problem-solving heuristics by generating and solving practice problems. This research has led to development of a domain-independent technique (goal-directed learning) for generalizing from examples. Research on machine learning over the coming year will include an attempt to apply these techniques to the task of learning rules for VLSI design.

This Symposium entitled, Mind Matters, held at Carnegie Mellon University on October 25-27, 1992 features unpublished papers of a technical nature describing original research in the areas of computer science and cognition. It is held in honor of Allen Newell, who has made seminal contributions to computer science and cognitive science . He is generally regarded as one of the founding fathers of the field of artificial intelligence. Dr. Newell s research for the past decade has focussed on the development of SOAR, as both an integrated architecture for building intelligent systems and as a unified theory of cognition. Soar is the unifying thread for this symposium. A member of the Soar community follows each invited speaker s talk, discussing the implications of the results just presented for the Soar architecture. The speakers, leading scholars in computer science and cognitive research, and their topics are chosen to reflect the diversity of Professor Newell s interests. The proceedings of the symposium are to be published as a book by Lawrence Erlbaum Publishers, as part of their Carnegie Symposium on Cognition series.

This research seeks to combine the two primary paradigms for machine learning: inductive and analytical learning. Inductive methods such as instance-based and neural network learning can reliably learn simple functions from noisy data, but require vast numbers of training examples in order to scale up to very complex functions. In contrast, analytical methods such as explanation-based learning can learn complex functions from much less data, but rely upon strong prior knowledge on the part of the learner. Much current research in machine learning seeks to combine the best of both approaches, to obtain methods that learn more correct generalizations from approximate prior knowledge together with observed data. The proposed research takes a novel approach to this problem: unifying neural network learning and explanation- based learning. More specifically, this research will build on the recently developed explanation-based neural network (EBNN) learning method. Preliminary research has demonstrated experimentally that EBNN can generalize better from fewer examples than pure inductive learning if accurate domain knowledge is available, and that it degrades gracefully with the quality of the learner's prior knowledge. This research will explore more fully the space of combined neural net and explanation-based methods, focusing on issues such as scaling up to more complex learning tasks, alternative types of information that can be extracted from explanations based on neural networks, operating robustly over the entire spectrum from very strong to very weak prior knowledge, and alternative representations for the domain theory and target function. EBNN learning will be applied to two different task domains. If successful, this research could produce learning methods that scale up to more practical problems, and lead to a clearer understanding of the correspondence between symbolic and neural network approaches.

This project is being funded through the Learning and Intelligent Systems (LIS) Initiative, with funds partially provided by the MPS/OMA office. Scientific and engineering data now come in large amounts and in new forms. Although the problem of analyzing and learning from purely numerical data has been heavily studied, we currently lack principled methods for analyzing the multiple-media data sets that form the basis of many modern empirical studies. These modern data sets contain a mixture of numerical features, symbolic logic descriptions, images, text, sound, and other media. This project offers an interdisciplinary research effort to create the statistical foundations and practical machine learning algorithms needed to take advantage of the growing number of such multiple-media data sets. The research plan is to develop new approaches to this problem by working with several large-scale multiple-media databases of significant scientific and societal importance. This research will provide the theoretical foundations and practical algorithms for analyzing multiple-media data in a broad range of application domains. For example, many medical institutions now collect detailed patient records that can be analyzed to predict treatment outcomes for future patients. These medical records are typically multiple-media records consisting of numerical features (e.g., temperature), symbolic features (e.g., gender), images (e.g., x-rays), other instrument data (e.g., EKG), text (e.g., physicians' notes), and other data. Current data analysis algorithms simply ignore most of these available features, because we lack well-understood methods for analyzing such multiple-media data. The current research seeks to develop new approaches that will be able to utilize the full information collected in such data sets. The goal is to extend the foundations of data interpretation that form the basis for many experimental sciences and engineering disciplines.

This award provides partial support for a cluster of eight workshops centered around automated learning and decision making based on data. The meeting is held at Carnegie Mellon University on June 11-13, 1998. It covers scientific research at the intersection of statistics, computer science, artificial intelligence, databases, social sciences and language technologies. The aim of this meeting is to initiate a dialogue between these disciplines. By doing do, it seeks to attain two types of impacts. First, it aims to generate synergy between previously separated fields, to lead to new, cross-disciplinary research collaborations and new, unified research approaches. Second, it attempts to provide guidance to the scientific community by characterizing the state-of-the-art, pointing out possible overlaps, making people aware of research results in other fields, and identifying some of the most promising cross-disciplinary research directions. One of the results of this meeting will be a written report, which will be made available to NSF and the scientific community at large, by posting it on the Web, and by submitting it to a widely accessible magazine or journal.

This collaborative project brings together a strong multi-institutional interdisciplinary team of investigators to study and advance the current understanding of cellular and sub-cellular events. Continuing technological advances in fluorescence and atomic-force microscopy allow scientists to observe molecular function, distribution, and interrelationships in living cells. However, a full understanding of tens of thousands of proteins and the complex molecular processes they engage in requires a voluminous amount of image data, which currently must be analyzed by visual inspection. To facilitate such an analysis, researchers from the four participating institutions are focusing on three main research thrusts. First, next-generation intelligent imaging involves information processing at the sensor level to enable high-speed and super-resolution imaging. The goal is to enable biologists to study cellular processes at resolutions in time and space that are not possible with current technologies. The second research thrust is pattern recognition and data mining as applied to bio-molecular image collections. Salient features that characterize the underlying patterns in cells and tissues need to be computed for the vast volumes of images acquired through automated microscopy. Third, a distributed database of bio-molecular images is being created. The merging of pattern-recognition and data-mining tools with new, powerful methods for indexing, data modeling, and collaboration, is aimed at creating a unique infrastructure that greatly facilitates image bioinformatics, thus complementing recent revolutionary advances in genomics.

The outcome of this research will lead to new and novel information-processing methods for bio-molecular image data. Efficient and effective representation of such data will enable researchers to search and browse through large collections of image and video data and look for similar patterns in such datasets, thus facilitating information discovery. During its five-year duration, this project will develop, test, and deploy a distributed database of bio-molecular image data accessible to researchers around the world. The impact of the distributed database will be through large-scale biology in which the results of a single experiment can be globally correlated with the results from other groups of scientists, thus accelerating discovery of dynamic relationships between structure and function in complex biological systems.

The project will develop new courses, and will facilitate student exchanges, semi-annual meetings, and workshops, benefiting students at all levels. This project will train a new generation of biologists, computer scientists and engineers well versed in the imaging and information-processing sciences at the forefront of next-generation biotechnology. Partnership will be established with institutions with large populations of students from groups underrepresented in science and engineering, such as the California State Universities at Fresno and San Bernardino and the Universidad Metropolitan in Puerto Rico, for undergraduate recruitment and outreach. An effective mode of outreach for students is to educate their teachers, and the project will offer summer fellowships for elementary, high-school, college, and university teachers.

Using machine learning and cognitive modeling to understand the fMRI-measured
brain activation underlying the representations of words and sentences

Tom M. Mitchell and Marcel A. Just

Project Abstract

A number of recent fMRI studies have reported significant and repeatable differences in fMRI brain activation when human subjects perceive pictures or words describing objects from different semantic categories (e.g., pictures or words that describe tools, buildings, or people). It is currently possible to determine with good accuracy which of several semantic categories a person is thinking about, based on their brain activation.

We propose new research that builds on these recent discoveries, and seeks to understand (1) human brain activity associated with different semantic categories of objects and actions (nouns and verbs); (2) whether the brain activity associated with semantic categories can be partitioned into more primitive semantic components (e.g., does the brain activity associated with words about tools factor into one component characterizing the tool's visual appearance and a second component characterizing the motor actions involved in using the tool?); and (3) how brain activity associated with individual words is combined into more complex patterns when reading word pairs or simple phrases and sentences.

This research involves:(1) applying machine learning algorithms to discover cortex-wide brain activation patterns associated with particular semantic domains, (2) developing a computational model of human language processing that instantiates the representational principles discovered and that makes specific, testable predictions, and (3) conducting new fMRI studies to obtain novel data about human semantic category representations.

The intellectual merit of the proposed research is multifaceted. If successful, our research will lead to new scientific insights into how the brain organizes information about meanings of words, objects, and actions. It will also lead to new methods for fMRI data analysis, especially for discovering complex temporal-spatial patterns of fMRI activation that accurately distinguish different mental states. The research will also lead toward a new paradigm for developing computational cognitive models and fitting them to empirical data obtained from fMRI and from behavioral measures.

The broader impacts of the proposed research will be amplified by specific outreach activities to several communities. In addition to publishing our scientific results in the cognitive and computational neuroscience literature, we will also actively engage this community by disseminating our new experimental fMRI data through the NSF-funded fMRI Data Center, and by documenting and publishing our new data analysis algorithms on the internet. We will proactively engage the statistical machine learning community, which has much to contribute to development of new fMRI analysis methods, and will develop and disseminate teaching materials for the undergraduate and graduate educational community,including fMRI data sets. Finally, our proposed research has potential impact on the medical research community, especially regarding the study of neurological conditions such as Alzheimer's disease, dyslexia and high-functioning autism - three areas entailing a language disturbance in which we already have active research collaborations, providing a direct conduit for transferring new scientific insights that may arise from this research.

This project seeks to develop a new understanding of how the brain represents and manipulates meaning, by bringing together the perspectives of brain imaging, machine learning and computational modeling, using converging approaches from behavioral psychology, linguistics, computer science and neuroscience. In particular, the brain activity that encodes the meanings of words, phrases and sentences is studied, along with how the brain encodes the meaning of individual words in terms of their component semantic features, how it modifies its encoding of an individual word when it occurs within a phrase or clause, and how it constructs the encoding of a phrase or clause from the encodings of its component words. This work builds on recent research showing (1) that repeatable patterns of fMRI activation are associated with viewing nouns describing concrete objects such as "hammer" or "toe," (2) that the neural patterns that encode the meanings of these words are similar across different people, and (3) that these encodings are similar whether the person views a word or a picture of the object. Whereas previous work has focused on the neural representation of single words in isolation, this project studies multiple word phrases and sentences, which comprise larger units of knowledge; for example how the neural encoding of a noun is influenced by its adjective (e.g., "fast rabbit" vs. "cuddly rabbit") and how the neural encoding of a proposition is related to the encodings of its component words (how "cut" and "surgeons" combine in the proposition "surgeons cut"). To address these questions, computational models are developed using a diverse set of training data including fMRI data, data from a trillion-word corpus of text that represents typical language use, and behavioral data from language comprehension and judgment tasks, as well as online linguistic knowledge bases such as VerbNet, and theoretical proposals from the cognitive neuroscience literature regarding how and where the brain encodes meaning. These perspectives are integrated into a theory in the form of a computational model trained from diverse data and prior knowledge, and capable of making experimentally testable predictions about the neural encodings and behavioral responses associated with tens of thousands of words, and hundreds of thousands of phrases and sentences.

This project potentially constitutes a significant scientific advance in understanding the relation between brain and mind, impacting a variety of scientific disciplines involved in the study of semantics, including linguistics, psychology, philosophy and cognitive science. A second impact comes from use of the methods and results to understand brain pathologies that involve language disturbances, such as aphasia, dyslexia, and autism. A third impact comes from the development of new statistical machine learning algorithms for analyzing and modeling cross-domain data sets to aid in scientific discovery. Finally, the emerging results and methods will have an educational impact through courses on Brain Imaging, Machine Learning, and Psychology taught by the Principal Investigators, and through a new course to be developed specifically on the topic of "Neural representations of meaning," with materials to be made available on the web.

This subproject is one of many research subprojects utilizing the resources provided by a Center grant funded by NIH/NCRR. The subproject and investigator (PI) may have received primary funding from another NIH source, and thus could be represented in other CRISP entries. The institution listed is for the Center, which is not necessarily the institution for the investigator. We propose to use the facilities at PSC to support our research to study the brain activity that encodes the meanings of words and phrases in the human brain. Our approach involves developing a computational model that predicts the brain activity observed via fMRI when a person reads arbitrary nouns. The model is trained using statistics of word use collected from a trillion-token text corpus, together with gigabytes of fMRI data. It is both computationally intensive and data intensive, making the PSC facilities an excellent platform for our computational needs.

Human computation studies how to collect useful data as a by-product of another activity in which people are interested (e.g., playing games). A popular example is the ESP Game, where two players are shown the same image and must independently generate tags; tags that match become labels for the image. ESP Game players have generated millions of labels that help improve image search engines.

Currently, little is understood about how to capitalize on each person's individual expertise to produce the best results in human computation systems. For example, the ESP Game could generate better results if automotive enthusiasts labeled images of cars while biologists labeled images of animals. This project aims to better understand how each individual's different capabilities can be assessed, dynamically leveraged, and even improved for the purposes of human-driven data collection.

Intellectual Merit: Improved understanding of the strengths and weaknesses of human users as teachers and data sources; an intelligent new objective-driven model of data collection; novel opportunities to study machine learning algorithms that capitalize on human teachers' abilities; and an analysis of learning opportunities as incentives for people to participate in human computation systems.

Broader Impact: Distribution of large new data sets (e.g., Wikipedia articles in multiple languages); several Internet-based human computation systems for large-scale evaluation of machine learning and other algorithms; a new course called ?Human-in-the-Loop Systems?; workshops held in conjunction with major conferences; and outreach activities (e.g., summer projects) that introduce female undergraduate students to interdisciplinary research.

DESCRIPTION (provided by applicant): Over the past ten years a good deal has been learned from fMRI studies about the spatial patterns of neural activation used by the human brain to represent meanings of words and concepts. Much less is understood about the time evolution of this neural activity, including the temporally interrelated sub-processes the brain employs during the hundreds of milliseconds it takes to comprehend a single word, or the more complex processes it uses to construct and encode meaning of entire sentences as the words arrive one by one. We propose research to study, and to build computational models of, the detailed spatial and temporal neural activity observed during the comprehension of single words, phrases, sentences, and stories. This proposed research will specifically target the following questions: What information is encoded by neural activity where and when, and by which subprocesses in the brain, during the time it takes to comprehend a single word in isolation? What is the flow of information encoded when a newly sensed word first activates sensory cortex, then later results in neural activation encoding the word meaning? How does the brain integrate a newly encountered word in the context of earlier words in the sentence or phrase, to compose the meaning representation of the multi-word phrase or sentence? and How do semantic expectations and demands, together with syntactic sentence structure alter the processing of words, compared to processing the same words in isolation, or as an unstructured set such as {kick, Joe, ball}? To study these questions we will (1) devise novel experimental protocols to probe the flow of information encoded in neural signals during word and sentence processing, (2) collect new brain image data using both fMRI to achieve spatial resolution of a few millimeters, and MEG to achieve temporal resolution of a few milliseconds, (3) develop and apply novel machine learning approaches to build computational models that integrate and that predict this combined experimental data. Our goal is to develop an increasingly accurate computational model of how the brain comprehends words, phrases and sentences - a model that makes testable predictions about the neural activity observed in response to novel language stimuli. Intellectual Merit: This collaborative research brings together advanced machine learning algorithms with novel experimental protocols for MEG and fMRI brain imaging to advance our understanding of two fundamental open questions about the human brain: how does the brain represent meaning, and what neuro-cognitive processes construct that meaning piece-by-piece from perceived language stimuli? Broader Impacts: If successful, this research will impact a broad range of communities, including (1) cognitive neuroscience and computational linguistics, providing improved understanding of language processing in the brain, (2) machine learning, by driving the development of new methods for time series and latent variable analysis, integrating multiple data sets, and incorporating diverse background knowledge as priors, (3) clinical studies of brain pathologies, especially those related to language processing, and informing treatment strategies for developmental and acquired language disorders (4) education of graduates, undergraduates and the general public, through dissemination of technical articles, teaching materials, and news about our work in the public press.

Tensors are multi-dimensional generalizations of matrices, and so can have non-numeric entries. Extremely large and sparse coupled tensors arise in numerous important applications that require the analysis of large, diverse, and partially related data. The effective analysis of coupled tensors requires the development of algorithms and associated software that can identify the core relations that exist among the different tensor modes, and scale to extremely large datasets. The objective of this project is to develop theory and algorithms for (coupled) sparse and low-rank tensor factorization, and associated scalable software toolkits to make such analysis possible. The research in the project is centered on three major thrusts. The first is designed to make novel theoretical contributions in the area of coupled tensor factorization, by developing multi-way compressed sensing methods for dimensionality reduction with perfect latent model reconstruction. Methods to handle missing values, noisy input, and coupled data will also be developed. The second thrust focuses on algorithms and scalability on modern architectures, which will enable the efficient analysis of coupled tensors with millions and billions of non-zero entries, using the map-reduce paradigm, as well as hybrid multicore architectures. An open-source coupled tensor factorization toolbox (HTF- Hybrid Tensor Factorization) will be developed that will provide robust and high-performance implementations of these algorithms. Finally, the third thrust focuses on evaluating and validating the effectiveness of these coupled factorization algorithms on a NeuroSemantics application whose goal is to understand how human brain activity correlates with text reading & understanding by analyzing fMRI and MEG brain image datasets obtained while reading various text passages.

Given triplets of facts (subject-verb-object), like ('Washington' 'is the capital of' 'USA'), can we find patterns, new objects, new verbs, anomalies? Can we correlate these with brain scans of people reading these words, to discover which parts of the brain get activated, say, by tool-like nouns ('hammer'), or action-like verbs ('run')?
We propose a unified "coupled tensor" factorization framework to systematically mine such datasets. Unique challenges in these settings include
(a) tera- and peta-byte scaling issues,
(b) distributed fault-tolerant computation,
(c) large proportions of missing data, and
(d) insufficient theory and methods for big sparse tensors.
The Intellectual Merit of this effort is exactly the solution to the above four challenges.

The Broader Impact is the derivation of new scientific hypotheses on how the brain works and how it processes language (from the never-ending language learning (NELL) and NeuroSemantics projects) and the development of scalable open source software for coupled tensor factorization. Our tensor analysis methods can also be used in many other settings, including recommendation systems and computer-network intrusion/anomaly detection.

KEYWORDS:
Data mining; map/reduce; read-the-web; neuro-semantics; tensors.

Although big data has had a huge impact in several areas, this impact is limited by the high cost and poor quality of analyzing unstructured data, and the costs of integrating data of multiple types. Lowering these costs will bring the benefits of big data based research to many new areas. Against this background, this project aims to develop machine-learning methods that read, analyze, and integrate web-scale collections of text and other data. The project can be expected to yield fundamental advances in data integration, machine learning, natural language understanding, and automated inference.

The project includes research thrusts in (1) robust semi-supervised bootstrap learning algorithms that can cope with ambiguity in text, (2) algorithms for detecting and aligning the schemas implicit in semi-structured sources relative to a shared common ontology, (3) NLP algorithms that perform deeper analysis on text to extract infrequently mentioned yet important facts, and (4) targeted reading agents capable of pursuing specific queries or conjectures based on the scientist's current focus.

Anticipated results of the project include fundamental advances in each of the research thrusts and their synergistic integration into software system (NESSIE) designed to help scientists in exploring scientific hypotheses in their respective domains of interest, by supporting targeted extraction of knowledge from large amounts of textual sources in relevant areas.

Broader impacts of the research include advanced techniques for extracting and organizing structured knowledge from text, and integrate the learned information with existing structured knowledge in multiple domains. The Additional broader impacts of the research include enhanced opportunities fore advanced research-based training of graduate students. The softare and data resulting from the research will be made freely available to the larger scientific community.

The aim of this project is to develop mathematical models, analysis, and algorithms that will advance both the design and understanding of large-scale machine learning systems. In recent years, machine learning has come into widespread use across a range of applications, and we have also seen significant advances in the theoretical understanding of learning processes. Yet despite these successes, there remains a gulf between theory and application. For example, applications often demonstrate success on problems that theory tells us are intractable in the worst case. Furthermore, as modern machine learning applications scale up from learning of single tasks to learning many tasks simultaneously, new theory is needed to analyze these larger scale multi-task learning settings. This project aims to bridge this gap by developing and applying theory targeted toward realistic-case analysis of learning problems, which capture the structures that enable applications to succeed even when theoretical analyses show the impossibility of doing so in the worst case. This work will be guided by problems at the core of NELL and InMind, two current learning systems that address large-scale multi-task machine learning problems, for reading the web and providing highly personalized electronic assistants to hundreds of interconnected mobile phone users.

More specifically, this project has three main components:

(1) To develop computationally efficient algorithms for clustering, constrained optimization, and related optimization tasks crucial to large-scale machine learning, with provable guarantees under natural, realistic non-worst-case analysis models.

(2) To develop foundations and practical algorithms for multi-task and life-long learning that exploit explicit and implicit structure to minimize key resources including computation time and human labeling effort, as well as address key constraints such as privacy.

(3) To apply the algorithms developed to solve key challenges in two current large-scale learning systems, NELL and InMind.

The proposed work will aid the development of large-scale machine learning applications, as well as create important connections between multiple areas of significant importance in modern machine learning and theoretical computer science. In addition to advising students on topics connected to this project, research progress (on multi-task learning, life-long learning, and clustering) will be integrated in the curricula of several courses at CMU and course materials will be made available on the world wide web. Course projects based on this research will be available to students in the introductory machine learning course at CMU, which enrolls over 600 students each year. In addition, students seeking topics for undergraduate thesis or independent study may also pursue research affiliated with this project.

Intelligent assistants such as Apple's Siri, Amazon's Alexa and Microsoft's Cortana are rapidly gaining popularity by providing a conversational natural language interface for users to access various online services and digital content. They allow computing tasks to be performed in contexts where users cannot touch their phones (such as while driving), and on wearable and Internet of Things (IoT) devices (such as Google Home). However, such conversational interfaces are limited in their ability to handle the "long-tail" of tasks and suffer from lack of customizability. This research will explore a new multi-modal, interactive, programming-by-demonstration (PBD) approach that enables end users to add new capabilities to an intelligent assistant by programming automation scripts for tasks in any existing third-party Android mobile app using a combination of demonstrations and verbal instructions. The system will leverage state-of-the-art machine learning and natural language processing techniques to comprehend the user's verbal instructions that supply information missing in the demonstration, such as implicit conditions, user intent and personal preferences. The user's demonstration on the graphical user interface will be used for grounding the conversation and reinforcing the natural language understanding model. The system will point the way to allowing the general public to more effectively use their smartphones, IoT devices and intelligent assistants, increasing the adoption, efficiency and correctness of uses of these technologies. The integration of intelligent assistants with PBD will have broad impact by exposing people to programming concepts in an easy-to-learn way, and thereby increasing computational thinking.

This project will result in several innovations beyond the current state of the art through advances in programming by demonstration (PBD) and intelligent assistants, and especially in their integration. The work will explore leveraging verbal instructions as an additional modality to address long-standing challenges in PBD research including generalizing the data descriptions and adding control structures. How to coordinate the two modalities to help the intelligent assistant learn new tasks effectively and efficiently from users will be investigated, and how users utilize the two modalities in multi-modal PBD systems for programming tasks in different situations will also be studied. New ways to leverage the displayed graphical user interfaces (GUI) of apps to enhance the speech recognition and language understanding by using the strings and other context of the GUI on the smartphone will be developed. The ability of the conversational assistant to participate in this generalization process will be enhanced, with a focus on having the system ask appropriate and helpful questions so the task automation will fit the user's needs and intentions. New approaches to representing scripts created by PBD systems that users can read, understand and edit will be explored, as will increasing trust and usefulness of the scripts and supporting error handling, debugging and maintenance. The new technology will also be able to extract data from and enter data into apps, and to learn, through demonstration and verbal instruction, how to transform the data into appropriate formats. Finally, how to support sharing of scripts created by PBD systems while ensuring the appropriate levels of privacy and security will also be investigated.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.