This study focuses on the modeling of the underlying structured semantic information in natural language text to predict real world phenomena. The thesis of this work is that a general and uniform representation of linguistic information that combines multiple levels, such as semantic frames and roles, syntactic dependency structure, lexical items and their sentiment values, can support challenging classification tasks for NLP problems. The hypothesis behind this work is that it is possible to generate a document representation using more complex data structures, such as trees and graphs, to distinguish the depicted scenarios and semantic roles of the entity mentions in text, which can facilitate text mining tasks by exploiting the deeper semantic information. The testbed for the document representation is entity-driven text analytics, a recent area of active research where large collection of documents are analyzed to study and make predictions about real world outcomes of the entity mentions in text, with the hypothesis that the prediction will be more successful if the representation can capture not only the actual words and grammatical structures but also the underlying semantic generalizations encoded in frame semantics, and the dependency relations among frames and words. The main contribution of this study includes the demonstration of the benefits of frame semantic features and how to use them in document representation. Novel tree and graph structured representations are proposed to model mentioned entities by incorporating different levels of linguistic information, such as lexical items, syntactic dependencies, and semantic frames and roles. For machine learning on graphs, we proposed a Node Edge Weighting graph kernel that allows a recursive computation on the substructures of graphs, which explores an exponential number of subgraphs for fine-grained feature engineering. We demonstrate the effectiveness of our model to predict price movement of companies in different market sectors solely based on financial news. Based on a comprehensive comparison between different structures of document representation and their corresponding learning methods, e.g. vector, tree and graph space model, we found that the application of a rich semantic feature learning on trees and graphs can lead to high prediction accuracy and interpretable features for problem understanding. Two key questions motivate this study: (1) Can semantic parsing based on frame semantics, a lexical conceptual representation that captures underlying semantic similarities (scenarios) across different forms, be exploited for prediction tasks where information is derived from large scale document collections? (2) Given alternative data structures to represent the underlying meaning captured in frame semantics, which data structure will be most effective? To address (1), sentences that have dependency parses and frame semantic parses, and specialized lexicons that incorporate aspects of sentiment in words, will be used to generate representations that include individual lexical items, sentiment of lexical items, semantic frames and roles, syntactic dependency information and other structural relations among words and phrases within the sentence. To address (2), we incorporate the information derived from semantic frame parsing, dependency parsing, and specialized lexicons into vector space, tree space and graph space representations, and kernel methods for the corresponding data structures are used for SVM (support vector machine) learning to compare their predictive power. A vector space model beyond bag-of-words is first presented. It is based on a combination of semantic frame attributes, n-gram lexical items, and part-of-speech specific words weighted by a psycholinguistic dictionary. The second model encompasses a semantic tree representation that encodes the relations among semantic frame features and, in particular, the roles of the entity mentions in text. It depends on tree kernel functions for machine learning. The third is a semantic graph model that provides a concise and convenient representation of linguistic semantic information. It subsumes the vector space model and the semantic tree model by using a graph data structure for a unified representation for semantic frames, lexical items, and syntactic dependency relations derived from frame parses and dependency parses of sentences. The general goal of this study is to ground information derived from NLP techniques to textual datasets in real world observations, where natural language semantics is used as a means to learn the semantic relations that are important in the domain, to understand what is relevant for objectives of interest of the practitioner. Experiments are conducted in a financial domain to investigate whether our computational linguistic methodologies applied to large-scale analysis of financial news can improve the understanding of a company's fundamental market value, and whether linguistic information derived from news produces a consistent enough result to benefit more comprehensive financial models. Stock price data is aligned with news articles. Two kinds of labels are assigned: the existence of a price change and the direction of change. The change in price and polarity tasks are formulated as binary classification problems and bipartite ranking problems. Using the bag-of-words model and the proposed vector-space-model as benchmarks, the experiments show a significant improvement from the use of the semantic tree model. The semantic graph model with more expressive power outperforms both the vector space model and the tree space model. At best, there may be a weak predictive effect of news on price for a particular data instance, which is, for example, a company on a date, due to the fluctuation in uncertainty of financial market and the efficient market hypothesis. However, the proposed models and their outputs can provide useful information to guide financial market price prediction and to help business analysts discover potential investment opportunities. These advantages come from the rich expressive power of the semantic tree model and the semantic graph space model, since the models are able to learn the semantic relations that are important in the problem domain, and effectively discover the useful underlying structured semantic information from large-scale textual data.

Today’s operating systems are large, complex, and plagued with vulnerabilities that allow perpetrators to exploit them for profit. The constant rise in the number of software weaknesses, coupled with the sophistication of modern adversaries, make the need for effective and adaptive defenses more critical than ever. In this dissertation, we develop a set of novel protection mechanisms, and introduce new concepts and techniques to secure commodity operating systems against attacks that exploit vulnerabilities in kernel code. Modern OSes opt for a shared process/kernel model to minimize the overhead of operations that cross protection domains. However, this design choice provides a unique vantage point to local attackers, as it allows them to control—both in terms of permissions and contents—part of the memory that is accessible by the kernel, easily circumventing protections like kernel-space ASLR and WˆX. Attacks that leverage the weak separation between user and kernel space, characterized as return-to-user (ret2usr) attacks, have been the de facto kernel exploitation technique in virtually every major OS, while they are not limited to the x86 platform, but have also targeted ARM and others. Given the multi-OS and cross-architecture nature of ret2usr threats, we propose kGuard: a kernel protection mechanism, realized as a cross-platform compiler extension, which can safeguard any 32- or 64-bit OS kernel from ret2usr attacks. kGuard enforces strong address space segregation by instrumenting exploitable control transfers with dynamic Control- Flow Assertions (CFAs). CFAs, a new confinement (inline monitoring) concept that we introduce, act as guards that prevent the unconstrained transition of privileged execution paths to user space. To thwart attacks against itself, kGuard also incorporates two novel code diversification techniques: code inflation and CFA motion. Both countermeasures randomize the location of the inline guards, creating a moving target for an attacker that tries to pinpoint their exact placement to evade kGuard. Evaluation results indicate that kGuard provides comprehensive ret2usr protection with negligible overhead (∼1%). Furthermore, we expose a set of additional kernel design practices that trade stronger isolation for performance, all of which can be harnessed to deconstruct kernel isolation. To demonstrate the significance of the problem, we introduce a new kernel exploitation technique, dubbed return-to-direct-mapped memory (ret2dir), which relies on inherent properties of the memory management (sub)system of modern OSes to bypass every ret2usr defense to date. To illustrate the effectiveness of ret2dir, we outline a principled methodology for constructing reliable exploits against hardened targets. We further apply it on real-world kernel exploits for x86, x86-64, and ARM Linux, transforming them into ret2dir-equivalents that bypass deployed ret2usr protections, like Intel SMEP and ARM PXN. Finally, we introduce the concept of eXclusive Page Frame Ownership (XPFO): a memory management approach that prevents the implicit sharing of page frames among user processes and the kernel, ensuring that user-controlled content can no longer be injected into kernel space using ret2dir. We built XPFO on Linux and implemented a set of optimizations, related to TLB handling and page frame content sanitization, to minimize its performance penalty. Evaluation results show that our proposed defense offers effective protection against ret2dir attacks with low runtime overhead (<3%).

Because of the rapid growth of large scale video recording and sharing, there is a growing need for robust and scalable solutions for analyzing video content. The ability to detect and recognize video events that capture real-world activities is one of the key and complex problems. This thesis aims at the development of robust and efficient solutions for large scale video event detection systems. In particular, we investigate the problem in two areas: first, event detection with automatically discovered event specific concepts with organized ontology, and second, event detection with multi-modality representations and multi-source fusion. Existing event detection works use various low-level features with statistical learning models, and achieve promising performance. However, such approaches lack the capability of interpreting the abundant semantic content associated with complex video events. Therefore, mid-level semantic concept representation of complex events has emerged as a promising method for understanding video events. In this area, existing works can be categorized into two groups: those that manually define a specialized concept set for a specific event, and those that apply a general concept lexicon directly borrowed from existing object, scene and action concept libraries. The first approach seems to require tremendous manual efforts, whereas the second approach is often insufficient in capturing the rich semantics contained in video events. In this work, we propose an automatic event-driven concept discovery method, and build a large-scale event and concept library with well-organized ontology, called EventNet. This method is different from past work that applies a generic concept library independent of the target while not requiring tedious manual annotations. Extensive experiments over the zero-shot event retrieval task when no training samples are available show that the proposed EventNet library consistently and significantly outperforms the state-of-the-art methods. Although concept-based event representation can interpret the semantic content of video events, in order to achieve high accuracy in event detection, we also need to consider and combine various features of different modalities and/or across different levels. One one hand, we observe that joint cross-modality patterns (e.g., audio-visual pattern) often exist in videos and provide strong multi-modal cues for detecting video events. We propose a joint audio-visual bi-modal codeword representation, called bi-modal words, to discover cross-modality correlations. On the other hand, combining features from multiple sources often produces performance gains, especially when the features complement with each other. Existing multi-source late fusion methods usually apply direct combination of confidence scores from different sources. This becomes limiting because heterogeneous results from various sources often produce incomparable confidence scores at different scales. This makes direct late fusion inappropriate, thus posing a great challenge. Based upon the above considerations, we propose a robust late fusion method with rank minimization, that not only achieves isotonicity among various scores from different sources, but also recovers a robust prediction score for individual test samples. We experimentally show that the proposed multi-modality representation and multi-source fusion methods achieve promising results compared with other benchmark baselines. The main contributions of the thesis include the following. 1. Large scale event and concept ontology: a) propose an automatic framework for discovering event-driven concepts; b) build the largest video event ontology, EventNet, which includes 500 complex events and 4,490 event-specific concepts; c) build the first interactive system that allows users to explore high-level events and associated concepts in videos with event browsing, search, and tagging functions. 2. Event detection with multi-modality representations and multi-source fusion: a) propose novel bi-modal codeword construction for discovering multi-modality correlations; b) propose novel robust late fusion with rank minimization method for combining information from multiple sources. The two parts of the thesis are complimentary. Concept-based event representation provides rich semantic information for video events. Cross-modality features also provide complementary information from multiple sources. The combination of those two parts in a unified framework can offer great potential for advancing state-of-the-art in large-scale event detection.

Statistical methods have been the major force driving the advance of machine translation in recent years. Complex models are designed to improve translation performance, but the added complexity also makes decoding more challenging. In this thesis, we focus on designing exact and approximate algorithms for machine translation decoding. More specifically, we will discuss the decoding problems for phrase-based translation models and bidirectional word alignment. The techniques explored in this thesis are Lagrangian relaxation and local search. Lagrangian relaxation based algorithms give us exact methods that have formal guarantees while being efficient in practice. We study extensions to Lagrangian relaxation that improve the convergence rate on machine translation decoding problems. The extensions include a tightening technique that adds constraints incrementally, optimality-preserving pruning to manage the search space size and utilizing the bounding properties of Lagrangian relaxation to develop an exact beam search algorithm. In addition to having the potential to improve translation accuracy, exact decoding deepens our understanding of the model that we are using, since it separates model errors from optimization errors. This leads to the question of designing models that improve the translation quality. We design a syntactic phrase-based model that incorporates a dependency language model to evaluate the fluency level of the target language. By employing local search, an approximate method, to decode this richer model, we discuss the trade-off between the complexity of a model and the decoding efficiency with the model.

This work investigates the hardness of solving natural computational problems according to different complexity measures. Our results and techniques span several areas in theoretical computer science and discrete mathematics. They have in common the following aspects: (i) the results are unconditional, i.e., they rely on no unproven hardness assumption from complexity theory; (ii) the corresponding lower bounds are essentially optimal. Among our contributions, we highlight the following results. Constraint Satisfaction Problems and Monotone Complexity. We introduce a natural formulation of the satisfiability problem as a monotone function, and prove a near-optimal 2^{Ω (n/log n)} lower bound on the size of monotone formulas solving k-SAT on n-variable instances (for a large enough k ∈ ℕ). More generally, we investigate constraint satisfaction problems according to the geometry of their constraints, i.e., as a function of the hypergraph describing which variables appear in each constraint. Our results show in a certain technical sense that the monotone circuit depth complexity of the satisfiability problem is polynomially related to the tree-width of the corresponding graphs. Interactive Protocols and Communication Complexity. We investigate interactive compression protocols, a hybrid model between computational complexity and communication complexity. We prove that the communication complexity of the Majority function on n-bit inputs with respect to Boolean circuits of size s and depth d extended with modulo p gates is precisely n/log^{ϴ(d)} s, where p is a fixed prime number, and d ∈ ℕ. Further, we establish a strong round-separation theorem for bounded-depth circuits, showing that (r+1)-round protocols can be substantially more efficient than r-round protocols, for every r ∈ ℕ. Negations in Computational Learning Theory. We study the learnability of circuits containing a given number of negation gates, a measure that interpolates between monotone functions, and the class of all functions. Let C^t_n be the class of Boolean functions on n input variables that can be computed by Boolean circuits with at most t negations. We prove that any algorithm that learns every f ∈ C^t_n with membership queries according to the uniform distribution to accuracy ε has query complexity 2^{Ω (2^t sqrt(n)/ε)} (for a large range of these parameters). Moreover, we give an algorithm that learns C^t_n from random examples only, and with a running time that essentially matches this information-theoretic lower bound. Negations in Theory of Cryptography. We investigate the power of negation gates in cryptography and related areas, and prove that many basic cryptographic primitives require essentially the maximum number of negations among all Boolean functions. In other words, cryptography is highly non-monotone. Our results rely on a variety of techniques, and give near-optimal lower bounds for pseudorandom functions, error-correcting codes, hardcore predicates, randomness extractors, and small-bias generators. Algorithms versus Circuit Lower Bounds. We strengthen a few connections between algorithms and circuit lower bounds. We show that the design of faster algorithms in some widely investigated learning models would imply new unconditional lower bounds in complexity theory. In addition, we prove that the existence of non-trivial satisfiability algorithms for certain classes of Boolean circuits of depth d+2 leads to lower bounds for the corresponding class of circuits of depth d. These results show that either there are no faster algorithms for some computational tasks, or certain circuit lower bounds hold.

<p> Temperature is an important and first step in determining the health of individuals. Using an infrared temperature sensor is easy to do, quick, and does not involve touching a patient. Current devices are useful but technological advances in electronics have brought new capabilities to infrared temperature readings. One advance has narrowed the field of view and thereby increased the distance range of infrared thermometers. This feature would allow health care personnel to avoid exposure to a contagious zone surrounding a patient. A second feature allows users to include the emissivity of infrared readings for humans. Neither of these advances can be exploited by current infrared thermometers leaving a void in the practical application of this new breed of infrared sensors. A 2014 report by the Canadian Agency for Drugs and in Health (CADTH) questioned the accuracy of infrared thermometers and called for more research. </p><p> This dissertation explores the parameters of the basic physics underlying infrared sensors. A methodology is developed to conduct various testing regimes using C++ or Python software programming and two surveys of students were conducted using a modern sensor. The evaluation of the results determined the accuracy and range of infrared sensor temperature readings were improved with the inclusion of the emissivity parameter using machine analysis of emissivity.</p><p>

<p> Datacenters are evolving to host heterogeneous Big Data workloads on shared clusters to reduce the operational cost and achieve higher resource utilization. However, it is challenging to schedule heterogeneous workloads with diverse resource requirements and QoS constraints. For example, when consolidating latency critical jobs and best-effort batch jobs in the same cluster, latency critical jobs may suffer from long queuing delay if their resource requests cannot be met immediately; while best-effort jobs would suffer from killing overhead when preempted. Moreover, resource contention may harm task performance running on worker nodes. Since resource requirements for diverse applications show heterogeneity and is not known before task execution, either the cluster manager has to over-provision resources for all incoming applications resulting in low cluster utilization; or applications may experience performance slowdown or even failure due to resource insufficiency. Existing approaches focus on either application awareness or system awareness and fail to address the semantic gap between the application layer and the system layer (e.g., OS scheduling mechanisms or cloud resource allocators). </p><p> To address these issues, we propose to attack these problems from a different angle. In other words, applications and underlying systems should cooperate synergistically. This this way, the resource demands of application can be exposed to the system. At the same time, application schedulers can be assisted with more runtimes of the system layer and perform more dedicated scheduling. However, the system and application co-design is challenging. First, the real resource demands for an application is hard to be predicted since its requirements vary during its lifetime. Second, there are tons of information generated from system layers (e.g., OS process schedulers or hardware counters), from which it is hard to associate these information to a dedicated task. Fortunately, with the help of lightweight virtualization, applications could run in isolated containers such that system level runtime information can be collected at the container level. The rich APIs of container based virtualization also enable to perform more advanced scheduling. </p><p> In this thesis, we focus on efficient and scalable techniques in datacenter scheduling by leveraging lightweight virtualization. Our thesis is two folds. First, we focus on profiling and optimizing the performance of Big Data applications. In this aspect, we built a tool to trace the scheduling delay for low-latency online data analytics workloads. We further built a map execution engine to address the performance heterogeneity for MapReduce. Second, we focus on leveraging OS containers to build advanced cluster scheduling mechanisms. In that, we built a preemptive cluster scheduler, an elastic memory manager and an OOM killer for Big Data applications. We also conducted a supplementary research on tracing the performance of Big Data training on TensorFlow. </p><p> We conducted extensive evaluations of the proposed projects in a real-world cluster. The experimental results demonstrate the effectiveness of proposed approaches in terms of improving performance and utilization of Big Data clusters. </p><p>

<p> The introduction of autonomous agents to replace humans in unfavorable and unreachable environments has been a longstanding goal in the field of robotics. The existing work of various researchers address several challenges involved in design or control of such robotic systems. However, existing solutions have been unable to offer users an easy and efficient programming environment for developing versatile robotic applications. These inadequacies have given rise to the development of a new robot programming language, called Programming LAnguage for Synchronous Agents (PLASA). </p><p> The main objective of this paper is to give a brief introduction about the newly developed robot programming language, PLASA, which facilitates the rapid implementation of co-operative applications on multiple physical robots, in dynamic environments. The syntax and semantics of this language are similar to those in many other high-level programming languages. In addition to the features offered by other high-level languages, PLASA offers two novel instructions: "do instruction'', which helps in executing the main motion primitives, and "query instruction'', which helps in executing a great variety of geometric and mathematical queries. A compiler produces a program that is executed by a virtual machine in each of the robots. The virtual machine offers a key characteristic that guarantees the timely execution of robots' movements through a synchronization protocol. To verify the correct functionality of the co-operative applications, a simulator that includes the proposed components has been provided. </p><p> The developed language offers abstraction for hiding complex network details and delivers human-readable language; these features make the programming environment suitable for anyone to control robot systems, regardless of expertise. The synchronization and co-ordination mechanisms provided by the language ensure the safety and prompt execution of robot operations in a robot system developed using PLASA.</p><p>

<p> The focus of this dissertation is the analysis of and verification of discrete time stochastic systems using martingales. Martingale theory yields a powerful set of tools that have recently been used to prove quantitative properties of stochastic systems such as stochastic safety. In this thesis, we focus on the analysis of qualitative trace properties of stochastic systems such as almost sure reachability and termination, persistence and recurrence. An almost sure reachability property &diam;(<i>T</i>) states that with probability 1 the executions of the system reach a target set of states <i> T</i>. A qualitative persistence property &diam;&square;(<i>T</i>) specifies that almost all executions of the stochastic system eventually reach the target set <i>T</i> and stay there forever. Likewise, a recurrence property &square;&diam;(<i>T</i>) specifies that a target set of states <i>T</i> is visited infinitely often by almost all executions of the stochastic system.</p><p> For each type of property, we present deductive reasoning techniques in the form of proof rules that rely on finding an appropriate certificate function to establish almost sure reachability, persistence and recurrence properties of infinite-state, discrete time polynomial stochastic systems. Next, we extend known efficient constraint-based and abstract interpretation-based invariant synthesis techniques to deduce the necessary supermartingale expressions to partly mechanize such proofs. We demonstrate that martingale certificates can serve as expectation invariants and generalize this idea to sets of mutually inductive expectation invariants.</p><p> Finally, we explore the connection between the properties of our martingale certificates and existing concentration of measure results to establish probability bounds on the quantitative version of these properties.</p>

<p>Scalability of applications is a key requirement to gaining performance in hybrid and cluster computing. Implementing code to utilize multiple accelerators and CPUs is difficult, particularly when dealing with dependencies, memory management, data locality, and processor occupancy. The Hybrid Task Graph Scheduler (HTGS) is designed to increase programmer productivity to develop applications for single nodes with multiple CPUs and accelerators. Current task graph schedulers provide APIs, directives, and compilers to schedule work on nodes; however, many fail to expose the locality of data and often use a single address space to represent memory resulting in inefficient data transfer patterns for accelerators. HTGS merges dataflow and traditional task graph schedulers into a novel model to assist developers in exposing the parallelism and data locality of their algorithm. With the HTGS model, an algorithm is represented at a high level of abstraction and modularizes the computationally intensive components as a series of concurrent tasks. Using this approach, the model explicitly defines memory for each address space and provides interfaces to express the locality of data between tasks. The result achieves the full performance of the node comparable to the best of breed implementations of algorithms such as matrix multiplication and LU decomposition. The performance gains are demonstrated with a modest effort using the HTGS C++ API, which improves programmer productivity with obtaining that performance. </p>