OpenRaiser/Intern-Atlas huggingface dataset:
Policy Recognition in the Abstract Hidden Markov Model
Venue: arXiv cs.AI 2011
Year: 2011

In this paper, we present a method for recognising an agent's behaviour in dynamic, noisy, uncertain domains, and across multiple levels of abstraction. We term this problem on-line plan recognition under uncertainty and view it generally as probabilistic inference on the stochastic process representing the execution of the agent's plan. Our contributions in this paper are twofold. In terms of probabilistic inference, we introduce the Abstract Hidden Markov Model (AHMM), a novel type of stochastic processes, provide its dynamic Bayesian network (DBN) structure and analyse the properties of this network. We then describe an application of the Rao-Blackwellised Particle Filter to the AHMM which allows us to construct an efficient, hybrid inference method for this model. In terms of plan recognition, we propose a novel plan recognition framework based on the AHMM as the plan execution model. The Rao-Blackwellised hybrid inference for AHMM can take advantage of the independence properties inherent in a model of plan execution, leading to an algorithm for online probabilistic plan recognition that scales well with the number of levels in the plan hierarchy. This illustrates that while stochastic models for plan execution can be complex, they exhibit special structures which, if exploited, can lead to efficient plan recognition algorithms. We demonstrate the usefulness of the AHMM framework via a behaviour recognition system in a complex spatial environment using distributed video surveillance data.
Simulating the Electroweak Phase Transition: Sonification of Bubble Nucleation
Venue: arXiv cs.SD 2011
Year: 2011

As an applicaton of sonification, a simulation of the early universe was developed to portray a phase transition that occurred shortly after the Big Bang. The Standard Model of particle physics postulates that a hypothetical particle, the Higgs boson, is responsible for the breaking of the symmetry between the electromagnetic force and the weak force. This phase transition may have been responsible for triggering Baryogenesis, the generation of an abundance of matter over anti-matter. This hypothesis is known as Electroweak Baryogenesis. In this simulation, aspects of bubble nucleation in Standard Model Electroweak Baryogenesis were examined and modeled using Mathematica, and sonified using SuperCollider3. The resulting simulation, which has been used for pedagogical purposes by one of the authors, suggests interesting possibilities for the integration of science and aesthetics as well as auditory perception. The sonification component in particular also had the unexpected benefit of being useful in debugging the Mathematica code.
Semantics for Possibilistic Disjunctive Programs
Venue: arXiv cs.AI 2011
Year: 2011

In this paper, a possibilistic disjunctive logic programming approach for modeling uncertain, incomplete and inconsistent information is defined. This approach introduces the use of possibilistic disjunctive clauses which are able to capture incomplete information and incomplete states of a knowledge base at the same time. By considering a possibilistic logic program as a possibilistic logic theory, a construction of a possibilistic logic programming semantic based on answer sets and the proof theory of possibilistic logic is defined. It shows that this possibilistic semantics for disjunctive logic programs can be characterized by a fixed-point operator. It is also shown that the suggested possibilistic semantics can be computed by a resolution algorithm and the consideration of optimal refutations from a possibilistic logic theory. In order to manage inconsistent possibilistic logic programs, a preference criterion between inconsistent possibilistic models is defined; in addition, the approach of cuts for restoring consistency of an inconsistent possibilistic knowledge base is adopted. The approach is illustrated in a medical scenario.
An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms
Venue: arXiv cs.GT 2011
Year: 2011

This paper presents a new exponential lower bound for the two most popular deterministic variants of the strategy improvement algorithms for solving parity, mean payoff, discounted payoff and simple stochastic games. The first variant improves every node in each step maximizing the current valuation locally, whereas the second variant computes the globally optimal improvement in each step. We outline families of games on which both variants require exponentially many strategy iterations.
A Fast Affine Projection Algorithm Based on Matching Pursuit in Adaptive Noise Cancellation for Speech Enhancement
Venue: arXiv cs.SD 2011
Year: 2011

In many application of noise cancellation, the changes in signal characteristics could be quite fast. This requires the utilization of adaptive algorithms, which converge rapidly. Least Mean Squares (LMS) adaptive filters have been used in a wide range of signal processing application. The Recursive Least Squares (RLS) algorithm has established itself as the "ultimate" adaptive filtering algorithm in the sense that it is the adaptive filter exhibiting the best convergence behavior. Unfortunately, practical implementations of the algorithm are often associated with high computational complexity and/or poor numerical properties. Recently adaptive filtering was presented that was based on Matching Pursuits, have a nice tradeoff between complexity and the convergence speed. This paper describes a new approach for noise cancellation in speech enhancement using the new adaptive filtering algorithm named fast affine projection algorithm (FAPA). The simulation results demonstrate the good performance of the FAPA in attenuating the noise.
Studying and Classification of the Most Significant Malicious Software
Venue: arXiv cs.CR 2011
Year: 2011

As the cost of information processing and Internet accessibility falls, most organizations are becoming increasingly vulnerable to potential cyber threats which its rate has been dramatically increasing every year in recent times. In this paper, we study, discuss and classify the most significant malicious software: viruses, Trojans, worms, adware and pornware which have made step forward in the science of Virology.
Ice-Creams and Wedge Graphs
Venue: arXiv cs.CG 2011
Year: 2011

What is the minimum angle $α>0$ such that given any set of $α$-directional antennas (that is, antennas each of which can communicate along a wedge of angle $α$), one can always assign a direction to each antenna such that the resulting communication graph is connected? Here two antennas are connected by an edge if and only if each lies in the wedge assigned to the other. This problem was recently presented by Carmi, Katz, Lotker, and Rosén \cite{CKLR10} who also found the minimum such $α$ namely $α=\fracπ{3}$. In this paper we give a simple proof of this result. Moreover, we obtain a much stronger and optimal result (see Theorem \ref{theorem:main}) saying in particular that one can chose the directions of the antennas so that the communication graph has diameter $\le 4$. Our main tool is a surprisingly basic geometric lemma that is of independent interest. We show that for every compact convex set $S$ in the plane and every $0 < α< π$, there exist a point $O$ and two supporting lines to $S$ passing through $O$ and touching $S$ at two \emph{single points} $X$ and $Y$, respectively, such that $|OX|=|OY|$ and the angle between the two lines is $α$.
Impact of Mobility on MIMO Green Wireless Systems
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies the impact of mobility on the power consumption of wireless networks. With increasing mobility, we show that the network should dedicate a non negligible fraction of the useful rate to estimate the different degrees of freedom. In order to keep the rate constant, we quantify the increase of power required for several cases of interest. In the case of a point to point MIMO link, we calculate the minimum transmit power required for a target rate and outage probability as a function of the coherence time and the number of antennas. Interestingly, the results show that there is an optimal number of antennas to be used for a given coherence time and power consumption. This provides a lower bound limit on the minimum power required for maintaining a green network.
Computable Bounds for Rate Distortion with Feed-Forward for Stationary and Ergodic Sources
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we consider the rate distortion problem of discrete-time, ergodic, and stationary sources with feed forward at the receiver. We derive a sequence of achievable and computable rates that converge to the feed-forward rate distortion. We show that, for ergodic and stationary sources, the rate {align} R_n(D)=\frac{1}{n}\min I(\hat{X}^n\rightarrow X^n){align} is achievable for any $n$, where the minimization is taken over the transition conditioning probability $p(\hat{x}^n|x^n)$ such that $\ex{}{d(X^n,\hat{X}^n)}\leq D$. The limit of $R_n(D)$ exists and is the feed-forward rate distortion. We follow Gallager's proof where there is no feed-forward and, with appropriate modification, obtain our result. We provide an algorithm for calculating $R_n(D)$ using the alternating minimization procedure, and present several numerical examples. We also present a dual form for the optimization of $R_n(D)$, and transform it into a geometric programming problem.
Complexity Analysis of Vario-eta through Structure
Venue: arXiv cs.LG 2011
Year: 2011

Graph-based representations of images have recently acquired an important role for classification purposes within the context of machine learning approaches. The underlying idea is to consider that relevant information of an image is implicitly encoded into the relationships between more basic entities that compose by themselves the whole image. The classification problem is then reformulated in terms of an optimization problem usually solved by a gradient-based search procedure. Vario-eta through structure is an approximate second order stochastic optimization technique that achieves a good trade-off between speed of convergence and the computational effort required. However, the robustness of this technique for large scale problems has not been yet assessed. In this paper we firstly provide a theoretical justification of the assumptions made by this optimization procedure. Secondly, a complexity analysis of the algorithm is performed to prove its suitability for large scale learning problems.
Open-loop multi-channel inversion of room impulse response
Venue: arXiv cs.SD 2011
Year: 2011

This paper considers methods for audio display in a CAVE-type virtual reality theater, a 3 m cube with displays covering all six rigid faces. Headphones are possible since the user's headgear continuously measures ear positions, but loudspeakers are preferable since they enhance the sense of total immersion. The proposed solution consists of open-loop acoustic point control. The transfer function, a matrix of room frequency responses from the loudspeakers to the ears of the user, is inverted using multi-channel inversion methods, to create exactly the desired sound field at the user's ears. The inverse transfer function is constructed from impulse responses simulated by the image source method. This technique is validated by measuring a 2x2 matrix transfer function, simulating a transfer function with the same geometry, and filtering the measured transfer function through the inverse of the simulation. Since accuracy of the image source method decreases with time, inversion performance is improved by windowing the simulated response prior to inversion. Parameters of the simulation and inversion are adjusted to minimize residual reverberant energy; the best-case dereverberation ratio is 10 dB.
Improving BDD Based Symbolic Model Checking with Isomorphism Exploiting Transition Relations
Venue: arXiv cs.LO 2011
Year: 2011

Symbolic model checking by using BDDs has greatly improved the applicability of model checking. Nevertheless, BDD based symbolic model checking can still be very memory and time consuming. One main reason is the complex transition relation of systems. Sometimes, it is even not possible to generate the transition relation, due to its exhaustive memory requirements. To diminish this problem, the use of partitioned transition relations has been proposed. However, there are still systems which can not be verified at all. Furthermore, if the granularity of the partitions is too fine, the time required for verification may increase. In this paper we target the symbolic verification of asynchronous concurrent systems. For such systems we present an approach which uses similarities in the transition relation to get further memory reductions and runtime improvements. By applying our approach, even the verification of systems with an previously intractable transition relation becomes feasible.
Type Inference for Bimorphic Recursion
Venue: arXiv cs.LO 2011
Year: 2011

This paper proposes bimorphic recursion, which is restricted polymorphic recursion such that every recursive call in the body of a function definition has the same type. Bimorphic recursion allows us to assign two different types to a recursively defined function: one is for its recursive calls and the other is for its calls outside its definition. Bimorphic recursion in this paper can be nested. This paper shows bimorphic recursion has principal types and decidable type inference. Hence bimorphic recursion gives us flexible typing for recursion with decidable type inference. This paper also shows that its typability becomes undecidable because of nesting of recursions when one removes the instantiation property from the bimorphic recursion.
Optimal Bounds in Parametric LTL Games
Venue: arXiv cs.GT 2011
Year: 2011

We consider graph games of infinite duration with winning conditions in parameterized linear temporal logic, where the temporal operators are equipped with variables for time bounds. In model checking such specifications were introduced as "PLTL" by Alur et al. and (in a different version called "PROMPT-LTL") by Kupferman et al.. We present an algorithm to determine optimal variable valuations that allow a player to win a game. Furthermore, we show how to determine whether a player wins a game with respect to some, infinitely many, or all valuations. All our algorithms run in doubly-exponential time; so, adding bounded temporal operators does not increase the complexity compared to solving plain LTL games.
Phase Selection Heuristics for Satisfiability Solvers
Venue: arXiv cs.LO 2011
Year: 2011

In general, a SAT Solver based on conflict-driven DPLL consists of variable selection, phase selection, Boolean Constraint Propagation, conflict analysis, clause learning and its database maintenance. Optimizing any part of these components can enhance the performance of a solver. This paper focuses on optimizing phase selection. Although the ACE (Approximation of the Combined lookahead Evaluation) weight is applied to a lookahead SAT solver such as March, so far, no conflict-driven SAT solver applies successfully the ACE weight, since computing the ACE weight is time-consuming. Here we apply the ACE weight to partial phase selection of conflict-driven SAT solvers. This can be seen as an improvement of the heuristic proposed by Jeroslow-Wang (1990). We incorporate the ACE heuristic and the existing phase selection heuristics in the new solver MPhaseSAT, and select a phase heuristic in a way similar to portfolio methods. Experimental results show that adding the ACE heuristic can improve the conflict-driven solvers. Particularly on application instances, MPhaseSAT with the ACE heuristic is significantly better than MPhaseSAT without the ACE heuristic, and even can solve a few SAT instances that remain unsolvable so far.
Volatility of Power Grids under Real-Time Pricing
Venue: arXiv cs.SY 2011
Year: 2011

The paper proposes a framework for modeling and analysis of the dynamics of supply, demand, and clearing prices in power system with real-time retail pricing and information asymmetry. Real-time retail pricing is characterized by passing on the real-time wholesale electricity prices to the end consumers, and is shown to create a closed-loop feedback system between the physical layer and the market layer of the power system. In the absence of a carefully designed control law, such direct feedback between the two layers could increase volatility and lower the system's robustness to uncertainty in demand and generation. A new notion of generalized price-elasticity is introduced, and it is shown that price volatility can be characterized in terms of the system's maximal relative price elasticity, defined as the maximal ratio of the generalized price-elasticity of consumers to that of the producers. As this ratio increases, the system becomes more volatile, and eventually, unstable. As new demand response technologies and distributed storage increase the price-elasticity of demand, the architecture under examination is likely to lead to increased volatility and possibly instability. This highlights the need for assessing architecture systematically and in advance, in order to optimally strike the trade-offs between volatility, economic efficiency, and system reliability.
Finding a Path is Harder than Finding a Tree
Venue: arXiv cs.AI 2011
Year: 2011

I consider the problem of learning an optimal path graphical model from data and show the problem to be NP-hard for the maximum likelihood and minimum description length approaches and a Bayesian approach. This hardness result holds despite the fact that the problem is a restriction of the polynomially solvable problem of finding the optimal tree graphical model.
A Critical Assessment of Benchmark Comparison in Planning
Venue: arXiv cs.AI 2011
Year: 2011

Recent trends in planning research have led to empirical comparison becoming commonplace. The field has started to settle into a methodology for such comparisons, which for obvious practical reasons requires running a subset of planners on a subset of problems. In this paper, we characterize the methodology and examine eight implicit assumptions about the problems, planners and metrics used in many of these comparisons. The problem assumptions are: PR1) the performance of a general purpose planner should not be penalized/biased if executed on a sampling of problems and domains, PR2) minor syntactic differences in representation do not affect performance, and PR3) problems should be solvable by STRIPS capable planners unless they require ADL. The planner assumptions are: PL1) the latest version of a planner is the best one to use, PL2) default parameter settings approximate good performance, and PL3) time cut-offs do not unduly bias outcome. The metrics assumptions are: M1) performance degrades similarly for each planner when run on degraded runtime environments (e.g., machine platform) and M2) the number of plan steps distinguishes performance. We find that most of these assumptions are not supported empirically; in particular, that planners are affected differently by these assumptions. We conclude with a call to the community to devote research resources to improving the state of the practice and especially to enhancing the available benchmark problems.
SMOTE: Synthetic Minority Over-sampling Technique
Venue: arXiv cs.AI 2011
Year: 2011

An approach to the construction of classifiers from imbalanced datasets is described. A dataset is imbalanced if the classification categories are not approximately equally represented. Often real-world data sets are predominately composed of "normal" examples with only a small percentage of "abnormal" or "interesting" examples. It is also the case that the cost of misclassifying an abnormal (interesting) example as a normal example is often much higher than the cost of the reverse error. Under-sampling of the majority (normal) class has been proposed as a good means of increasing the sensitivity of a classifier to the minority class. This paper shows that a combination of our method of over-sampling the minority (abnormal) class and under-sampling the majority (normal) class can achieve better classifier performance (in ROC space) than only under-sampling the majority class. This paper also shows that a combination of our method of over-sampling the minority class and under-sampling the majority class can achieve better classifier performance (in ROC space) than varying the loss ratios in Ripper or class priors in Naive Bayes. Our method of over-sampling the minority class involves creating synthetic minority class examples. Experiments are performed using C4.5, Ripper and a Naive Bayes classifier. The method is evaluated using the area under the Receiver Operating Characteristic curve (AUC) and the ROC convex hull strategy.
When do Numbers Really Matter?
Venue: arXiv cs.AI 2011
Year: 2011

Common wisdom has it that small distinctions in the probabilities (parameters) quantifying a belief network do not matter much for the results of probabilistic queries. Yet, one can develop realistic scenarios under which small variations in network parameters can lead to significant changes in computed queries. A pending theoretical question is then to analytically characterize parameter changes that do or do not matter. In this paper, we study the sensitivity of probabilistic queries to changes in network parameters and prove some tight bounds on the impact that such parameters can have on queries. Our analytic results pinpoint some interesting situations under which parameter changes do or do not matter. These results are important for knowledge engineers as they help them identify influential network parameters. They also help explain some of the previous experimental results and observations with regards to network robustness against parameter changes.
Monitoring Teams by Overhearing: A Multi-Agent Plan-Recognition Approach
Venue: arXiv cs.AI 2011
Year: 2011

Recent years are seeing an increasing need for on-line monitoring of teams of cooperating agents, e.g., for visualization, or performance tracking. However, in monitoring deployed teams, we often cannot rely on the agents to always communicate their state to the monitoring system. This paper presents a non-intrusive approach to monitoring by 'overhearing', where the monitored team's state is inferred (via plan-recognition) from team-members' routine communications, exchanged as part of their coordinated task execution, and observed (overheard) by the monitoring system. Key challenges in this approach include the demanding run-time requirements of monitoring, the scarceness of observations (increasing monitoring uncertainty), and the need to scale-up monitoring to address potentially large teams. To address these, we present a set of complementary novel techniques, exploiting knowledge of the social structures and procedures in the monitored team: (i) an efficient probabilistic plan-recognition algorithm, well-suited for processing communications as observations; (ii) an approach to exploiting knowledge of the team's social behavior to predict future observations during execution (reducing monitoring uncertainty); and (iii) monitoring algorithms that trade expressivity for scalability, representing only certain useful monitoring hypotheses, but allowing for any number of agents and their different activities to be represented in a single coherent entity. We present an empirical evaluation of these techniques, in combination and apart, in monitoring a deployed team of agents, running on machines physically distributed across the country, and engaged in complex, dynamic task execution. We also compare the performance of these techniques to human expert and novice monitors, and show that the techniques presented are capable of monitoring at human-expert levels, despite the difficulty of the task.