OpenRaiser/Intern-Atlas huggingface dataset:
Irregular-Time Bayesian Networks
Venue: arXiv cs.AI 2012
Year: 2012

In many fields observations are performed irregularly along time, due to either measurement limitations or lack of a constant immanent rate. While discrete-time Markov models (as Dynamic Bayesian Networks) introduce either inefficient computation or an information loss to reasoning about such processes, continuous-time Markov models assume either a discrete state space (as Continuous-Time Bayesian Networks), or a flat continuous state space (as stochastic differential equations). To address these problems, we present a new modeling class called Irregular-Time Bayesian Networks (ITBNs), generalizing Dynamic Bayesian Networks, allowing substantially more compact representations, and increasing the expressivity of the temporal dynamics. In addition, a globally optimal solution is guaranteed when learning temporal systems, provided that they are fully observed at the same irregularly spaced time-points, and a semiparametric subclass of ITBNs is introduced to allow further adaptation to the irregular nature of the available data.
Dynamic programming in in uence diagrams with decision circuits
Venue: arXiv cs.AI 2012
Year: 2012

Decision circuits perform efficient evaluation of influence diagrams, building on the ad- vances in arithmetic circuits for belief net- work inference [Darwiche, 2003; Bhattachar- jya and Shachter, 2007]. We show how even more compact decision circuits can be con- structed for dynamic programming in influ- ence diagrams with separable value functions and conditionally independent subproblems. Once a decision circuit has been constructed based on the diagram's "global" graphical structure, it can be compiled to exploit "lo- cal" structure for efficient evaluation and sen- sitivity analysis.
Variance-Based Rewards for Approximate Bayesian Reinforcement Learning
Venue: arXiv cs.LG 2012
Year: 2012

The explore{exploit dilemma is one of the central challenges in Reinforcement Learning (RL). Bayesian RL solves the dilemma by providing the agent with information in the form of a prior distribution over environments; however, full Bayesian planning is intractable. Planning with the mean MDP is a common myopic approximation of Bayesian planning. We derive a novel reward bonus that is a function of the posterior distribution over environments, which, when added to the reward in planning with the mean MDP, results in an agent which explores efficiently and effectively. Although our method is similar to existing methods when given an uninformative or unstructured prior, unlike existing methods, our method can exploit structured priors. We prove that our method results in a polynomial sample complexity and empirically demonstrate its advantages in a structured exploration task.
Primal View on Belief Propagation
Venue: arXiv cs.LG 2012
Year: 2012

It is known that fixed points of loopy belief propagation (BP) correspond to stationary points of the Bethe variational problem, where we minimize the Bethe free energy subject to normalization and marginalization constraints. Unfortunately, this does not entirely explain BP because BP is a dual rather than primal algorithm to solve the Bethe variational problem -- beliefs are infeasible before convergence. Thus, we have no better understanding of BP than as an algorithm to seek for a common zero of a system of non-linear functions, not explicitly related to each other. In this theoretical paper, we show that these functions are in fact explicitly related -- they are the partial derivatives of a single function of reparameterizations. That means, BP seeks for a stationary point of a single function, without any constraints. This function has a very natural form: it is a linear combination of local log-partition functions, exactly as the Bethe entropy is the same linear combination of local entropies.
Rollout Sampling Policy Iteration for Decentralized POMDPs
Venue: arXiv cs.AI 2012
Year: 2012

We present decentralized rollout sampling policy iteration (DecRSPI) - a new algorithm for multi-agent decision problems formalized as DEC-POMDPs. DecRSPI is designed to improve scalability and tackle problems that lack an explicit model. The algorithm uses Monte- Carlo methods to generate a sample of reachable belief states. Then it computes a joint policy for each belief state based on the rollout estimations. A new policy representation allows us to represent solutions compactly. The key benefits of the algorithm are its linear time complexity over the number of agents, its bounded memory usage and good solution quality. It can solve larger problems that are intractable for existing planning algorithms. Experimental results confirm the effectiveness and scalability of the approach.
Modeling Multiple Annotator Expertise in the Semi-Supervised Learning Scenario
Venue: arXiv cs.LG 2012
Year: 2012

Learning algorithms normally assume that there is at most one annotation or label per data point. However, in some scenarios, such as medical diagnosis and on-line collaboration,multiple annotations may be available. In either case, obtaining labels for data points can be expensive and time-consuming (in some circumstances ground-truth may not exist). Semi-supervised learning approaches have shown that utilizing the unlabeled data is often beneficial in these cases. This paper presents a probabilistic semi-supervised model and algorithm that allows for learning from both unlabeled and labeled data in the presence of multiple annotators. We assume that it is known what annotator labeled which data points. The proposed approach produces annotator models that allow us to provide (1) estimates of the true label and (2) annotator variable expertise for both labeled and unlabeled data. We provide numerical comparisons under various scenarios and with respect to standard semi-supervised learning. Experiments showed that the presented approach provides clear advantages over multi-annotator methods that do not use the unlabeled data and over methods that do not use multi-labeler information.
Automatic Tuning of Interactive Perception Applications
Venue: arXiv cs.LG 2012
Year: 2012

Interactive applications incorporating high-data rate sensing and computer vision are becoming possible due to novel runtime systems and the use of parallel computation resources. To allow interactive use, such applications require careful tuning of multiple application parameters to meet required fidelity and latency bounds. This is a nontrivial task, often requiring expert knowledge, which becomes intractable as resources and application load characteristics change. This paper describes a method for automatic performance tuning that learns application characteristics and effects of tunable parameters online, and constructs models that are used to maximize fidelity for a given latency constraint. The paper shows that accurate latency models can be learned online, knowledge of application structure can be used to reduce the complexity of the learning task, and operating points can be found that achieve 90% of the optimal fidelity by exploring the parameter space only 3% of the time.
RAPID: A Reachable Anytime Planner for Imprecisely-sensed Domains
Venue: arXiv cs.AI 2012
Year: 2012

Despite the intractability of generic optimal partially observable Markov decision process planning, there exist important problems that have highly structured models. Previous researchers have used this insight to construct more efficient algorithms for factored domains, and for domains with topological structure in the flat state dynamics model. In our work, motivated by findings from the education community relevant to automated tutoring, we consider problems that exhibit a form of topological structure in the factored dynamics model. Our Reachable Anytime Planner for Imprecisely-sensed Domains (RAPID) leverages this structure to efficiently compute a good initial envelope of reachable states under the optimal MDP policy in time linear in the number of state variables. RAPID performs partially-observable planning over the limited envelope of states, and slowly expands the state space considered as time allows. RAPID performs well on a large tutoring-inspired problem simulation with 122 state variables, corresponding to a flat state space of over 10^30 states.
Experimenting with the Novel Approaches in Text Steganography
Venue: arXiv cs.CR 2012
Year: 2012

As is commonly known, the steganographic algorithms employ images, audio, video or text files as the medium to ensure hidden exchange of information between multiple contenders to protect the data from the prying eyes. However, using text as the target medium is relatively difficult as compared to the other target media, because of the lack of available redundant information in a text file. In this paper, in the backdrop of the limitations in the prevalent text based steganographic approaches, we propose simple, yet novel approaches that overcome the same. Our approaches are based on combining the random character sequence and feature coding methods to hide a character. We also analytically evaluate the approaches based on metrics viz. hiding strength, time overhead and memory overhead entailed. As compared to other methods, we believe the approaches proposed impart increased randomness and thus aid higher security at lower overhead.
Multilateration: Methods For Clustering Intersection Points For Wireless Sensor Networks Localization With Distance Estimation Error
Venue: arXiv cs.NI 2012
Year: 2012

In this paper we describe three methods for localizing a wireless sensor network node, using anchor nodes in its neighbourhood, when there is an error in distance estimation present. We use the intersection points of the circles formed with the estimated distances from each anchors and we apply different methods to form clusters. We then use the cluster points to calculate the final position.
Tree-width for first order formulae
Venue: arXiv cs.LO 2012
Year: 2012

We introduce tree-width for first order formulae ϕ, fotw(ϕ). We show that computing fotw is fixed-parameter tractable with parameter fotw. Moreover, we show that on classes of formulae of bounded fotw, model checking is fixed parameter tractable, with parameter the length of the formula. This is done by translating a formula ϕ with fotw(ϕ)<k into a formula of the k-variable fragment L^k of first order logic. For fixed k, the question whether a given first order formula is equivalent to an L^k formula is undecidable. In contrast, the classes of first order formulae with bounded fotw are fragments of first order logic for which the equivalence is decidable. Our notion of tree-width generalises tree-width of conjunctive queries to arbitrary formulae of first order logic by taking into account the quantifier interaction in a formula. Moreover, it is more powerful than the notion of elimination-width of quantified constraint formulae, defined by Chen and Dalmau (CSL 2005): for quantified constraint formulae, both bounded elimination-width and bounded fotw allow for model checking in polynomial time. We prove that fotw of a quantified constraint formula ϕ is bounded by the elimination-width of ϕ, and we exhibit a class of quantified constraint formulae with bounded fotw, that has unbounded elimination-width. A similar comparison holds for strict tree-width of non-recursive stratified datalog as defined by Flum, Frick, and Grohe (JACM 49, 2002). Finally, we show that fotw has a characterization in terms of a cops and robbers game without monotonicity cost.
Stochastic Characteristics and Simulation of the Random Waypoint Mobility Model
Venue: arXiv cs.NI 2012
Year: 2012

Simulation results for Mobile Ad-Hoc Networks (MANETs) are fundamentally governed by the underlying Mobility Model. Thus it is imperative to find whether events functionally dependent on the mobility model 'converge' to well defined functions or constants. This shall ensure the long-run consistency among simulation performed by disparate parties. This paper reviews a work on the discrete Random Waypoint Mobility Model (RWMM), addressing its long run stochastic stability. It is proved that each model in the targeted discrete class of the RWMM satisfies Birkhoff's pointwise ergodic theorem [13], and hence time averaged functions on the mobility model surely converge. We also simulate the most common and general version of the RWMM to give insight into its working.
Path Planning Algorithm for Extinguishing Forest Fires
Venue: arXiv cs.RO 2012
Year: 2012

One of the major impacts of climatic changes is due to destroying of forest. Destroying of forest takes place in many ways but the majority of the forest is destroyed due to wild forest fires. In this paper we have presented a path planning algorithm for extinguishing fires which uses Wireless Sensor and Actor Networks (WSANs) for detecting fires. Since most of the works on forest fires are based on Wireless Sensor Networks (WSNs) and a collection of work has been done on coverage, message transmission, deployment of nodes, battery power depletion of sensor nodes in WSNs we focused our work in path planning approach of the Actor to move to the target area where the fire has occurred and extinguish it. An incremental approach is presented in order to determine the successive moves of the Actor to extinguish fire in an environment with and without obstacles. This is done by comparing the moves determined with target location readings obtained using sensors until the Actor reaches the target area to extinguish fires.
SignsWorld; Deeping Into the Silence World and Hearing Its Signs (State of the Art)
Venue: arXiv cs.CL 2012
Year: 2012

Automatic speech processing systems are employed more and more often in real environments. Although the underlying speech technology is mostly language independent, differences between languages with respect to their structure and grammar have substantial effect on the recognition systems performance. In this paper, we present a review of the latest developments in the sign language recognition research in general and in the Arabic sign language (ArSL) in specific. This paper also presents a general framework for improving the deaf community communication with the hearing people that is called SignsWorld. The overall goal of the SignsWorld project is to develop a vision-based technology for recognizing and translating continuous Arabic sign language ArSL.
Clustering Using Isoperimetric Number of Trees
Venue: arXiv cs.CV 2012
Year: 2012

In this paper we propose a graph-based data clustering algorithm which is based on exact clustering of a minimum spanning tree in terms of a minimum isoperimetry criteria. We show that our basic clustering algorithm runs in $O(n \log n)$ and with post-processing in $O(n^2)$ (worst case) time where $n$ is the size of the data set. We also show that our generalized graph model which also allows the use of potentials at vertices can be used to extract a more detailed pack of information as the {\it outlier profile} of the data set. In this direction we show that our approach can be used to define the concept of an outlier-set in a precise way and we propose approximation algorithms for finding such sets. We also provide a comparative performance analysis of our algorithm with other related ones and we show that the new clustering algorithm (without the outlier extraction procedure) behaves quite effectively even on hard benchmarks and handmade examples.
Analysis of Quality of Service Performances of Connection Admission Control Mechanisms in OFDMA IEEE 802.16 Network using BMAP Queuing
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we consider a single-cell IEEE 802.16 environment in which the base station allocates subchannels to the subscriber stations in its coverage area. The subchannels allocated to a subscriber station are shared by multiple connections at that subscriber station. To ensure the Quality of Service (QoS) performances, two Connection Admission Control (CAC) mechanisms, namely, threshold-based and queue-aware CAC mechanisms are considered at a subscriber station. A queuing analytical framework for these admission control mechanisms is presented considering Orthogonal Frequency Division Multiple Access (OFDMA) based transmission at the physical layer. Then, based on the queuing model, both the connection-level and the packet-level performances are studied and compared with their analogues in the case without CAC. The connection arrival is modeled by a Poisson process and the packet arrival for a connection by Batch Markov Arrival Process (BMAP). We determine analytically and numerically different QoS performance measures (connection blocking probability, average number of ongoing connections, average queue length, packet dropping probability, queue throughput and average packet delay).
Budget Feasible Mechanism Design: From Prior-Free to Bayesian
Venue: arXiv cs.GT 2012
Year: 2012

Budget feasible mechanism design studies procurement combinatorial auctions where the sellers have private costs to produce items, and the buyer(auctioneer) aims to maximize a social valuation function on subsets of items, under the budget constraint on the total payment. One of the most important questions in the field is "which valuation domains admit truthful budget feasible mechanisms with `small' approximations (compared to the social optimum)?" Singer showed that additive and submodular functions have such constant approximations. Recently, Dobzinski, Papadimitriou, and Singer gave an O(log^2 n)-approximation mechanism for subadditive functions; they also remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive functions." We address this question from two viewpoints: prior-free worst case analysis and Bayesian analysis. For the prior-free framework, we use an LP that describes the fractional cover of the valuation function; it is also connected to the concept of approximate core in cooperative game theory. We provide an O(I)-approximation mechanism for subadditive functions, via the worst case integrality gap I of LP. This implies an O(log n)-approximation for subadditive valuations, O(1)-approximation for XOS valuations, and for valuations with a constant I. XOS valuations are an important class of functions that lie between submodular and subadditive classes. We give another polynomial time O(log n/loglog n) sub-logarithmic approximation mechanism for subadditive valuations. For the Bayesian framework, we provide a constant approximation mechanism for all subadditive functions, using the above prior-free mechanism for XOS valuations as a subroutine. Our mechanism allows correlations in the distribution of private information and is universally truthful.
Secured Position Location and Tracking (SPL&T) for Detection of Multiple Malicious Nodes Maintaining Two Friendly References in Mobile Ad hoc Networks
Venue: arXiv cs.NI 2012
Year: 2012

Secured Position Location and Tracking (PL&T) scheme is developed for multiple malicious radios or nodes detection using integrated key based strict friendly scheme and position location and tracking by multi-sectored based multiple target's PL&T. The friendly and malicious nodes detection is based on the integrated key consisting of symmetric keys, geographic location and round trip response time. Two strictly friend references dynamically form the tracking zone over the detected multiple malicious nodes using the multi-sectored adaptive beam forming. This PL&T technique is robust, precise, scalable, and faster than using the single reference, two reference and three reference nodes based PL&T method in the battlefield oriented Mobile Ad hoc Networks. The simulation results show that the lower relative speed bound of any participating node increased the switching overhead, the decreasing received energy with increasing number of the multi-sectored beams reduced tracking accuracy and the strict friendly authentication overhead depends upon the time period between two latest periodic authentication failures.
Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms
Venue: arXiv cs.IT 2012
Year: 2012

This paper treats the problem of minimizing a general continuously differentiable function subject to sparsity constraints. We present and analyze several different optimality criteria which are based on the notions of stationarity and coordinate-wise optimality. These conditions are then used to derive three numerical algorithms aimed at finding points satisfying the resulting optimality criteria: the iterative hard thresholding method and the greedy and partial sparse-simplex methods. The first algorithm is essentially a gradient projection method while the remaining two algorithms are of coordinate descent type. The theoretical convergence of these methods and their relations to the derived optimality conditions are studied. The algorithms and results are illustrated by several numerical examples.
Why Watching Movie Tweets Won't Tell the Whole Story?
Venue: arXiv cs.SI 2012
Year: 2012

Data from Online Social Networks (OSNs) are providing analysts with an unprecedented access to public opinion on elections, news, movies etc. However, caution must be taken to determine whether and how much of the opinion extracted from OSN user data is indeed reflective of the opinion of the larger online population. In this work we study this issue in the context of movie reviews on Twitter and compare the opinion of Twitter users with that of the online population of IMDb and Rotten Tomatoes. We introduce new metrics to show that the Twitter users can be characteristically different from general users, both in their rating and their relative preference for Oscar-nominated and non-nominated movies. Additionally, we investigate whether such data can truly predict a movie's box-office success.
Citation Analysis with Medical Subject Headings (MeSH) using the Web of Knowledge: A new routine
Venue: arXiv cs.DL 2012
Year: 2012

Citation analysis of documents retrieved from the Medline database (at the Web of Knowledge) has been possible only on a case-by-case basis. A technique is here developed for citation analysis in batch mode using both Medical Subject Headings (MeSH) at the Web of Knowledge and the Science Citation Index at the Web of Science. This freeware routine is applied to the case of "Brugada Syndrome," a specific disease and field of research (since 1992). The journals containing these publications, for example, are attributed to Web-of-Science Categories other than "Cardiac and Cardiovascular Systems"), perhaps because of the possibility of genetic testing for this syndrome in the clinic. With this routine, all the instruments available for citation analysis can now be used on the basis of MeSH terms. Other options for crossing between Medline, WoS, and Scopus are also reviewed.
On the Design of a Novel Joint Network-Channel Coding Scheme for the Multiple Access Relay Channel
Venue: arXiv cs.IT 2012
Year: 2012

This paper proposes a novel joint non-binary network-channel code for the Time-Division Decode-and-Forward Multiple Access Relay Channel (TD-DF-MARC), where the relay linearly combines -- over a non-binary finite field -- the coded sequences from the source nodes. A method based on an EXIT chart analysis is derived for selecting the best coefficients of the linear combination. Moreover, it is shown that for different setups of the system, different coefficients should be chosen in order to improve the performance. This conclusion contrasts with previous works where a random selection was considered. Monte Carlo simulations show that the proposed scheme outperforms, in terms of its gap to the outage probabilities, the previously published joint network-channel coding approaches. Besides, this gain is achieved by using very short-length codewords, which makes the scheme particularly attractive for low-latency applications.