OpenRaiser/Intern-Atlas huggingface dataset:
Likelihood Computations Using Value Abstractions
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we use evidence-specific value abstraction for speeding Bayesian networks inference. This is done by grouping variable values and treating the combined values as a single entity. As we show, such abstractions can exploit regularities in conditional probability distributions and also the specific values of observed variables. To formally justify value abstraction, we define the notion of safe value abstraction and devise inference algorithms that use it to reduce the cost of inference. Our procedure is particularly useful for learning complex networks with many hidden variables. In such cases, repeated likelihood computations are required for EM or other parameter optimization techniques. Since these computations are repeated with respect to the same evidence set, our methods can provide significant speedup to the learning procedure. We demonstrate the algorithm on genetic linkage problems where the use of value abstraction sometimes differentiates between a feasible and non-feasible solution.
Dependency Networks for Collaborative Filtering and Data Visualization
Venue: arXiv cs.AI 2013
Year: 2013

We describe a graphical model for probabilistic relationships---an alternative to the Bayesian network---called a dependency network. The graph of a dependency network, unlike a Bayesian network, is potentially cyclic. The probability component of a dependency network, like a Bayesian network, is a set of conditional distributions, one for each node given its parents. We identify several basic properties of this representation and describe a computationally efficient procedure for learning the graph and probability components from data. We describe the application of this representation to probabilistic inference, collaborative filtering (the task of predicting preferences), and the visualization of acausal predictive relationships.
Marginalization in Composed Probabilistic Models
Venue: arXiv cs.AI 2013
Year: 2013

Composition of low-dimensional distributions, whose foundations were laid in the papaer published in the Proceeding of UAI'97 (Jirousek 1997), appeared to be an alternative apparatus to describe multidimensional probabilistic models. In contrast to Graphical Markov Models, which define multidomensinoal distributions in a declarative way, this approach is rather procedural. Ordering of low-dimensional distributions into a proper sequence fully defines the resepctive computational procedure; therefore, a stury of different type of generating sequences is one fo the central problems in this field. Thus, it appears that an important role is played by special sequences that are called perfect. Their main characterization theorems are presetned in this paper. However, the main result of this paper is a solution to the problem of margnialization for general sequences. The main theorem describes a way to obtain a generating sequence that defines the model corresponding to the marginal of the distribution defined by an arbitrary genearting sequence. From this theorem the reader can see to what extent these comutations are local; i.e., the sequence consists of marginal distributions whose computation must be made by summing up over the values of the variable eliminated (the paper deals with finite model).
Credal Networks under Maximum Entropy
Venue: arXiv cs.AI 2013
Year: 2013

We apply the principle of maximum entropy to select a unique joint probability distribution from the set of all joint probability distributions specified by a credal network. In detail, we start by showing that the unique joint distribution of a Bayesian tree coincides with the maximum entropy model of its conditional distributions. This result, however, does not hold anymore for general Bayesian networks. We thus present a new kind of maximum entropy models, which are computed sequentially. We then show that for all general Bayesian networks, the sequential maximum entropy model coincides with the unique joint distribution. Moreover, we apply the new principle of sequential maximum entropy to interval Bayesian networks and more generally to credal networks. We especially show that this application is equivalent to a number of small local entropy maximizations.
Risk Agoras: Dialectical Argumentation for Scientific Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

We propose a formal framework for intelligent systems which can reason about scientific domains, in particular about the carcinogenicity of chemicals, and we study its properties. Our framework is grounded in a philosophy of scientific enquiry and discourse, and uses a model of dialectical argumentation. The formalism enables representation of scientific uncertainty and conflict in a manner suitable for qualitative reasoning about the domain.
PEGASUS: A Policy Search Method for Large MDPs and POMDPs
Venue: arXiv cs.AI 2013
Year: 2013

We propose a new approach to the problem of searching a space of policies for a Markov decision process (MDP) or a partially observable Markov decision process (POMDP), given a model. Our approach is based on the following observation: Any (PO)MDP can be transformed into an "equivalent" POMDP in which all state transitions (given the current state and action) are deterministic. This reduces the general problem of policy search to one in which we need only consider POMDPs with deterministic transitions. We give a natural way of estimating the value of all policies in these transformed POMDPs. Policy search is then simply performed by searching for a policy with high estimated value. We also establish conditions under which our value estimates will be good, recovering theoretical results similar to those of Kearns, Mansour and Ng (1999), but with "sample complexity" bounds that have only a polynomial rather than exponential dependence on the horizon time. Our method applies to arbitrary POMDPs, including ones with infinite state and action spaces. We also present empirical results for our approach on a small discrete problem, and on a complex continuous state/continuous action problem involving learning to ride a bicycle.
Probabilistic State-Dependent Grammars for Plan Recognition
Venue: arXiv cs.AI 2013
Year: 2013

Techniques for plan recognition under uncertainty require a stochastic model of the plan-generation process. We introduce Probabilistic State-Dependent Grammars (PSDGs) to represent an agent's plan-generation process. The PSDG language model extends probabilistic context-free grammars (PCFGs) by allowing production probabilities to depend on an explicit model of the planning agent's internal and external state. Given a PSDG description of the plan-generation process, we can then use inference algorithms that exploit the particular independence properties of the PSDG language to efficiently answer plan-recognition queries. The combination of the PSDG language model and inference algorithms extends the range of plan-recognition domains for which practical probabilistic inference is possible, as illustrated by applications in traffic monitoring and air combat.
(Extended Version) Algebraic Characterization of the Class of Languages recognized by Measure Only Quantum Automata
Venue: arXiv cs.FL 2013
Year: 2013

We study a model of one-way quantum automaton where only measurement operations are allowed ($\mon$). We give an algebraic characterization of $\lmo(Σ)$, showing that the syntactic monoids of the languages in $\lmo(Σ)$ are exactly the $J$-trivial literally idempotent syntactic monoids, where $J$ is the Green's relation determined by two-sided ideals. We also prove that $\lmo(Σ)$ coincides with the literal variety of literally idempotent piecewise testable regular languages. This allows us to prove the existence of a polynomial time algorithm for deciding whether a regular language belongs to $\lmo(Σ)$ and to discuss definability issues in terms of the existential first-order logic $Σ_1[<]$ and the linear temporal logic without the next operator LTLWN.
Multiscale Discriminant Saliency for Visual Attention
Venue: arXiv cs.CV 2013
Year: 2013

The bottom-up saliency, an early stage of humans' visual attention, can be considered as a binary classification problem between center and surround classes. Discriminant power of features for the classification is measured as mutual information between features and two classes distribution. The estimated discrepancy of two feature classes very much depends on considered scale levels; then, multi-scale structure and discriminant power are integrated by employing discrete wavelet features and Hidden markov tree (HMT). With wavelet coefficients and Hidden Markov Tree parameters, quad-tree like label structures are constructed and utilized in maximum a posterior probability (MAP) of hidden class variables at corresponding dyadic sub-squares. Then, saliency value for each dyadic square at each scale level is computed with discriminant power principle and the MAP. Finally, across multiple scales is integrated the final saliency map by an information maximization rule. Both standard quantitative tools such as NSS, LCC, AUC and qualitative assessments are used for evaluating the proposed multiscale discriminant saliency method (MDIS) against the well-know information-based saliency method AIM on its Bruce Database wity eye-tracking data. Simulation results are presented and analyzed to verify the validity of MDIS as well as point out its disadvantages for further research direction.
Generic Regular Decompositions for Parametric Polynomial Systems
Venue: arXiv cs.SC 2013
Year: 2013

This paper presents a generalization of our earlier work in [19]. In this paper, the two concepts, generic regular decomposition (GRD) and regular-decomposition-unstable (RDU) variety introduced in [19] for generic zero-dimensional systems, are extended to the case where the parametric systems are not necessarily zero-dimensional. An algorithm is provided to compute GRDs and the associated RDU varieties of parametric systems simultaneously on the basis of the algorithm for generic zero-dimensional systems proposed in [19]. Then the solutions of any parametric system can be represented by the solutions of finitely many regular systems and the decomposition is stable at any parameter value in the complement of the associated RDU variety of the parameter space. The related definitions and the results presented in [19] are also generalized and a further discussion on RDU varieties is given from an experimental point of view. The new algorithm has been implemented on the basis of DISCOVERER with Maple 16 and experimented with a number of benchmarks from the literature.
Performance Comparison of Proposed Lifetime Maximizing Trees for Data Aggregation in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this paper a packet level simulator is used to explore the performance of the proposed DLMT and CLMT algorithms under various traffic conditions. Performance of the proposed algorithms is compared with already existing E-Span tree structure. These proposed algorithms tend to extend the node lifetime in order to increase the amount of information gathered by the tree root. Decentralized lifetime maximizing tree (DLMT) features in nodes with higher energy to be chosen as data aggregating parents while Centralized Lifetime Maximizing Tree (CLMT) features with the identification of the bottleneck node to collect data in a central manner among given set of nodes. By choosing Forwarded Diffusion as our underlying routing platform the simulations are carried on J-Sim. Our simulation results have shown that the functional lifetime of event sources can be enhanced by a maximum of 147% when data is aggregated via DLMT and by 139% when data is aggregated via CLMT. Our proposed DLMT algorithm has shown maximum of 13% additional lifetime saving without increasing the delay. Packet delivery ratio has also shown a remarkable increase when the tree depth is considered in these proposed tree structures. Furthermore, the delay is also reduced by using DLMT & CLMT in comparison with E-Span.
Punctured Trellis-Coded Modulation
Venue: arXiv cs.IT 2013
Year: 2013

In classic trellis-coded modulation (TCM) signal constellations of twice the cardinality are applied when compared to an uncoded transmission enabling transmission of one bit of redundancy per PAM-symbol, i.e., rates of $\frac{K}{K+1}$ when $2^{K+1}$ denotes the cardinality of the signal constellation. In order to support different rates, multi-dimensional (i.e., $\mathcal{D}$-dimensional) constellations had been proposed by means of combining subsequent one- or two-dimensional modulation steps, resulting in TCM-schemes with $\frac{1}{\mathcal{D}}$ bit redundancy per real dimension. In contrast, in this paper we propose to perform rate adjustment for TCM by means of puncturing the convolutional code (CC) on which a TCM-scheme is based on. It is shown, that due to the nontrivial mapping of the output symbols of the CC to signal points in the case of puncturing, a modification of the corresponding Viterbi-decoder algorithm and an optimization of the CC and the puncturing scheme are necessary.
Design Pattern-Based Extension of Class Hierarchies to Support Runtime Invariant Checks
Venue: arXiv cs.PL 2013
Year: 2013

We present a technique for automatically weaving structural invariant checks into an existing collection of classes. Using variations on existing design patterns, we use a concise specification to generate from this collection a new set of classes that implement the interfaces of the originals, but with the addition of user-specified class invariant checks. Our work is notable in the scarcity of assumptions made. Unlike previous design pattern approaches to this problem, our technique requires no modification of the original source code, relies only on single inheritance, and does not require that the attributes used in the checks be publicly visible. We are able to instrument a wide variety of class hierarchies, including those with pure interfaces, abstract classes and classes with type parameters. We have implemented the construction as an Eclipse plug-in for Java development.
Creative telescoping for rational functions using the Griffiths-Dwork method
Venue: arXiv cs.SC 2013
Year: 2013

Creative telescoping algorithms compute linear differential equations satisfied by multiple integrals with parameters. We describe a precise and elementary algorithmic version of the Griffiths-Dwork method for the creative telescoping of rational functions. This leads to bounds on the order and degree of the coefficients of the differential equation, and to the first complexity result which is simply exponential in the number of variables. One of the important features of the algorithm is that it does not need to compute certificates. The approach is vindicated by a prototype implementation.
A Scalable Hybrid MAC Protocol for Massive M2M Networks
Venue: arXiv cs.NI 2013
Year: 2013

In Machine to Machine (M2M) networks, a robust Medium Access Control (MAC) protocol is crucial to enable numerous machine-type devices to concurrently access the channel. Most literatures focus on developing simplex (reservation or contention based)MAC protocols which cannot provide a scalable solution for M2M networks with large number of devices. In this paper, a frame-based Hybrid MAC scheme, which consists of a contention period and a transmission period, is proposed for M2M networks. In the proposed scheme, the devices firstly contend the transmission opportunities during the contention period, only the successful devices will be assigned a time slot for transmission during the transmission period. To balance the tradeoff between the contention and transmission period in each frame, an optimization problem is formulated to maximize the system throughput by finding the optimal contending probability during contention period and optimal number of devices that can transmit during transmission period. A practical hybrid MAC protocol is designed to implement the proposed scheme. The analytical and simulation results demonstrate the effectiveness of the proposed Hybrid MAC protocol.
Applying machine learning techniques to improve user acceptance on ubiquitous environement
Venue: arXiv cs.IR 2013
Year: 2013

Ubiquitous information access becomes more and more important nowadays and research is aimed at making it adapted to users. Our work consists in applying machine learning techniques in order to adapt the information access provided by ubiquitous systems to users when the system only knows the user social group, without knowing anything about the user interest. The adaptation procedures associate actions to perceived situations of the user. Associations are based on feedback given by the user as a reaction to the behavior of the system. Our method brings a solution to some of the problems concerning the acceptance of the system by users when applying machine learning techniques to systems at the beginning of the interaction between the system and the user.
Local-Search based Approximation Algorithms for Mobile Facility Location Problems
Venue: arXiv cs.DS 2013
Year: 2013

We consider the {\em mobile facility location} (\mfl) problem. We are given a set of facilities and clients located in a common metric space. The goal is to move each facility from its initial location to a destination and assign each client to the destination of some facility so as to minimize the sum of the movement-costs of the facilities and the client-assignment costs. This abstracts facility-location settings where one has the flexibility of moving facilities from their current locations to other destinations so as to serve clients more efficiently by reducing their assignment costs. We give the first {\em local-search based} approximation algorithm for this problem and achieve the best-known approximation guarantee. Our main result is $(3+ε)$-approximation for this problem for any constant $ε>0$ using local search. The previous best guarantee was an 8-approximation algorithm based on LP-rounding. Our guarantee {\em matches} the best-known approximation guarantee for the $k$-median problem. Since there is an approximation-preserving reduction from the $k$-median problem to \mfl, any improvement of our result would imply an analogous improvement for the $k$-median problem. Furthermore, {\em our analysis is tight} (up to $o(1)$ factors) since the tight example for the local-search based 3-approximation algorithm for $k$-median can be easily adapted to show that our local-search algorithm has a tight approximation ratio of 3. One of the chief novelties of the analysis is that in order to generate a suitable collection of local-search moves whose resulting inequalities yield the desired bound on the cost of a local-optimum, we define a tree-like structure that (loosely speaking) functions as a "recursion tree", using which we spawn off local-search moves by exploring this tree to a constant depth.
Decentralized Lifetime Minimizing Tree for Data Aggregation in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

To meet the demands of wireless sensor networks (WSNs) where data are usually aggregated at a single source prior to transmitting to any distant user, there is a need to establish a tree structure inside any given event region. In this paper, we propose a novel technique to create one such tree, which preserves the energy and minimizes the lifetime of event sources while they are constantly transmitting for data aggregation in future WSNs. We use the term Decentralized Lifetime-Minimizing Tree (DLMT) to denote this tree. DLMT features in nodes with higher energy tend to be chosen as data aggregating parents so that the time to detect the first broken tree link can be extended and less energy is involved in tree maintenance. In addition, by constructing the tree in such a way, the protocol is also able to reduce the frequency of tree reconstruction, minimizes the amount of data loss, minimizes the delay during data collection and preserves the energy. Forwarded directed Diffusion protocol is chosen as the routing platform.
Counting publications and citations: Is more always better?
Venue: arXiv cs.DL 2013
Year: 2013

Is more always better? We address this question in the context of bibliometric indices that aim to assess the scientific impact of individual researchers by counting their number of highly cited publications. We propose a simple model in which the number of citations of a publication depends not only on the scientific impact of the publication but also on other 'random' factors. Our model indicates that more need not always be better. It turns out that the most influential researchers may have a systematically lower performance, in terms of highly cited publications, than some of their less influential colleagues. The model also suggests an improved way of counting highly cited publications.
Two-Way Training for Discriminatory Channel Estimation in Wireless MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

This work examines the use of two-way training to efficiently discriminate the channel estimation performances at a legitimate receiver (LR) and an unauthorized receiver (UR) in a multiple-input multiple-output (MIMO) wireless system. This work improves upon the original discriminatory channel estimation (DCE) scheme proposed by Chang et al where multiple stages of feedback and retraining were used. While most studies on physical layer secrecy are under the information-theoretic framework and focus directly on the data transmission phase, studies on DCE focus on the training phase and aim to provide a practical signal processing technique to discriminate between the channel estimation performances at LR and UR. A key feature of DCE designs is the insertion of artificial noise (AN) in the training signal to degrade the channel estimation performance at UR. To do so, AN must be placed in a carefully chosen subspace based on the transmitter's knowledge of LR's channel in order to minimize its effect on LR. In this paper, we adopt the idea of two-way training that allows both the transmitter and LR to send training signals to facilitate channel estimation at both ends. Both reciprocal and non-reciprocal channels are considered and a two-way DCE scheme is proposed for each scenario. {For mathematical tractability, we assume that all terminals employ the linear minimum mean square error criterion for channel estimation. Based on the mean square error (MSE) of the channel estimates at all terminals,} we formulate and solve an optimization problem where the optimal power allocation between the training signal and AN is found by minimizing the MSE of LR's channel estimate subject to a constraint on the MSE achievable at UR. Numerical results show that the proposed DCE schemes can effectively discriminate between the channel estimation and hence the data detection performances at LR and UR.
Capacity Analysis of Bidirectional AF Relay Selection with Imperfect Channel State Information
Venue: arXiv cs.IT 2013
Year: 2013

In this letter, we analyze the ergodic capacity of bidirectional amplify-and-forward relay selection (RS) with imperfect channel state information (CSI), i.e., outdated CSI and imperfect channel estimation. Practically, the optimal RS scheme in maximizing the ergodic capacity cannot be achieved, due to the imperfect CSI. Therefore, two suboptimal RS schemes are discussed and analyzed, in which the first RS scheme is based on the imperfect channel coefficients, and the second RS scheme is based on the predicted channel coefficients. The lower bound of the ergodic capacity with imperfect CSI is derived in a closed-form, which matches tightly with the simulation results. The results reveal that once CSI is imperfect, the ergodic capacity of bidirectional RS degrades greatly, whereas the RS scheme based on the predicted channel has better performance, and it approaches infinitely to the optimal performance, when the prediction length is sufficiently large.