UC Santa Cruz

Complex tasks such as sequence labeling, collective classification, and activity recognition involve predicting outputs that are interdependent, a task known as structured prediction. Approaches such as structured support vector machines, conditional random fields, and statistical relational learning (SRL) frameworks are known to be effective at structured prediction. Of these approaches, SRL frameworks are unique as they combine ease of using logical statements with the power of probabilistic models. However, structured prediction using SRL frameworks face several challenges that affect both scalability and accuracy of these models. In this dissertation, I address four key challenges that significantly improves scalability and accuracy of SRL model at performing structured prediction task. First, structured prediction using large graphical models: graphical models generated through SRL frameworks for structured prediction tasks are often large, and this can make inference computationally expensive. Second, memory-constrained structured prediction: often performing structured prediction using large graphical models require a large amount of memory, which can be infeasible as some model sizes can grow to require terabytes of space. Third, real-time structured prediction: some applications require performing structured prediction tasks in real-time, which requires an extremely efficient inference engine that can perform model generation and inference in under a few milliseconds. Fourth, the optimization of arbitrary user-defined evaluation function: every application evaluates its structured prediction task via a unique evaluation function with arbitrary form, making it challenging to optimize them through well-known approaches such as gradient-descent. In this dissertation, I propose four general techniques that address these challenges and improve the scalability and accuracy of structured prediction tasks. First, I develop an approach to detect and exploit symmetries in large graphical models that make inference more tractable. Second, I develop a new framework that intertwines model generation and inference to perform structured prediction effectively. Further, this approach makes use of disk space and a smart in-memory cache to minimize the memory footprint and scale inference based on disk space rather than the main memory. Third, I derive a new inference procedure based on a second-order method, which reduces the inference time on small graphical models to under a millisecond enabling structured prediction to be performed online in real-time. Further, to demonstrate the effectiveness of this procedure, I introduce the concept of a micrograph to generate small effective graphical models and perform real-time structured prediction in the product search domain. Finally, I propose four parameter estimation approaches based on search strategies that can directly optimize any user-defined evaluation function by treating it as a black-box. These methods significantly improve the scalability and accuracy of structured prediction tasks and expand their scope to domains previously impossible.