Context Structures for Dialogs
Edward Eugene Burns ('08), Kim Bruce
When we speak, our words, phrases, and sentences do not exist in a vacuum. Instead, they interact and gain meaning, both from what has been said as well as what we are expected to say. This complex interplay, especially when coupled with humanity’s aggravating tendency to never say quite exactly what we mean, forces models of conversation into unexplored theoretical territory. We approach this problem by representing sentences as statements of first-order logic. This allows us to automatically infer and verify certain aspects of sentence meaning, such as pragmatic presuppositions (what a speaker’s sentences presuppose) and speaker consistency (if the speaker is contradicting his or her previous claims). In addition, a table-based structure allows us to track the current state of a conversation: what has been discussed, what remains to be talked about, and a general map of the predicted outcome of the conversation. This ongoing project is an implementation of theoretical work by Profs. Bruce and Farkas and is currently capable of basic conversational modeling, presupposition inference, and consistency checking. Further work with complex sentence forms and more general conversational implicature will require additional work with automated theorem provers and the integration of additional linguistic conversation theory.
Funding provided by: SURP (Richter)
Feature-Based Face Recognition for Vending Machine vs. Amer-Alert System
Adriana Ivanova Kovashka ('08), Tzu-Yi Chen, Margaret Martonosi*
*Department of Electrical Engineering, Princeton University, Princeton, NJ
Face recognition systems are an important field in computer vision and are currently used to monitor for dangerous persons and track criminals. A face recognition system uses a database of images and compares another image against those to find a match, if one exists. We implemented an original face recognizer in Java and tested it for recall and accuracy with three image sets. For each facial image, we created a fingerprint of 18 features, such as the RGB values for the eye color, the width and height of the face, various ratios etc. We utilized WEKA machine learning to determine which features are most important and to give them appropriate weights. We found that the distances between the eyes, nose and mouth were not useful as they vary little between people. Overall, our method achieved very good results. For scenarios like surveillance which require low false negatives, our accuracy rate was 75% (and 2.3% false negatives). For vending machine authentication where low false positives are needed, we had 49.3% accuracy (and 1.5% false positives). Our system often outperformed WEKA since it uses a more flexible classification rule in the form of a similarity score rather than a binary decision tree.
Funding provided by: Computing Research Association (Distributed Mentor Program)
A Reinforcement Learning Based Approach to the Selection of Sparse Linear Solvers
Erik William Kuefler ('09), Tzu-Yi Chen, America Holloway
Reinforcement learning is a technique in artificial intelligence that allows a program to learn by interacting with its environment. After experimenting with its capabilities on a trial-and-error basis, the program learns which actions are best for achieving its goals in the environment. In this work we apply reinforcement learning to the selection of preconditioned iterative solvers for sparse linear systems (Ax=b). Using the right solver can significantly reduce the time needed to solve the system, but the variety of solvers available makes choosing the right one for any particular system challenging. While other researchers have tried applying machine learning techniques to this problem, the techniques they use simply evaluate pre-created strategies. The reinforcement learning based approach that we take, however, can generate a strategy on its own initiative. We describe the design and implementation of our system and its application to this problem. We show that its performance is comparable to that of other known methods and describe potential ways to improve the the strategies generated by our system.
Funding provided by: NSF (#CCF-0446604 - TYC)
A Smarter Java Verifier
Patrick Summerhays McNally ('08), Kim Bruce
It is important to ensure that programs downloaded to a computer are safe, yet execute efficiently. This summer we examined Sun Microsystems’ open-source JDK (an implementation of the Java Programming Language Platform) and implemented a system to remove inefficient type casts employed by the current java virtual machine to guarantee the type security of generic structures. Generics are a relatively new feature in Java that allow programmers to create general classes that can be used securely to accommodate a wide variety of kinds of data. The current industry version of Java utilizes type casts inserted into byte code to guarantee the type security of generics and protect against viruses. These type casts are unnecessary and inefficient. If the verifier instead just considered a generic structure’s actual type, they could be removed. By using annotations in source code, we were able to remove these type casts and develop a new, more intelligent verifier that considered the actual types of generic data structures and methods. Our new system will guarantee programs to be just as secure as the current Java Virtual Machine, and will also more efficiently run long programs utilizing generic structures or methods.
Funding provided by: Pomona College Computer Science Department
Graph Theoretic Approaches to Studying Nonsymetric Perfect Elimination Matrices
Ragib Morshed ('09), Tzu-Yi Chen
Solving a sparse linear system Ax=b for x is an important problem arising in a variety of applications ranging from computational fluid dynamics to circuit simulation. Unfortunately, applying the standard Gaussian elimination procedure to a sparse matrix may introduce fill-in by turning some of the entries that were initially zero to nonzero. Preservation of sparseness is important since otherwise it can lead to significantly increased computer storage requirements. However, choosing the sequence of pivots wisely can reduce fill-in. In this work we use graphs to study the class of perfect elimination matrices, which are those that have a sequence of pivots that produces no fill-in. We focused on understanding nonsymmetric perfect elimination matrices. While we were not able to generalize known results about symmetric perfect elimination matrices to the nonsymmetric case, we were able to prove certain structural properties of some types of nonsymmetric perfect elimination graphs, and to construct a class of recursive perfect elimination graphs we call rspeb. We have also made some progress using optimization technique in modeling the minimum fill-in problem, which is finding the least number of edges whose addition makes the graph perfect elimination.
Funding provided by: NSF (#CCF-0446604 - TYC)
Analyzing Current Confinement Mechanisms
Charles Zhou ('08), Everett Bull
Computer security has become a growing concern for computer users everywhere. With virus alerts coming out on a daily basis, many resources are being dedicated to keeping sensitive information safe. My summer research with Professor Everett Bull was to examine one key aspect of security: confinement. The underlying idea is the Principle of Least Privilege: Applications should run with the bare minimum amount of privileges they need to accomplish their designated tasks. A game like solitaire should never have the ability to access your personal data, connect to the Internet, and send the data to a malicious outsider. Yet many applications we run are over-privileged. This is why email viruses are able to do significant damage to our computers. A successful confinement strategy would limit such damage, but current programming languages and systems do not provide adequate support for the task. In our research, we examined some new, experimental "secure" operating systems and programming languages, with emphasis on the object- capability model, and tested their security claims. Our purpose was to assess their feasibility and to build a knowledge base of information and data in preparation for a future advanced computer security course at Pomona.
Funding provided by: Rose Hills Foundation