OpenRaiser/Intern-Atlas huggingface dataset:
Low Delay MAC Scheduling for Frequency-agile Multi-radio Wireless Networks
Venue: arXiv cs.NI 2013
Year: 2013

Recent trends suggest that cognitive radio based wireless networks will be frequency agile and the nodes will be equipped with multiple radios capable of tuning across large swaths of spectrum. The MAC scheduling problem in such networks refers to making intelligent decisions on which communication links to activate at which time instant and over which frequency band. The challenge in designing a low-complexity distributed MAC, that achieves low delay, is posed by two additional dimensions of cognitive radio networks: interference graphs and data rates that are frequency-band dependent, and explosion in number of feasible schedules due to large number of available frequency-bands. In this paper, we propose MAXIMALGAIN MAC, a distributed MAC scheduler for frequency agile multi-band networks that simultaneously achieves the following: (i) optimal network-delay scaling with respect to the number of communicating pairs, (ii) low computational complexity of O(log2(maximum degree of the interference graphs)) which is independent of the number of frequency bands, number of radios per node, and overall size of the network, and (iii) robustness, i.e., it can be adapted to a scenario where nodes are not synchronized and control packets could be lost. Our proposed MAC also achieves a throughput provably within a constant fraction (under isotropic propagation) of the maximum throughput. Due to a recent impossibility result, optimal delay-scaling could only be achieved with some amount of throughput loss [30]. Extensive simulations using OMNeT++ network simulator shows that, compared to a multi-band extension of a state-of-art CSMA algorithm (namely, Q-CSMA), our asynchronous algorithm achieves a 2.5x? reduction in delay while achieving at least 85% of the maximum achievable throughput. Our MAC algorithms are derived from a novel local search based technique.
Adaptive Minimum BER Reduced-Rank Interference Suppression Algorithms Based on Joint and Iterative Optimization of Parameters
Venue: arXiv cs.IT 2013
Year: 2013

In this letter, we propose a novel adaptive reduced-rank strategy based on joint iterative optimization (JIO) of filters according to the minimization of the bit error rate (BER) cost function. The proposed optimization technique adjusts the weights of a subspace projection matrix and a reduced-rank filter jointly. We develop stochastic gradient (SG) algorithms for their adaptive implementation and introduce a novel automatic rank selection method based on the BER criterion. Simulation results for direct-sequence code-division-multiple-access (DS-CDMA) systems show that the proposed adaptive algorithms significantly outperform the existing schemes.
Towards a theory of good SAT representations
Venue: arXiv cs.AI 2013
Year: 2013

We aim at providing a foundation of a theory of "good" SAT representations F of boolean functions f. We argue that the hierarchy UC_k of unit-refutation complete clause-sets of level k, introduced by the authors, provides the most basic target classes, that is, F in UC_k is to be achieved for k as small as feasible. If F does not contain new variables, i.e., F is equivalent (as a CNF) to f, then F in UC_1 is similar to "achieving (generalised) arc consistency" known from the literature (it is somewhat weaker, but theoretically much nicer to handle). We show that for polysize representations of boolean functions in this sense, the hierarchy UC_k is strict. The boolean functions for these separations are "doped" minimally unsatisfiable clause-sets of deficiency 1; these functions have been introduced in [Sloan, Soerenyi, Turan, 2007], and we generalise their construction and show a correspondence to a strengthened notion of irredundant sub-clause-sets. Turning from lower bounds to upper bounds, we believe that many common CNF representations fit into the UC_k scheme, and we give some basic tools to construct representations in UC_1 with new variables, based on the Tseitin translation. Note that regarding new variables the UC_1-representations are stronger than mere "arc consistency", since the new variables are not excluded from consideration.
Termhood-based Comparability Metrics of Comparable Corpus in Special Domain
Venue: arXiv cs.CL 2013
Year: 2013

Cross-Language Information Retrieval (CLIR) and machine translation (MT) resources, such as dictionaries and parallel corpora, are scarce and hard to come by for special domains. Besides, these resources are just limited to a few languages, such as English, French, and Spanish and so on. So, obtaining comparable corpora automatically for such domains could be an answer to this problem effectively. Comparable corpora, that the subcorpora are not translations of each other, can be easily obtained from web. Therefore, building and using comparable corpora is often a more feasible option in multilingual information processing. Comparability metrics is one of key issues in the field of building and using comparable corpus. Currently, there is no widely accepted definition or metrics method of corpus comparability. In fact, Different definitions or metrics methods of comparability might be given to suit various tasks about natural language processing. A new comparability, namely, termhood-based metrics, oriented to the task of bilingual terminology extraction, is proposed in this paper. In this method, words are ranked by termhood not frequency, and then the cosine similarities, calculated based on the ranking lists of word termhood, is used as comparability. Experiments results show that termhood-based metrics performs better than traditional frequency-based metrics.
Generating Non-Linear Interpolants by Semidefinite Programming
Venue: arXiv cs.LO 2013
Year: 2013

Interpolation-based techniques have been widely and successfully applied in the verification of hardware and software, e.g., in bounded-model check- ing, CEGAR, SMT, etc., whose hardest part is how to synthesize interpolants. Various work for discovering interpolants for propositional logic, quantifier-free fragments of first-order theories and their combinations have been proposed. However, little work focuses on discovering polynomial interpolants in the literature. In this paper, we provide an approach for constructing non-linear interpolants based on semidefinite programming, and show how to apply such results to the verification of programs by examples.
Channel-Aware Random Access in the Presence of Channel Estimation Errors
Venue: arXiv cs.IT 2013
Year: 2013

In this work, we consider the random access of nodes adapting their transmission probability based on the local channel state information (CSI) in a decentralized manner, which is called CARA. The CSI is not directly available to each node but estimated with some errors in our scenario. Thus, the impact of imperfect CSI on the performance of CARA is our main concern. Specifically, an exact stability analysis is carried out when a pair of bursty sources are competing for a common receiver and, thereby, have interdependent services. The analysis also takes into account the compound effects of the multipacket reception (MPR) capability at the receiver. The contributions in this paper are twofold: first, we obtain the exact stability region of CARA in the presence of channel estimation errors; such an assessment is necessary as the errors in channel estimation are inevitable in the practical situation. Secondly, we compare the performance of CARA to that achieved by the class of stationary scheduling policies that make decisions in a centralized manner based on the CSI feedback. It is shown that the stability region of CARA is not necessarily a subset of that of centralized schedulers as the MPR capability improves.
Predicting Intermediate Storage Performance for Workflow Applications
Venue: arXiv cs.DC 2013
Year: 2013

Configuring a storage system to better serve an application is a challenging task complicated by a multidimensional, discrete configuration space and the high cost of space exploration (e.g., by running the application with different storage configurations). To enable selecting the best configuration in a reasonable time, we design an end-to-end performance prediction mechanism that estimates the turn-around time of an application using storage system under a given configuration. This approach focuses on a generic object-based storage system design, supports exploring the impact of optimizations targeting workflow applications (e.g., various data placement schemes) in addition to other, more traditional, configuration knobs (e.g., stripe size or replication level), and models the system operation at data-chunk and control message level. This paper presents our experience to date with designing and using this prediction mechanism. We evaluate this mechanism using micro- as well as synthetic benchmarks mimicking real workflow applications, and a real application.. A preliminary evaluation shows that we are on a good track to meet our objectives: it can scale to model a workflow application run on an entire cluster while offering an over 200x speedup factor (normalized by resource) compared to running the actual application, and can achieve, in the limited number of scenarios we study, a prediction accuracy that enables identifying the best storage system configuration.
Conditioning Methods for Exact and Approximate Inference in Causal Networks
Venue: arXiv cs.AI 2013
Year: 2013

We present two algorithms for exact and approximate inference in causal networks. The first algorithm, dynamic conditioning, is a refinement of cutset conditioning that has linear complexity on some networks for which cutset conditioning is exponential. The second algorithm, B-conditioning, is an algorithm for approximate inference that allows one to trade-off the quality of approximations with the computation time. We also present some experimental results illustrating the properties of the proposed algorithms.
Independence Concepts for Convex Sets of Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we study different concepts of independence for convex sets of probabilities. There will be two basic ideas for independence. The first is irrelevance. Two variables are independent when a change on the knowledge about one variable does not affect the other. The second one is factorization. Two variables are independent when the joint convex set of probabilities can be decomposed on the product of marginal convex sets. In the case of the Theory of Probability, these two starting points give rise to the same definition. In the case of convex sets of probabilities, the resulting concepts will be strongly related, but they will not be equivalent. As application of the concept of independence, we shall consider the problem of building a global convex set from marginal convex sets of probabilities.
Numerical Representations of Acceptance
Venue: arXiv cs.AI 2013
Year: 2013

Accepting a proposition means that our confidence in this proposition is strictly greater than the confidence in its negation. This paper investigates the subclass of uncertainty measures, expressing confidence, that capture the idea of acceptance, what we call acceptance functions. Due to the monotonicity property of confidence measures, the acceptance of a proposition entails the acceptance of any of its logical consequences. In agreement with the idea that a belief set (in the sense of Gardenfors) must be closed under logical consequence, it is also required that the separate acceptance o two propositions entail the acceptance of their conjunction. Necessity (and possibility) measures agree with this view of acceptance while probability and belief functions generally do not. General properties of acceptance functions are estabilished. The motivation behind this work is the investigation of a setting for belief revision more general than the one proposed by Alchourron, Gardenfors and Makinson, in connection with the notion of conditioning.
Plausibility Measures: A User's Guide
Venue: arXiv cs.AI 2013
Year: 2013

We examine a new approach to modeling uncertainty based on plausibility measures, where a plausibility measure just associates with an event its plausibility, an element is some partially ordered set. This approach is easily seen to generalize other approaches to modeling uncertainty, such as probability measures, belief functions, and possibility measures. The lack of structure in a plausibility measure makes it easy for us to add structure on an "as needed" basis, letting us examine what is required to ensure that a plausibility measure has certain properties of interest. This gives us insight into the essential features of the properties in question, while allowing us to prove general results that apply to many approaches to reasoning about uncertainty. Plausibility measures have already proved useful in analyzing default reasoning. In this paper, we examine their "algebraic properties," analogues to the use of + and * in probability theory. An understanding of such properties will be essential if plausibility measures are to be used in practice as a representation tool.
Probabilistic Temporal Reasoning with Endogenous Change
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a probabilistic model for reasoning about the state of a system as it changes over time, both due to exogenous and endogenous influences. Our target domain is a class of medical prediction problems that are neither so urgent as to preclude careful diagnosis nor progress so slowly as to allow arbitrary testing and treatment options. In these domains there is typically enough time to gather information about the patient's state and consider alternative diagnoses and treatments, but the temporal interaction between the timing of tests, treatments, and the course of the disease must also be considered. Our approach is to elicit a qualitative structural model of the patient from a human expert---the model identifies important attributes, the way in which exogenous changes affect attribute values, and the way in which the patient's condition changes endogenously. We then elicit probabilistic information to capture the expert's uncertainty about the effects of tests and treatments and the nature and timing of endogenous state changes. This paper describes the model in the context of a problem in treating vehicle accident trauma, and suggests a method for solving the model based on the technique of sequential imputation. A complementary goal of this work is to understand and synthesize a disparate collection of research efforts all using the name ?probabilistic temporal reasoning.? This paper analyzes related work and points out essential differences between our proposed model and other approaches in the literature.
On the Complexity of Solving Markov Decision Problems
Venue: arXiv cs.AI 2013
Year: 2013

Markov decision problems (MDPs) provide the foundations for a number of problems of interest to AI researchers studying automated planning and reinforcement learning. In this paper, we summarize results regarding the complexity of solving MDPs and the running time of MDP solution algorithms. We argue that, although MDPs can be solved efficiently in theory, more study is needed to reveal practical algorithms for solving large problems quickly. To encourage future research, we sketch some alternative methods of analysis that rely on the structure of MDPs.
Causal Inference and Causal Explanation with Background Knowledge
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents correct algorithms for answering the following two questions; (i) Does there exist a causal explanation consistent with a set of background knowledge which explains all of the observed independence facts in a sample? (ii) Given that there is such a causal explanation what are the causal relationships common to every such causal explanation?
On the Testability of Causal Models with Latent and Instrumental Variables
Venue: arXiv cs.AI 2013
Year: 2013

Certain causal models involving unmeasured variables induce no independence constraints among the observed variables but imply, nevertheless, inequality contraints on the observed distribution. This paper derives a general formula for such instrumental variables, that is, exogenous variables that directly affect some variables but not all. With the help of this formula, it is possible to test whether a model involving instrumental variables may account for the data, or, conversely, whether a given variables can be deemed instrumental.
Defaults and Infinitesimals: Defeasible Inference by Nonarchimedean Entropy-Maximization
Venue: arXiv cs.AI 2013
Year: 2013

We develop a new semantics for defeasible inference based on extended probability measures allowed to take infinitesimal values, on the interpretation of defaults as generalized conditional probability constraints and on a preferred-model implementation of entropy maximization.
Optimization of Inter-Subnet Belief Updating in Multiply Sectioned Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

Recent developments show that Multiply Sectioned Bayesian Networks (MSBNs) can be used for diagnosis of natural systems as well as for model-based diagnosis of artificial systems. They can be applied to single-agent oriented reasoning systems as well as multi-agent distributed probabilistic reasoning systems. Belief propagation between a pair of subnets plays a central role in maintenance of global consistency in a MSBN. This paper studies the operation UpdateBelief, presented originally with MSBNs, for inter-subnet propagation. We analyze how the operation achieves its intended functionality, which provides hints as for how its efficiency can be improved. We then define two new versions of UpdateBelief that reduce the computation time for inter-subnet propagation. One of them is optimal in the sense that the minimum amount of computation for coordinating multi-linkage belief propagation is required. The optimization problem is solved through the solution of a graph-theoretic problem: the minimum weight open tour in a tree.
Pooling-Invariant Image Feature Learning
Venue: arXiv cs.CV 2013
Year: 2013

Unsupervised dictionary learning has been a key component in state-of-the-art computer vision recognition architectures. While highly effective methods exist for patch-based dictionary learning, these methods may learn redundant features after the pooling stage in a given early vision architecture. In this paper, we offer a novel dictionary learning scheme to efficiently take into account the invariance of learned features after the spatial pooling stage. The algorithm is built on simple clustering, and thus enjoys efficiency and scalability. We discuss the underlying mechanism that justifies the use of clustering algorithms, and empirically show that the algorithm finds better dictionaries than patch-based methods with the same dictionary size.
Q#, a quantum computation package for the .NET platform
Venue: arXiv cs.ET 2013
Year: 2013

Quantum computing is a promising approach of computation that is based on equations from Quantum Mechanics. A simulator for quantum algorithms must be capable of performing heavy mathematical matrix transforms. The design of the simulator itself takes one of three forms: Quantum Turing Machine, Network Model or circuit model of connected gates or, Quantum Programming Language, yet, some simulators are hybrid. We studied previous simulators and then we adopt features from three simulators of different implementation languages, different paradigms, and for different platforms. They are Quantum Computing Language (QCL), QUASI, and Quantum Optics Toolbox for Matlab 5. Our simulator for quantum algorithms takes the form of a package or a programming library for Quantum computing, with a case study showing the ability of using it in the circuit model. The .NET is a promising platform for computing. VB.NET is an easy, high productive programming language with the full power and functionality provided by the .NET framework. It is highly readable, writeable, and flexible language, compared to another language such as C#.NET in many aspects. We adopted VB.NET although its shortage in built-in mathematical complex and matrix operations, compared to Matlab. For implementation, we first built a mathematical core of matrix operations. Then, we built a quantum core which contains: basic qubits and register operations, basic 1D, 2D, and 3D quantum gates, and multi-view visualization of the quantum state, then a window for demos to show you how to use and get the most of the package.
Software model refactoring based on performance analysis: better working on software or performance side?
Venue: arXiv cs.PF 2013
Year: 2013

Several approaches have been introduced in the last few years to tackle the problem of interpreting model-based performance analysis results and translating them into architectural feedback. Typically the interpretation can take place by browsing either the software model or the performance model. In this paper, we compare two approaches that we have recently introduced for this goal: one based on the detection and solution of performance antipatterns, and another one based on bidirectional model transformations between software and performance models. We apply both approaches to the same example in order to illustrate the differences in the obtained performance results. Thereafter, we raise the level of abstraction and we discuss the pros and cons of working on the software side and on the performance side.
Towards a Formal Framework for Mobile, Service-Oriented Sensor-Actuator Networks
Venue: arXiv cs.NI 2013
Year: 2013

Service-oriented sensor-actuator networks (SOSANETs) are deployed in health-critical applications like patient monitoring and have to fulfill strong safety requirements. However, a framework for the rigorous formal modeling and analysis of SOSANETs does not exist. In particular, there is currently no support for the verification of correct network behavior after node failure or loss/addition of communication links. To overcome this problem, we propose a formal framework for SOSANETs. The main idea is to base our framework on the π-calculus, a formally defined, compositional and well-established formalism. We choose KLAIM, an existing formal language based on the π-calculus as the foundation for our framework. With that, we are able to formally model SOSANETs with possible topology changes and network failures. This provides the basis for our future work on prediction, analysis and verification of the network behavior of these systems. Furthermore, we illustrate the real-life applicability of this approach by modeling and extending a use case scenario from the medical domain.
A Virtual World Model to Enhance Tourism Destination Accessibility in Developing Countries
Venue: arXiv cs.CY 2013
Year: 2013

The problem of destination accessibility is a vital concern in the sustainable tourism development in the emerging regions due to the increasing numbers of tourism business growth in the recent times. Tourism is one of the potential foreign exchange earning sectors, which place sustainability as one of the main success metrics for benchmarking the industry's overall development. On the other hand, there are several destinations, which are inaccessible to tourists due to several reasons. Underutilization of potential destinations in both pre purchase and consumption stages is a strategic disadvantage for emerging countries on leading their tourism industry towards sustainability. A virtual world model to increase the destination accessibility of tourism products has been proposed. The model has to be designed with visual and auditory experience to tourists. The model is expected to enhance the accessibility of destinations for users of different categories. Elderly users, users with panic disorders, users with mobility impairments also will be able to enjoy traveling experience just same as other, through the proposed model.