Spring 2005

February 3, 2005

Localization is a critical base level capability that underlies a variety of applications in robotics,computer vision and sensor networks. This talk will describe an approach to localizing a set of nodes based on available range and bearing measurements.

Conceptually, the idea is that range and bearing measurements induce constraints on the configuration space of the ensemble. Taken together, these constraints define a feasible region in this space that represents the set of formations that are consistent with all of the available sensor measurements.The scheme produces bounded uncertainty estimates for the relative configuration of the nodes by using modern convex optimization techniques to approximate the projection of this feasible region onto various subspaces of the configuration space.

The talk will describe how the localization schemes can be applied to robotics applications and how they are being extended for use on smart camera sensor networks.

April 4, 2005

Visual object recognition (“Is there a chair in this photograph?”) remains the grand challenge of computer vision. Any solution to this problem must account for the fact that the same object (or different instances of the same object class) may look very different from one image to the next, due to “external” causes (e.g., viewpoint or lighting changes), or “internal” variability (e.g., a Chevy Chevette and a Ferrari are both cars). In this context, I will first discuss a representation of individual three-dimensional (3D) objects in terms of small (planar) patches and their invariants, which, once combined with global geometric constraints, allows the automated acquisition of 3D object models from a small set of unregistered pictures, and their recognition in cluttered photographs taken from unconstrained viewpoints. I will then propose a probabilistic part-based approach to category-level object recognition, where each training image is represented by a set of features encoding the pattern of occurrences of semi-local parts (spatially coherent, distinctive groups of keypoints), and the posterior distribution of the class labels given this pattern is learned using a discriminative maximum entropy framework. Both approaches will be illustrated with extensive experiments.

Speaker Biography: Jean Ponce’s research focuses on computer vision (3D photography and object recognition) and robotics (grasp and manipulation planning). He received the Doctorat de Troisieme Cycle and Doctorat d’Etat degrees in Computer Science from the University of Paris Orsay in 1983 and 1988. He held Research Scientist positions at the Institut National de la Recherche en Informatique et Automatique (1981–1984), the MIT Artificial Intelligence Laboratory (1984–1985), and the Stanford University Robotics Laboratory (1985–1989). Since 1990, he has been with the Department of Computer Science and the Beckman Institute at the University of Illinois at Urbana-Champaign, where he is a Full Professor. Dr. Ponce is the author of over a hundred technical publications, including the textbook “Computer Vision: A Modern Approach”, in collaboration with David Forsyth. Dr. Ponce is Editor-in-Chief of the International Journal of Computer Vision, and was an Area Editor of Computer Vision and Image Understanding (1994–2000) and an Associate Editor of the IEEE Transactions on Robotics and Automation (1996–2001). He was Program Chair of the 1997 IEEE Conference on Computer Vision and Pattern Recognition and served as General Chair of the year 2000 edition of this conference. In 2003, he was named an IEEE Fellow for his contributions to Computer Vision, and he received a US patent for the development of a robotic parts feeder.

April 5, 2005

In this talk I will describe successful attacks on the TIRIS Digital Signature Transponder (DST) Tag, an RFID device used to secure millions of SpeedPass payment transponders and automobile ignition keys. The cipher used by these devices is proprietary, so I will begin by presenting the techniques used to reverse engineer the algorithm given black-box access to chosen input/output pairs. I will then present a number of different methods for brute-forcing the keys to this cipher and the engineering that was required to create a tag simulator. I will conclude with some discussion of future directions for secure RFIDs.

April 7, 2005

The maturing of speech recognition and corpus-based natural language processing has led to many practical applications in human-machine or human-human interactions utilizing both technologies. Speech processing is ultimately about detecting, finding and translating pertinent information from the spoken input rather than word by word transcription.

In this talk, I will give an overview of our research in the last seven years at HKUST combining both automatic speech recognition and natural language processing for spontaneous speech modeling, speech topic detection and summarization and speech translation. The main challenge of these tasks lies in discovering critical information from large amounts of unstructured, spontaneous, often accented, and multilingual speech. To this end, we propose that:

” A common acoustic model for speech recognition of multiple languages can be achieved by bootstrapping from a single language. ” Spontaneous and accented speech recognition can be best achieved by differentiating between phonetic and acoustic changes. ” Spontaneous and colloquial speech recognition can be made efficient by statistical learning of a spontaneous speech grammar. ” The best context information for translation disambiguation in a mixed language query is the most salient trigger word. ” Topic detection and summarization of multilingual, multimodal and multiple documents can be efficiently achieved by a unified segmental HMM framework. ” Fixed-point front end processing, discrete HMMs, and unambiguous inversion transduction grammars provide the optimal performance and speed tradeoff for speech translation on portable devices.

I will also discuss our contributions in mining and collecting large amounts of speech and text data for the above research.

Speaker Biography: Pascale Fung received her PhD from Columbia University in 1997. She is one of the founding faculty members of the Human Language Technology Center (HLTC) at HKUST. She is the co-editor of the Special Issue on Learning in Speech and Language Technologies of Machine Learning Journal. She has been on the organizing committee of the Association of Computational Linguistics (ACL)’s SIGDAT, and served as area chair for ACL and chair for the Conference on Empirical Methods in Natural Language Processing (EMNLP), as well as co-chair of SemaNet 2002 at Coling. Pascale was the team leader for Pronunciation Modeling of Mandarin Casual Speech at the 2000 Johns Hopkins Summer Workshop. She has served as program committee member of numerous international conferences and technical publications. She is a Senior Member of the Institute of Electrical and Electronic Engineers (IEEE) and a Member of the Association of Computational Linguistics (ACL).

During her professional leave from 2000-2002, Pascale Fung co-founded and became the CTO and CEO of a Silicon Valley based multinational company specialized in developing and marketing speech and natural language solutions for internet and corporate customers. She was Member of Technical Staff and later Consultant at AT&T Bell Labs from 1993-1997. During 1991-1992, she was Associate Scientist at BBN Systems & Technologies (Cambridge, MA), participating in the design and implementation of the BYBLOS speech recognition system. She was a visiting researcher at LIMSI, Centre National de la Recherche Scientifique (France) in 1991, working on speaker adaptation and French speech recognition. From 1989-1991, she was a research student in the Department of Information Science, Kyoto University (Japan), working on Japanese phoneme recognition and speaker adaptation. Prior to that, she was an exchange student at Ecole Centrale Paris (France) working on speech recognition. A fluent speaker of six European and Asian languages, she has been particularly interested in multilingual speech and natural language issues.

April 8, 2005

This talk introduces the proportional genetic algorithm (PGA) and discusses the evolution of genomic organization in a PGA.

Knowledge representation is an important issue in the development of machine learning algorithms such as the genetic algorithm (GA). A representation determines what can be expressed, which in turn determines the concepts thatcan or cannot be learned. How a problem is represented in a learning algorithm also defines the shape of the landscape on which a learning algorithm searches which in turn determines the connections between candidate solutions and determine how a learning algorithm traverses the solution space.

Typical binary-encoded GA representations are order-based representations that are compact and efficient but limit the evolvability of the GA. Problems such as positional bias and Hamming cliffs further limit the performance of a typical GA. We analyze the effectiveness of a general, multi-character representation in which information is encoded solely in terms of the presence or absence of genomic symbols on an individual. As a result, the ordering of the genomic symbols is free to evolve in response to other factors, for example, in response to the identification and formation of building blocks. Experimental analyses indicate that when the ordering of genomic symbols in a GA is completely independent of the fitness function and therefore free to evolve along with the candidate solutions that they encode, the resulting genomes self-organize into self-similar structures that favor the desirable property of a positive correlation between the form and quality of solutions.

Speaker Biography: Dr. Annie S. Wu is currently an assistant professor in the School of Computer Science at the University of Central Florida (UCF). She received a Ph.D. in Computer Science and Engineering from the University of Michigan under the guidance of Professors John Holland and Robert Lindsay. Before joining UCF, she was a National Research Council Postdoctoral Associate at the Navy Center for Applied Research in Artificial Intelligence at the Naval Research Laboratory. Dr. Wu has written over 45 peer-reviewed publications in the area of evolutionary computation. Her research has been funded by Intelligent Systems Technology Inc., DARPA, ITT Industries, Naval Research Laboratory,NAWCTSD, and SAIC. She is a member of the Executive Board of the ACM Special Interest Group for Genetic and Evolutionary Computation (SIGEVO) and a member of the editorial boards of the Evolutionary Computation Journal and the Journal of Genetic Programming and Evolvable Machines.

April 15, 2005

Software vulnerability and software exploit are the root cause of a majority of computer security problems. But how does software break? How do attackers make software break on purpose? What tools can be used to break software? This talk is about making software beg for mercy. You will learn:

  • Why software exploit will continue to be a serious problem
  • When network security mechanisms fail
  • How attack patterns can be used to build better software
  • Why reverse engineering is an essential skill
  • Why rootkits are the apex of software exploit, and how they work
  • Why the only answer is building better software

Some may argue that discussing software exploit in public is a bad idea. In fact, it’s impossible to protect yourself if you don’t know what you’re up against. Come find out for yourself.

Speaker Biography: Gary McGraw, Cigital, Inc.’s CTO, researches software security and sets technical vision in the area of Software Quality Management. Dr. McGraw is co-author of four popular books: Java Security (Wiley, 1996), Securing Java (Wiley, 1999), Software Fault Injection (Wiley 1998), and Building Secure Software (Addison-Wesley, 2001). His best selling fifth book, Exploiting Software (Addison-Wesley), was released in February 2004. A noted authority on software and application security, Dr. McGraw consults with major software producers and consumers. Dr. McGraw has written over sixty peer-reviewed technical publications and functions as principal investigator on grants from Air Force Research Labs, DARPA, National Science Foundation, and NIST’s Advanced Technology Program. He serves on Advisory Boards of Authentica, Counterpane, Fortify Software, and Indigo Security as well as advising the CS Department at UC Davis. Dr. McGraw holds a dual PhD in Cognitive Science and Computer Science from Indiana University and a BA in Philosophy from UVa. He writes a monthly security column for Network magazine, is the editor of Building Security In for IEEE Security & Privacy magazine, and is often quoted in national press articles.

April 19, 2005

Many pattern recognition applications use statistical models with a large number of parameters, although the amount of available training data is often insufficient for robust parameter estimation. A common technique to reduce the effect of data sparseness is the divide-and-conquer approach, which decomposes a problem into a number of smaller subproblems, each of which can be handled by a more specialized and potentially more robust model. This talk describes how this principle can be applied to a variety of problems in speech and language processing: the general procedure is to adopt a feature-based representation for the objects to be modelled (such as phones or words), learn statistical models describing the features of the object rather than the object itself, and recombine these partial probability estimates. This enables a more efficient use of data, and the sharing of data from heterogeneous sources (such as different languages). I will present both knowledge-inspired and data-driven techniques for designing appropriate feature representations, and unsupervised methods for optimizing the model combination on task-specific criteria. Experimental results will be presented for four different applications: articulatory-based speech recognition, multi-stream automatic language identification, factored statistical language modeling, and statistical machine translation.

April 29, 2005

June 7, 2005

The performance of algorithms is analytically measured by familiar notions of time and space complexity. The efficiency of randomized algorithms is judged by a third measure called the random bit complexity, i.e. the number of random bits needed by the algorithm. Derandomization is an extreme procedure of eliminating the need for random bits altogether.

We present new tools and ideas for derandomizing algorithms. We apply these tools to derandomize combinatorial problems such as Max Cut and algorithms for dimensionality reduction.

The talk will give an introduction to derandomization and a high level description of some new ideas in derandomizing algorithms.

June 17, 2005

The aerospace and defense industries have made use of so-called ?automatic test equipment? for over 40 years to test and maintain their systems. An ATE comprises a suite of electronic test instruments (e.g., multi-meters, waveform generators, and oscilloscopes), power supplies, a test control computer, a switching matrix, and an interface device to connect to a unit under test (UUT). The test control computer runs a program that controls both the UUT and the test instruments, sequencing a set of tests that are run against the UUT. Ultimately, the purpose of the ATE is to detect and isolate faults in the UUT so that the UUT can subsequently be repaired.

Until recently, the architecture of the ATE largely utilized brute-force interfaces and algorithms to test the UUT, and many ATE are configured for a specific UUT or class of UUTs. Due to the high cost of developing and maintaining ATE, current requirements by ATE users, including the department of defense and the commercial airlines, demand the development of systems that are interoperable, adaptable, and capable of handling the complexities of diagnosis and prognosis of multiple UUTs.

In this talk, I will discuss recent research in developing diagnostic test programs that address these demands. Specifically, I will describe an emerging automatic test system (ATS) framework for defining ATS architectures and place diagnostics and prognostics within that framework. I will then describe the evolution of diagnosis within the ATS and present recent research in the application of Bayesian networks to diagnosis and prognosis. Note that while Bayesian diagnosis has been around for some time, it has never been applied in the ATE environment. Note also that only reliability-based prognosis has been applied to electronic systems, and this method is known to be inadequate. It is believed that Bayesian methods (with the recent emergence of ?dynamic? Bayesian networks) offer some hope in addressing the prognosis problem and thus offer tremendous potential for the diagnosis problem as well.

Speaker Biography: John Sheppard is a corporate fellow at ARINC Incorporated, a company privately owned by the commercial airlines dedicated to solving complex problems for both the airline and defense industries. He has been performing research and development in model-based diagnosis and machine learning for almost 20 years and is recognized as a leading expert in system-level diagnosis within the defense industry. Dr. Sheppard received his PhD in computer science from Johns Hopkins University in 1997 and has been affiliated with JHU, either as a student or a part time member of the faculty, since 1988. He served as the technical program chair for AUTOTESTCON (the only conference on system-level test and diagnosis) in 2001 and is the 2007 technical program chair. He is also the vice chair of the IEEE Standards Coordinating Committee 20 on Test and Diagnosis of Electronic Systems and the past chair of the Diagnostic and Maintenance Control subcommittee of SCC20.