OpenRaiser/Intern-Atlas huggingface dataset:
Web Analytics for Security Informatics
Venue: arXiv cs.SI 2012
Year: 2012

An enormous volume of security-relevant information is present on the Web, for instance in the content produced each day by millions of bloggers worldwide, but discovering and making sense of these data is very challenging. This paper considers the problem of exploring and analyzing the Web to realize three fundamental objectives: 1.) security relevant information discovery; 2.) target situational awareness, typically by making (near) real-time inferences concerning events and activities from available observations; and 3.) predictive analysis, to include providing early warning for crises and forming predictions regarding likely outcomes of emerging issues and contemplated interventions. The proposed approach involves collecting and integrating three types of Web data, textual, relational, and temporal, to perform assessments and generate insights that would be difficult or impossible to obtain using standard methods. We demonstrate the efficacy of the framework by summarizing a number of successful real-world deployments of the methodology.
Stability Analysis Of Delayed System Using Bodes Integral
Venue: arXiv cs.SY 2012
Year: 2012

The PID controller parameters can be adjusted in such a manner that it gives the desired frequency response and the results are found using the Bodes integral formula in order to adjust the slope of the nyquist curve in a desired manner. The same idea is applied for plants with time delay . The same has also been done in a new approach . The delay term is approximated as a transfer function using Pade approximation and then the Bode integral is used to determine the controller parameters. Both the methodologies are demonstrated with MATLAB simulation of representative plants and accompanying PID controllers. A proper comparison of the two methodologies is also done. The PID controller parameters are also tuned using a real coded Genetic Algorithm (GA) and a proper comparison is done between the three methods.
Nonlinear Instabilities in D2TCP-II
Venue: arXiv cs.NI 2012
Year: 2012

In the era of heavy-duty transmission control protocols (TCP), adapted for extremely hi-bandwidth datacenters, the fundamental question of stable interaction with either proposed active queue management(AQM) or popularly discussed Random Early Detection (RED) remains a hotly debated issue. While there are claims of "oscillation" only dynamical behavior, there are equally large number of claims which demonstrate the chaotic nature of different flavors of TCP and their AQM interaction. In this work, we provide a sound and analytical mathematical model of DTCP/D2TCP and study their interaction with threshold based packet marking policy. Our work shows that for a simple scenario this interaction is chaotic in nature and has large variability in dynamical behavior over orders of magnitude changes in parameter range as demonstrated by bifurcation diagrams. We conclude with numerical simulation evidence that chaotic behavior of protocols is inherent in their design which they inherit from their early vanilla TCP days, and it has serious implications for data-center throughput, load batching and collapse in Incast kind of scenario.
Learning Hierarchical Object Maps Of Non-Stationary Environments with mobile robots
Venue: arXiv cs.LG 2012
Year: 2012

Building models, or maps, of robot environments is a highly active research area; however, most existing techniques construct unstructured maps and assume static environments. In this paper, we present an algorithm for learning object models of non-stationary objects found in office-type environments. Our algorithm exploits the fact that many objects found in office environments look alike (e.g., chairs, recycling bins). It does so through a two-level hierarchical representation, which links individual objects with generic shape templates of object classes. We derive an approximate EM algorithm for learning shape parameters at both levels of the hierarchy, using local occupancy grid maps for representing shape. Additionally, we develop a Bayesian model selection algorithm that enables the robot to estimate the total number of objects and object templates in the environment. Experimental results using a real robot equipped with a laser range finder indicate that our approach performs well at learning object-based maps of simple office environments. The approach outperforms a previously developed non-hierarchical algorithm that models objects but lacks class templates.
Generalized Instrumental Variables
Venue: arXiv cs.AI 2012
Year: 2012

This paper concerns the assessment of direct causal effects from a combination of: (i) non-experimental data, and (ii) qualitative domain knowledge. Domain knowledge is encoded in the form of a directed acyclic graph (DAG), in which all interactions are assumed linear, and some variables are presumed to be unobserved. We provide a generalization of the well-known method of Instrumental Variables, which allows its application to models with few conditional independeces.
Interpolating Conditional Density Trees
Venue: arXiv cs.LG 2012
Year: 2012

Joint distributions over many variables are frequently modeled by decomposing them into products of simpler, lower-dimensional conditional distributions, such as in sparsely connected Bayesian networks. However, automatically learning such models can be very computationally expensive when there are many datapoints and many continuous variables with complex nonlinear relationships, particularly when no good ways of decomposing the joint distribution are known a priori. In such situations, previous research has generally focused on the use of discretization techniques in which each continuous variable has a single discretization that is used throughout the entire network. \ In this paper, we present and compare a wide variety of tree-based algorithms for learning and evaluating conditional density estimates over continuous variables. These trees can be thought of as discretizations that vary according to the particular interactions being modeled; however, the density within a given leaf of the tree need not be assumed constant, and we show that such nonuniform leaf densities lead to more accurate density estimation. We have developed Bayesian network structure-learning algorithms that employ these tree-based conditional density representations, and we show that they can be used to practically learn complex joint probability models over dozens of continuous variables from thousands of datapoints. We focus on finding models that are simultaneously accurate, fast to learn, and fast to evaluate once they are learned.
Distributed Planning in Hierarchical Factored MDPs
Venue: arXiv cs.AI 2012
Year: 2012

We present a principled and efficient planning algorithm for collaborative multiagent dynamical systems. All computation, during both the planning and the execution phases, is distributed among the agents; each agent only needs to model and plan for a small part of the system. Each of these local subsystems is small, but once they are combined they can represent an exponentially larger problem. The subsystems are connected through a subsystem hierarchy. Coordination and communication between the agents is not imposed, but derived directly from the structure of this hierarchy. A globally consistent plan is achieved by a message passing algorithm, where messages correspond to natural local reward functions and are computed by local linear programs; another message passing algorithm allows us to execute the resulting policy. When two portions of the hierarchy share the same structure, our algorithm can reuse plans and messages to speed up computation.
Coordinates: Probabilistic Forecasting of Presence and Availability
Venue: arXiv cs.HC 2012
Year: 2012

We present methods employed in Coordinate, a prototype service that supports collaboration and communication by learning predictive models that provide forecasts of users s AND availability.We describe how data IS collected about USER activity AND proximity FROM multiple devices, IN addition TO analysis OF the content OF users, the time of day, and day of week. We review applications of presence forecasting embedded in the Priorities application and then present details of the Coordinate service that was informed by the earlier efforts.
A Bayesian Network Scoring Metric That Is Based On Globally Uniform Parameter Priors
Venue: arXiv cs.AI 2012
Year: 2012

We introduce a new Bayesian network (BN) scoring metric called the Global Uniform (GU) metric. This metric is based on a particular type of default parameter prior. Such priors may be useful when a BN developer is not willing or able to specify domain-specific parameter priors. The GU parameter prior specifies that every prior joint probability distribution P consistent with a BN structure S is considered to be equally likely. Distribution P is consistent with S if P includes just the set of independence relations defined by S. We show that the GU metric addresses some undesirable behavior of the BDeu and K2 Bayesian network scoring metrics, which also use particular forms of default parameter priors. A closed form formula for computing GU for special classes of BNs is derived. Efficiently computing GU for an arbitrary BN remains an open problem.
General Lower Bounds based on Computer Generated Higher Order Expansions
Venue: arXiv cs.NA 2012
Year: 2012

In this article we show the rough outline of a computer algorithm to generate lower bounds on the exponential function of (in principle) arbitrary precision. We implemented this to generate all necessary analytic terms for the Boltzmann machine partition function thus leading to lower bounds of any order. It turns out that the extra variational parameters can be optimized analytically. We show that bounds upto nineth order are still reasonably calculable in practical situations. The generated terms can also be used as extra correction terms (beyond TAP) in mean field expansions.
Monitoring a Complez Physical System using a Hybrid Dynamic Bayes Net
Venue: arXiv cs.AI 2012
Year: 2012

The Reverse Water Gas Shift system (RWGS) is a complex physical system designed to produce oxygen from the carbon dioxide atmosphere on Mars. If sent to Mars, it would operate without human supervision, thus requiring a reliable automated system for monitoring and control. The RWGS presents many challenges typical of real-world systems, including: noisy and biased sensors, nonlinear behavior, effects that are manifested over different time granularities, and unobservability of many important quantities. In this paper we model the RWGS using a hybrid (discrete/continuous) Dynamic Bayesian Network (DBN), where the state at each time slice contains 33 discrete and 184 continuous variables. We show how the system state can be tracked using probabilistic inference over the model. We discuss how to deal with the various challenges presented by the RWGS, providing a suite of techniques that are likely to be useful in a wide range of applications. In particular, we describe a general framework for dealing with nonlinear behavior using numerical integration techniques, extending the successful Unscented Filter. We also show how to use a fixed-point computation to deal with effects that develop at different time scales, specifically rapid changes occurring during slowly changing processes. We test our model using real data collected from the RWGS, demonstrating the feasibility of hybrid DBNs for monitoring complex real-world physical systems.
Decayed MCMC Filtering
Venue: arXiv cs.AI 2012
Year: 2012

Filtering---estimating the state of a partially observable Markov process from a sequence of observations---is one of the most widely studied problems in control theory, AI, and computational statistics. Exact computation of the posterior distribution is generally intractable for large discrete systems and for nonlinear continuous systems, so a good deal of effort has gone into developing robust approximation algorithms. This paper describes a simple stochastic approximation algorithm for filtering called {em decayed MCMC}. The algorithm applies Markov chain Monte Carlo sampling to the space of state trajectories using a proposal distribution that favours flips of more recent state variables. The formal analysis of the algorithm involves a generalization of standard coupling arguments for MCMC convergence. We prove that for any ergodic underlying Markov process, the convergence time of decayed MCMC with inverse-polynomial decay remains bounded as the length of the observation sequence grows. We show experimentally that decayed MCMC is at least competitive with other approximation algorithms such as particle filtering.
Real-valued All-Dimensions search: Low-overhead rapid searching over subsets of attributes
Venue: arXiv cs.AI 2012
Year: 2012

This paper is about searching the combinatorial space of contingency tables during the inner loop of a nonlinear statistical optimization. Examples of this operation in various data analytic communities include searching for nonlinear combinations of attributes that contribute significantly to a regression (Statistics), searching for items to include in a decision list (machine learning) and association rule hunting (Data Mining). This paper investigates a new, efficient approach to this class of problems, called RADSEARCH (Real-valued All-Dimensions-tree Search). RADSEARCH finds the global optimum, and this gives us the opportunity to empirically evaluate the question: apart from algorithmic elegance what does this attention to optimality buy us? We compare RADSEARCH with other recent successful search algorithms such as CN2, PRIM, APriori, OPUS and DenseMiner. Finally, we introduce RADREG, a new regression algorithm for learning real-valued outputs based on RADSEARCHing for high-order interactions.
Continuous Time Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

In this paper we present a language for finite state continuous time Bayesian networks (CTBNs), which describe structured stochastic processes that evolve over continuous time. The state of the system is decomposed into a set of local variables whose values change over time. The dynamics of the system are described by specifying the behavior of each local variable as a function of its parents in a directed (possibly cyclic) graph. The model specifies, at any given point in time, the distribution over two aspects: when a local variable changes its value and the next value it takes. These distributions are determined by the variable s CURRENT value AND the CURRENT VALUES OF its parents IN the graph.More formally, each variable IS modelled AS a finite state continuous time Markov process whose transition intensities are functions OF its parents.We present a probabilistic semantics FOR the language IN terms OF the generative model a CTBN defines OVER sequences OF events.We list types OF queries one might ask OF a CTBN, discuss the conceptual AND computational difficulties associated WITH exact inference, AND provide an algorithm FOR approximate inference which takes advantage OF the structure within the process.
On the Testable Implications of Causal Models with Hidden Variables
Venue: arXiv cs.AI 2012
Year: 2012

The validity OF a causal model can be tested ONLY IF the model imposes constraints ON the probability distribution that governs the generated data. IN the presence OF unmeasured variables, causal models may impose two types OF constraints : conditional independencies, AS READ through the d - separation criterion, AND functional constraints, FOR which no general criterion IS available.This paper offers a systematic way OF identifying functional constraints AND, thus, facilitates the task OF testing causal models AS well AS inferring such models FROM data.
When you talk about "Information processing" what actually do you have in mind?
Venue: arXiv cs.AI 2012
Year: 2012

"Information Processing" is a recently launched buzzword whose meaning is vague and obscure even for the majority of its users. The reason for this is the lack of a suitable definition for the term "information". In my attempt to amend this bizarre situation, I have realized that, following the insights of Kolmogorov's Complexity theory, information can be defined as a description of structures observable in a given data set. Two types of structures could be easily distinguished in every data set - in this regard, two types of information (information descriptions) should be designated: physical information and semantic information. Kolmogorov's theory also posits that the information descriptions should be provided as a linguistic text structure. This inevitably leads us to an assertion that information processing has to be seen as a kind of text processing. The idea is not new - inspired by the observation that human information processing is deeply rooted in natural language handling customs, Lotfi Zadeh and his followers have introduced the so-called "Computing With Words" paradigm. Despite of promotional efforts, the idea is not taking off yet. The reason - a lack of a coherent understanding of what should be called "information", and, as a result, misleading research roadmaps and objectives. I hope my humble attempt to clarify these issues would be helpful in avoiding common traps and pitfalls.
Collusion in Unrepeated, First-Price Auctions with an Uncertain Number of Participants
Venue: arXiv cs.GT 2012
Year: 2012

We consider the question of whether collusion among bidders (a "bidding ring") can be supported in equilibrium of unrepeated first-price auctions. Unlike previous work on the topic such as that by McAfee and McMillan [1992] and Marshall and Marx [2007], we do not assume that non-colluding agents have perfect knowledge about the number of colluding agents whose bids are suppressed by the bidding ring, and indeed even allow for the existence of multiple cartels. Furthermore, while we treat the association of bidders with bidding rings as exogenous, we allow bidders to make strategic decisions about whether to join bidding rings when invited. We identify a bidding ring protocol that results in an efficient allocation in Bayes{Nash equilibrium, under which non-colluding agents bid straightforwardly, and colluding agents join bidding rings when invited and truthfully declare their valuations to the ring center. We show that bidding rings benefit ring centers and all agents, both members and non-members of bidding rings, at the auctioneer's expense. The techniques we introduce in this paper may also be useful for reasoning about other problems in which agents have asymmetric information about a setting.
Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme
Venue: arXiv cs.DS 2012
Year: 2012

We give a polynomial-time approximation scheme for the generalization of Huffman Coding in which codeword letters have non-uniform costs (as in Morse code, where the dash is twice as long as the dot). The algorithm computes a (1+epsilon)-approximate solution in time O(n + f(epsilon) log^3 n), where n is the input size.
Semi-local string comparison: algorithmic techniques and applications
Venue: arXiv cs.DS 2013
Year: 2013

A classical measure of string comparison is given by the longest common subsequence (LCS) problem on a pair of strings. We consider its generalisation, called the semi-local LCS problem, which arises naturally in many string-related problems. The semi-local LCS problem asks for the LCS scores for each of the input strings against every substring of the other input string, and for every prefix of each input string against every suffix of the other input string. Such a comparison pattern provides a much more detailed picture of string similarity than a single LCS score; it also arises naturally in many string-related problems. In fact, the semi-local LCS problem turns out to be fundamental for string comparison, providing a powerful and flexible alternative to classical dynamic programming. It is especially useful when the input to a string comparison problem may not be available all at once: for example, comparison of dynamically changing strings; comparison of compressed strings; parallel string comparison. The same approach can also be applied to permutation strings, providing efficient solutions for local versions of the longest increasing subsequence (LIS) problem, and for the problem of computing a maximum clique in a circle graph. Furthermore, the semi-local LCS problem turns out to have surprising connections in a few seemingly unrelated fields, such as computational geometry and algebra of semigroups. This work is devoted to exploring the structure of the semi-local LCS problem, its efficient solutions, and its applications in string comparison and other related areas, including computational molecular biology.
A Synthesizer Based on Frequency-Phase Analysis and Square Waves
Venue: arXiv cs.SD 2013
Year: 2013

This article introduces an effective generalization of the polar flavor of the Fourier Theorem based on a new method of analysis. Under the premises of the new theory an ample class of functions become viable as bases, with the further advantage of using the same basis for analysis and reconstruction. In fact other tools, like the wavelets, admit specially built nonorthogonal bases but require different bases for analysis and reconstruction (biorthogonal and dual bases) and vectorial coordinates; this renders those systems unintuitive and computing intensive. As an example of the advantages of the new generalization of the Fourier Theorem, this paper introduces a novel method for the synthesis that is based on frequency-phase series of square waves (the equivalent of the polar Fourier Theorem but for nonorthogonal bases). The resulting synthesizer is very efficient needing only few components, frugal in terms of computing needs, and viable for many applications.
Locating Restricted Facilities on Binary Maps
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we consider several facility location problems with applications to cost and social welfare optimization, when the area map is encoded as a binary (0,1) mxn matrix. We present algorithmic solutions for all the problems. Some cases are too particular to be used in practical situations, but they are at least a starting point for more generic solutions.
Periodic Single-Pass Instruction Sequences
Venue: arXiv cs.PL 2013
Year: 2013

A program is a finite piece of data that produces a (possibly infinite) sequence of primitive instructions. From scratch we develop a linear notation for sequential, imperative programs, using a familiar class of primitive instructions and so-called repeat instructions, a particular type of control instructions. The resulting mathematical structure is a semigroup. We relate this set of programs to program algebra (PGA) and show that a particular subsemigroup is a carrier for PGA by providing axioms for single-pass congruence, structural congruence, and thread extraction. This subsemigroup characterizes periodic single-pass instruction sequences and provides a direct basis for PGA's toolset.
Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
Venue: arXiv cs.IT 2013
Year: 2013

The current best asymptotic lower bound on the minimum distance of quantum LDPC codes with fixed non-zero rate is logarithmic in the blocklength. We propose a construction of quantum LDPC codes with fixed non-zero rate and prove that the minimum distance grows proportionally to the square root of the blocklength.
Subshifts as Models for MSO Logic
Venue: arXiv cs.DM 2013
Year: 2013

We study the Monadic Second Order (MSO) Hierarchy over colourings of the discrete plane, and draw links between classes of formula and classes of subshifts. We give a characterization of existential MSO in terms of projections of tilings, and of universal sentences in terms of combinations of "pattern counting" subshifts. Conversely, we characterise logic fragments corresponding to various classes of subshifts (subshifts of finite type, sofic subshifts, all subshifts). Finally, we show by a separation result how the situation here is different from the case of tiling pictures studied earlier by Giammarresi et al.