OpenRaiser/Intern-Atlas huggingface dataset:
Secure Communication Via an Untrusted Non-Regenerative Relay in Fading Channels
Venue: arXiv cs.IT 2013
Year: 2013

We investigate a relay network where the source can potentially utilize an untrusted non-regenerative relay to augment its direct transmission of a confidential message to the destination. Since the relay is untrusted, it is desirable to protect the confidential data from it while simultaneously making use of it to increase the reliability of the transmission. We first examine the secrecy outage probability (SOP) of the network assuming a single antenna relay, and calculate the exact SOP for three different schemes: direct transmission without using the relay, conventional non-regenerative relaying, and cooperative jamming by the destination. Subsequently, we conduct an asymptotic analysis of the SOPs to determine the optimal policies in different operating regimes. We then generalize to the multi-antenna relay case and investigate the impact of the number of relay antennas on the secrecy performance. Finally, we study a scenario where the relay has only a single RF chain which necessitates an antenna selection scheme, and we show that unlike the case where all antennas are used, under certain conditions the cooperative jamming scheme with antenna selection provides a diversity advantage for the receiver. Numerical results are presented to verify the theoretical predictions of the preferred transmission policies.
Fiedler Vectors and Elongation of Graphs: A Threshold Phenomenon on a Particular Class of Trees
Venue: arXiv cs.DM 2013
Year: 2013

Let $G$ be a graph. Its laplacian matrix $L(G)$ is positive and we consider eigenvectors of its first non-null eigenvalue that are called Fiedler vector. They have been intensively used in spectral partitioning problems due to their good empirical properties. More recently Fiedler vectors have been also popularized in the computer graphics community to describe elongation of shapes. In more technical terms, authors have conjectured that extrema of Fiedler vectors can yield the diameter of a graph. In this work we present (FED) property for a graph $G$, i.e. the fact that diameter of a graph can be obtain by Fiedler vectors. We study in detail a parametric family of trees that gives indeed a counter example for the previous conjecture but reveals a threshold phenomenon for (FED) property. We end by an exhaustive enumeration of trees with at most 20 vertices for which (FED) is true and some perspectives.
Parametric Schedulability Analysis of Fixed Priority Real-Time Distributed Systems
Venue: arXiv cs.DC 2013
Year: 2013

Parametric analysis is a powerful tool for designing modern embedded systems, because it permits to explore the space of design parameters, and to check the robustness of the system with respect to variations of some uncontrollable variable. In this paper, we address the problem of parametric schedulability analysis of distributed real-time systems scheduled by fixed priority. In particular, we propose two different approaches to parametric analysis: the first one is a novel technique based on classical schedulability analysis, whereas the second approach is based on model checking of Parametric Timed Automata (PTA). The proposed analytic method extends existing sensitivity analysis for single processors to the case of a distributed system, supporting preemptive and non-preemptive scheduling, jitters and unconstrained deadlines. Parametric Timed Automata are used to model all possible behaviours of a distributed system, and therefore it is a necessary and sufficient analysis. Both techniques have been implemented in two software tools, and they have been compared with classical holistic analysis on two meaningful test cases. The results show that the analytic method provides results similar to classical holistic analysis in a very efficient way, whereas the PTA approach is slower but covers the entire space of solutions.
Cloud Computing framework for Computer Vision Research:An Introduction
Venue: arXiv cs.CV 2013
Year: 2013

Cloud computing offers the potential to help scientists to process massive number of computing resources often required in machine learning application such as computer vision problems. This proposal would like to show that which benefits can be obtained from cloud in order to help medical image analysis users (including scientists, clinicians, and research institutes). As security and privacy of algorithms are important for most of algorithms inventors, these algorithms can be hidden in a cloud to allow the users to use the algorithms as a package without any access to see/change their inside. In another word, in the user part, users send their images to the cloud and configure the algorithm via an interface. In the cloud part, the algorithms are applied to this image and the results are returned back to the user. My proposal has two parts: (1) investigate the potential of cloud computing for computer vision problems and (2) study the components of a proposed cloud-based framework for medical image analysis application and develop them (depending on the length of the internship). The investigation part will involve a study on several aspects of the problem including security, usability (for medical end users of the service), appropriate programming abstractions for vision problems, scalability and resource requirements. In the second part of this proposal I am going to thoroughly study of the proposed framework components and their relations and develop them. The proposed cloud-based framework includes an integrated environment to enable scientists and clinicians to access to the previous and current medical image analysis algorithms using a handful user interface without any access to the algorithm codes and procedures.
Adaptive Sparse Channel Estimation for Time-Variant MISO Communication Systems
Venue: arXiv cs.IT 2013
Year: 2013

Channel estimation problem is one of the key technical issues in time-variant multiple-input single-output (MSIO) communication systems. To estimate the MISO channel, least mean square (LMS) algorithm is applied to adaptive channel estimation (ACE). Since the MISO channel is often described by sparse channel model, such sparsity can be exploited and then estimation performance can be improved by adaptive sparse channel estimation (ASCE) methods using sparse LMS algorithms. However, conventional ASCE methods have two main drawbacks: 1) sensitive to random scale of training signal and 2) unstable in low signal-to-noise ratio (SNR) regime. To overcome these two harmful factors, in this paper, we propose a novel ASCE method using normalized LMS (NLMS) algorithm (ASCE-NLMS). In addition, we also proposed an improved ASCE method using normalized least mean fourth (NLMF) algorithm (ASCE-NLMF). Two proposed methods can exploit the channel sparsity effectively. Also, stability of the proposed methods is confirmed by mathematical derivation. Computer simulation results show that the proposed sparse channel estimation methods can achieve better estimation performance than conventional methods.
Characterizing and Evaluating The Impact of Software Interface Clones
Venue: arXiv cs.SE 2013
Year: 2013

Software Interfaces are meant to describe contracts governing interactions between logic modules. Interfaces, if well designed, significantly reduce software complexity and ease maintainability . However, as software evolves, the organization and the quality of software interfaces gradually deteriorate. As a consequence, this often leads to increased development cost, lower code quality and reduced reusability . Code clones are one of the most known bad smells in source code. This design defect may occur in interfaces by duplicating method/API declarations in several interfaces. Such interfaces are similar from the point of view of public services/APIs they specify, thus they indicate a bad organization of application services. In this paper, we characterize the interface clone design defect and illustrate it via examples taken from real-world open source software applications. We conduct an empirical study covering nine real-world open source software applications to quantify the presence of interface clones and evaluate their impact on interface design quality . The results of the empirical study show that interface clones are widely present in software interfaces. They also show that the presence of interface clones may cause a degradation of interface cohesion and indicate a considerable presence of code clones at implementations level.
Clique cycle-transversals in distance-hereditary graphs
Venue: arXiv cs.DM 2013
Year: 2013

A cycle-transversal of a graph G is a subset T of V(G) such that T intersects every cycle of G. A clique cycle-transversal, or cct for short, is a cycle-transversal which is a clique. Recognizing graphs which admit a cct can be done in polynomial time; however, no structural characterization of such graphs is known. We characterize distance-hereditary graphs admitting a cct in terms of forbidden induced subgraphs. This extends similar results for chordal graphs and cographs.
Sémantique des déterminants dans un cadre richement typé
Venue: arXiv cs.CL 2013
Year: 2013

The variation of word meaning according to the context leads us to enrich the type system of our syntactical and semantic analyser of French based on categorial grammars and Montague semantics (or lambda-DRT). The main advantage of a deep semantic analyse is too represent meaning by logical formulae that can be easily used e.g. for inferences. Determiners and quantifiers play a fundamental role in the construction of those formulae. But in our rich type system the usual semantic terms do not work. We propose a solution ins- pired by the tau and epsilon operators of Hilbert, kinds of generic elements and choice functions. This approach unifies the treatment of the different determi- ners and quantifiers as well as the dynamic binding of pronouns. Above all, this fully computational view fits in well within the wide coverage parser Grail, both from a theoretical and a practical viewpoint.
ContentFlow: Mapping Content to Flows in Software Defined Networks
Venue: arXiv cs.NI 2013
Year: 2013

Information-Centric Networks place content as the narrow waist of the network architecture. This allows to route based upon the content name, and not based upon the locations of the content consumer and producer. However, current Internet architecture does not support content routing at the network layer. We present ContentFlow, an Information-Centric network architecture which supports content routing by mapping the content name to an IP flow, and thus enables the use of OpenFlow switches to achieve content routing over a legacy IP architecture. ContentFlow is viewed as an evolutionary step between the current IP networking architecture, and a full fledged ICN architecture. It supports content management, content caching and content routing at the network layer, while using a legacy OpenFlow infrastructure and a modified controller. In particular, ContentFlow is transparent from the point of view of the client and the server, and can be inserted in between with no modification at either end. We have implemented ContentFlow and describe our implementation choices as well as the overall architecture specification. We evaluate the performance of ContentFlow in our testbed.
Generating target probability sequences and events
Venue: arXiv cs.CR 2013
Year: 2013

Cryptography and simulation of systems require that events of pre-defined probability be generated. This paper presents methods to generate target probability events based on the oblivious transfer protocol and target probabilistic sequences using probability distribution functions.
Exploiting Uncertain and Temporal Information in Correlation
Venue: arXiv cs.AI 2013
Year: 2013

A modelling language is described which is suitable for the correlation of information when the underlying functional model of the system is incomplete or uncertain and the temporal dependencies are imprecise. An efficient and incremental implementation is outlined which depends on cost functions satisfying certain criteria. Possibilistic logic and probability theory (as it is used in the applications targetted) satisfy these criteria.
Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
Venue: arXiv cs.AI 2013
Year: 2013

Most exact algorithms for general partially observable Markov decision processes (POMDPs) use a form of dynamic programming in which a piecewise-linear and convex representation of one value function is transformed into another. We examine variations of the "incremental pruning" method for solving this problem and compare them to earlier algorithms from theoretical and empirical perspectives. We find that incremental pruning is presently the most efficient exact method for solving POMDPs.
Defining Explanation in Probabilistic Systems
Venue: arXiv cs.AI 2013
Year: 2013

As probabilistic systems gain popularity and are coming into wider use, the need for a mechanism that explains the system's findings and recommendations becomes more critical. The system will also need a mechanism for ordering competing explanations. We examine two representative approaches to explanation in the literature - one due to Gärdenfors and one due to Pearl - and show that both suffer from significant problems. We propose an approach to defining a notion of "better explanation" that combines some of the features of both together with more recent work by Pearl and others on causality.
Structured Arc Reversal and Simulation of Dynamic Probabilistic Networks
Venue: arXiv cs.AI 2013
Year: 2013

We present an algorithm for arc reversal in Bayesian networks with tree-structured conditional probability tables, and consider some of its advantages, especially for the simulation of dynamic probabilistic networks. In particular, the method allows one to produce CPTs for nodes involved in the reversal that exploit regularities in the conditional distributions. We argue that this approach alleviates some of the overhead associated with arc reversal, plays an important role in evidence integration and can be used to restrict sampling of variables in DPNs. We also provide an algorithm that detects the dynamic irrelevance of state variables in forward simulation. This algorithm exploits the structured CPTs in a reversed network to determine, in a time-independent fashion, the conditions under which a variable does or does not need to be sampled.
Efficient Induction of Finite State Automata
Venue: arXiv cs.AI 2013
Year: 2013

This paper introduces a new algorithm for the induction if complex finite state automata from samples of behavior. The algorithm is based on information theoretic principles. The algorithm reduces the search space by many orders of magnitude over what was previously thought possible. We compare the algorithm with some existing induction techniques for finite state automata and show that the algorithm is much superior in both run time and quality of inductions.
Myopic Value of Information in Influence Diagrams
Venue: arXiv cs.AI 2013
Year: 2013

We present a method for calculation of myopic value of information in influence diagrams (Howard & Matheson, 1981) based on the strong junction tree framework (Jensen, Jensen & Dittmer, 1994). The difference in instantiation order in the influence diagrams is reflected in the corresponding junction trees by the order in which the chance nodes are marginalized. This order of marginalization can be changed by table expansion and in effect the same junction tree with expanded tables may be used for calculating the expected utility for scenarios with different instantiation order. We also compare our method to the classic method of modeling different instantiation orders in the same influence diagram.
Decision-making Under Ordinal Preferences and Comparative Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

This paper investigates the problem of finding a preference relation on a set of acts from the knowledge of an ordering on events (subsets of states of the world) describing the decision-maker (DM)s uncertainty and an ordering of consequences of acts, describing the DMs preferences. However, contrary to classical approaches to decision theory, we try to do it without resorting to any numerical representation of utility nor uncertainty, and without even using any qualitative scale on which both uncertainty and preference could be mapped. It is shown that although many axioms of Savage theory can be preserved and despite the intuitive appeal of the method for constructing a preference over acts, the approach is inconsistent with a probabilistic representation of uncertainty, but leads to the kind of uncertainty theory encountered in non-monotonic reasoning (especially preferential and rational inference), closely related to possibility theory. Moreover the method turns out to be either very little decisive or to lead to very risky decisions, although its basic principles look sound. This paper raises the question of the very possibility of purely symbolic approaches to Savage-like decision-making under uncertainty and obtains preliminary negative results.
The Complexity of Plan Existence and Evaluation in Probabilistic Domains
Venue: arXiv cs.AI 2013
Year: 2013

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with succinct representations. We find that many problems of interest are complete for a variety of complexity classes: NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. Of these, the probabilistic classes PP and NP^PP are likely to be of special interest in the field of uncertainty in artificial intelligence and are deserving of additional study. These results suggest a fruitful direction of future algorithmic development.
Algorithm Portfolio Design: Theory vs. Practice
Venue: arXiv cs.AI 2013
Year: 2013

Stochastic algorithms are among the best for solving computationally hard search and reasoning problems. The runtime of such procedures is characterized by a random variable. Different algorithms give rise to different probability distributions. One can take advantage of such differences by combining several algorithms into a portfolio, and running them in parallel or interleaving them on a single processor. We provide a detailed evaluation of the portfolio approach on distributions of hard combinatorial search problems. We show under what conditions the protfolio approach can have a dramatic computational advantage over the best traditional methods.
Learning Bayesian Nets that Perform Well
Venue: arXiv cs.AI 2013
Year: 2013

A Bayesian net (BN) is more than a succinct way to encode a probabilistic distribution; it also corresponds to a function used to answer queries. A BN can therefore be evaluated by the accuracy of the answers it returns. Many algorithms for learning BNs, however, attempt to optimize another criterion (usually likelihood, possibly augmented with a regularizing term), which is independent of the distribution of queries that are posed. This paper takes the "performance criteria" seriously, and considers the challenge of computing the BN whose performance - read "accuracy over the distribution of queries" - is optimal. We show that many aspects of this learning task are more difficult than the corresponding subtasks in the standard model.
Probability Update: Conditioning vs. Cross-Entropy
Venue: arXiv cs.AI 2013
Year: 2013

Conditioning is the generally agreed-upon method for updating probability distributions when one learns that an event is certainly true. But it has been argued that we need other rules, in particular the rule of cross-entropy minimization, to handle updates that involve uncertain information. In this paper we re-examine such a case: van Fraassen's Judy Benjamin problem, which in essence asks how one might update given the value of a conditional probability. We argue that -- contrary to the suggestions in the literature -- it is possible to use simple conditionalization in this case, and thereby obtain answers that agree fully with intuition. This contrasts with proposals such as cross-entropy, which are easier to apply but can give unsatisfactory answers. Based on the lessons from this example, we speculate on some general philosophical issues concerning probability update.
Problem-Focused Incremental Elicitation of Multi-Attribute Utility Models
Venue: arXiv cs.AI 2013
Year: 2013

Decision theory has become widely accepted in the AI community as a useful framework for planning and decision making. Applying the framework typically requires elicitation of some form of probability and utility information. While much work in AI has focused on providing representations and tools for elicitation of probabilities, relatively little work has addressed the elicitation of utility models. This imbalance is not particularly justified considering that probability models are relatively stable across problem instances, while utility models may be different for each instance. Spending large amounts of time on elicitation can be undesirable for interactive systems used in low-stakes decision making and in time-critical decision making. In this paper we investigate the issues of reasoning with incomplete utility models. We identify patterns of problem instances where plans can be proved to be suboptimal if the (unknown) utility function satisfies certain conditions. We present an approach to planning and decision making that performs the utility elicitation incrementally and in a way that is informed by the domain model.
Models and Selection Criteria for Regression and Classification
Venue: arXiv cs.LG 2013
Year: 2013

When performing regression or classification, we are interested in the conditional probability distribution for an outcome or class variable Y given a set of explanatoryor input variables X. We consider Bayesian models for this task. In particular, we examine a special class of models, which we call Bayesian regression/classification (BRC) models, that can be factored into independent conditional (y|x) and input (x) models. These models are convenient, because the conditional model (the portion of the full model that we care about) can be analyzed by itself. We examine the practice of transforming arbitrary Bayesian models to BRC models, and argue that this practice is often inappropriate because it ignores prior knowledge that may be important for learning. In addition, we examine Bayesian methods for learning models from data. We discuss two criteria for Bayesian model selection that are appropriate for repression/classification: one described by Spiegelhalter et al. (1993), and another by Buntine (1993). We contrast these two criteria using the prequential framework of Dawid (1984), and give sufficient conditions under which the criteria agree.