OpenRaiser/Intern-Atlas huggingface dataset:
Matroid Bandits: Fast Combinatorial Optimization with Learning
Venue: arXiv cs.LG 2014
Year: 2014

A matroid is a notion of independence in combinatorial optimization which is closely related to computational efficiency. In particular, it is well known that the maximum of a constrained modular function can be found greedily if and only if the constraints are associated with a matroid. In this paper, we bring together the ideas of bandits and matroids, and propose a new class of combinatorial bandits, matroid bandits. The objective in these problems is to learn how to maximize a modular function on a matroid. This function is stochastic and initially unknown. We propose a practical algorithm for solving our problem, Optimistic Matroid Maximization (OMM); and prove two upper bounds, gap-dependent and gap-free, on its regret. Both bounds are sublinear in time and at most linear in all other quantities of interest. The gap-dependent upper bound is tight and we prove a matching lower bound on a partition matroid bandit. Finally, we evaluate our method on three real-world problems and show that it is practical.
Interactive Debugging of ASP Programs
Venue: arXiv cs.AI 2014
Year: 2014

Broad application of answer set programming (ASP) for declarative problem solving requires the development of tools supporting the coding process. Program debugging is one of the crucial activities within this process. Recently suggested ASP debugging approaches allow efficient computation of possible explanations of a fault. However, even for a small program a debugger might return a large number of possible explanations and selection of the correct one must be done manually. In this paper we present an interactive query-based ASP debugging method which extends previous approaches and finds a preferred explanation by means of observations. The system queries a programmer whether a set of ground atoms must be true in all (cautiously) or some (bravely) answer sets of the program. Since some queries can be more informative than the others, we discuss query selection strategies which, given user's preferences for an explanation, can find the best query. That is, the query an answer of which reduces the overall number of queries required for the identification of a preferred explanation.
SMT-Based Bounded Model Checking of Fixed-Point Digital Controllers
Venue: arXiv cs.SY 2014
Year: 2014

Digital controllers have several advantages with respect to their flexibility and design's simplicity. However, they are subject to problems that are not faced by analog controllers. In particular, these problems are related to the finite word-length implementation that might lead to overflows, limit cycles, and time constraints in fixed-point processors. This paper proposes a new method to detect design's errors in digital controllers using a state-of-the art bounded model checker based on satisfiability modulo theories. The experiments with digital controllers for a ball and beam plant demonstrate that the proposed method can be very effective in finding errors in digital controllers than other existing approaches based on traditional simulations tools.
Rhythmic generation of infinite trees and languages
Venue: arXiv cs.FL 2014
Year: 2014

This work builds on the notion of breadth-first signature of infinite trees and (prefix-closed) languages introduced by the authors in a previous work. We focus here on periodic signatures, a case coming from the study of rational base numeration systems; the language of integer representations in base~$\frac{p}{q}$ has a purely periodic signature whose period is derived from the Christoffel word of slope~$\frac{p}{q}$. Conversely, we characterise languages whose signature are purely periodic as representations of integers in such number systems with non-canonical alphabets of digits.
Experimental Implementation of an Invariant Extended Kalman Filter-based Scan Matching SLAM
Venue: arXiv cs.SY 2014
Year: 2014

We describe an application of the Invariant Extended Kalman Filter (IEKF) design methodology to the scan matching SLAM problem. We review the theoretical foundations of the IEKF and its practical interest of guaranteeing robustness to poor state estimates, then implement the filter on a wheeled robot hardware platform. The proposed design is successfully validated in experimental testing.
Obtaining Information about Queries behind Views and Dependencies
Venue: arXiv cs.DB 2014
Year: 2014

We consider the problems of finding and determining certain query answers and of determining containment between queries; each problem is formulated in presence of materialized views and dependencies under the closed-world assumption. We show a tight relationship between the problems in this setting. Further, we introduce algorithms for solving each problem for those inputs where all the queries and views are conjunctive, and the dependencies are embedded weakly acyclic. We also determine the complexity of each problem under the security-relevant complexity measure introduced by Zhang and Mendelzon in 2005. The problems studied in this paper are fundamental in ensuring correct specification of database access-control policies, in particular in case of fine-grained access control. Our approaches can also be applied in the areas of inference control, secure data publishing, and database auditing.
Privacy in Sensor-Driven Human Data Collection: A Guide for Practitioners
Venue: arXiv cs.CY 2014
Year: 2014

In recent years, the amount of information collected about human beings has increased dramatically. This development has been partially driven by individuals posting and storing data about themselves and friends using online social networks or collecting their data for self-tracking purposes (quantified-self movement). Across the sciences, researchers conduct studies collecting data with an unprecedented resolution and scale. Using computational power combined with mathematical models, such rich datasets can be mined to infer underlying patterns, thereby providing insights into human nature. Much of the data collected is sensitive. It is private in the sense that most individuals would feel uncomfortable sharing their collected personal data publicly. For this reason, the need for solutions to ensure the privacy of the individuals generating data has grown alongside the data collection efforts. Out of all the massive data collection efforts, this paper focuses on efforts directly instrumenting human behavior, and notes that -- in many cases -- the privacy of participants is not sufficiently addressed. For example, study purposes are often not explicit, informed consent is ill-defined, and security and sharing protocols are only partially disclosed. This paper provides a survey of the work related to addressing privacy issues in research studies that collect detailed sensor data on human behavior. Reflections on the key problems and recommendations for future work are included. We hope the overview of the privacy-related practices in massive data collection studies can be used as a frame of reference for practitioners in the field. Although focused on data collection in an academic context, we believe that many of the challenges and solutions we identify are also relevant and useful for other domains where massive data collection takes place, including businesses and governments.
An ESPRIT-Based Approach for 2-D Localization of Incoherently Distributed Sources in Massive MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, an approach of estimating signal parameters via rotational invariance technique (ESPRIT) is proposed for two-dimensional (2-D) localization of incoherently distributed (ID) sources in large-scale/massive multiple-input multiple-output (MIMO) systems. The traditional ESPRIT-based methods are valid only for one-dimensional (1-D) localization of the ID sources. By contrast, in the proposed approach the signal subspace is constructed for estimating the nominal azimuth and elevation direction-of-arrivals and the angular spreads. The proposed estimator enjoys closed-form expressions and hence it bypasses the searching over the entire feasible field. Therefore, it imposes significantly lower computational complexity than the conventional 2-D estimation approaches. Our analysis shows that the estimation performance of the proposed approach improves when the large-scale/massive MIMO systems are employed. The approximate Cramér-Rao bound of the proposed estimator for the 2-D localization is also derived. Numerical results demonstrate that albeit the proposed estimation method is comparable with the traditional 2-D estimators in terms of performance, it benefits from a remarkably lower computational complexity.
State Machine Flattening: Mapping Study and Assessment
Venue: arXiv cs.SE 2014
Year: 2014

State machine formalisms equipped with hierarchy and parallelism allow to compactly model complex system behaviours. Such models can then be transformed into executable code or inputs for model-based testing and verification techniques. Generated artifacts are mostly flat descriptions of system behaviour. \emph{Flattening} is thus an essential step of these transformations. To assess the importance of flattening, we have defined and applied a systematic mapping process and 30 publications were finally selected. However, it appeared that flattening is rarely the sole focus of the publications and that care devoted to the description and validation of flattening techniques varies greatly. Preliminary assessment of associated tool support indicated limited tool availability and scalability on challenging models. We see this initial investigation as a first step towards generic flattening techniques and scalable tool support, cornerstones of reliable model-based behavioural development.
Catalog Dynamics: Impact of Content Publishing and Perishing on the Performance of a LRU Cache
Venue: arXiv cs.NI 2014
Year: 2014

The Internet heavily relies on Content Distribution Networks and transparent caches to cope with the ever-increasing traffic demand of users. Content, however, is essentially versatile: once published at a given time, its popularity vanishes over time. All requests for a given document are then concentrated between the publishing time and an effective perishing time. In this paper, we propose a new model for the arrival of content requests, which takes into account the dynamical nature of the content catalog. Based on two large traffic traces collected on the Orange network, we use the semi-experimental method and determine invariants of the content request process. This allows us to define a simple mathematical model for content requests; by extending the so-called "Che approximation", we then compute the performance of a LRU cache fed with such a request process, expressed by its hit ratio. We numerically validate the good accuracy of our model by comparison to trace-based simulation.
Continuous Optimization for Fields of Experts Denoising Works
Venue: arXiv cs.CV 2014
Year: 2014

Several recent papers use image denoising with a Fields of Experts prior to benchmark discrete optimization methods. We show that a non-linear least squares solver significantly outperforms all known discrete methods on this problem.
SmartAnnotator: An Interactive Tool for Annotating RGBD Indoor Images
Venue: arXiv cs.CV 2014
Year: 2014

RGBD images with high quality annotations in the form of geometric (i.e., segmentation) and structural (i.e., how do the segments are mutually related in 3D) information provide valuable priors to a large number of scene and image manipulation applications. While it is now simple to acquire RGBD images, annotating them, automatically or manually, remains challenging especially in cluttered noisy environments. We present SmartAnnotator, an interactive system to facilitate annotating RGBD images. The system performs the tedious tasks of grouping pixels, creating potential abstracted cuboids, inferring object interactions in 3D, and comes up with various hypotheses. The user simply has to flip through a list of suggestions for segment labels, finalize a selection, and the system updates the remaining hypotheses. As objects are finalized, the process speeds up with fewer ambiguities to resolve. Further, as more scenes are annotated, the system makes better suggestions based on structural and geometric priors learns from the previous annotation sessions. We test our system on a large number of database scenes and report significant improvements over naive low-level annotation tools.
Examining Perceptions of Astronomy Images Across Mobile Platforms
Venue: arXiv cs.HC 2014
Year: 2014

Modern society has led many people to become consumers of data unlike previous generations. How this shift in the way information is communicated and received - including in areas of science - and affects perception and comprehension is still an open question. This study examined one aspect of this digital age: perceptions of astronomical images and their labels, on mobile platforms. Participants were n = 2183 respondents to an online survey, and two focus groups (n = 12 astrophysicists; n = 11 lay public). Online participants were randomly assigned to 1 of 12 images, and compared two label formats. Focus groups compared mobile devices and label formats. Results indicated that the size and quality of the images on the mobile devices affected label comprehension and engagement. The question label format was significantly preferred to the fun fact. Results are discussed in terms of effective science communication using technology.
Energy-Throughput Trade-offs in a Wireless Sensor Network with Mobile Relay
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we analyze the trade-offs between energy and throughput for links in a wireless sensor network. Our application of interest is one in which a number of low-powered sensors need to wirelessly communicate their measurements to a communications sink, or destination node, for communication to a central processor. We focus on one particular sensor source, and consider the case where the distance to the destination is beyond the peak power of the source. A relay node is required. Transmission energy of the sensor and the relay can be adjusted to minimize the total energy for a given throughput of the connection from sensor source to destination. We introduce a bounded random walk model for movement of the relay between the sensor and destination nodes, and characterize the total transmission energy and throughput performance using Markov steady state analysis. Based on the trade-offs between total energy and throughput we propose a new time-sharing protocol to exploit the movement of the relay to reduce the total energy. We demonstrate the effectiveness of time-sharing for minimizing the total energy consumption while achieving the throughput requirement. We then show that the time-sharing scheme is more energy efficient than the popular sleep mode scheme.
Simulation Based: Study and Analysis of Routing Protocol in Vehicular Ad-hoc Network Environment
Venue: arXiv cs.NI 2014
Year: 2014

A Vehicular Ad hoc Network consists of vehicles which communicate with each other and exchange data via wireless communication links available between the vehicles which are in communication ranges of vehicles to improve the road safety in city.The communication between vehicles is used to provide road safety, comfort and entertainment.The performance of communication depends on how better routing takes place in the network.Routing data between the source and destination vehicle depends on the routing protocols being used in vehicular adhoc network.In this simulation based study we investigated about different ad hoc routing protocols for vehicular adhoc network.The main goal of our study was to identify which ad hoc routing protocol has better performance in highly mobile environment of vehicular adhoc network.We have measured the performance of routing protocols using 802.11p in vehicular adhoc network in which we considered the scenario of city i.e. Route between Nerul and Vashi where we have taken 1200 different types of vehicles and checked their performance.Routing protocols are selected after the literature review.The selected protocols are then evaluated through simulation under 802.11p in terms of performance metrics i.e PDR & E2E delay.
Column Weight Two and Three LDPC Codes with High Rates and Large Girths
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the concept of the {\it broken diagonal pair} in the chess-like square board is used to define some well-structured block designs whose incidence matrices can be considered as the parity-check matrices of some high rate cycle codes with girth 12. The structure of the proposed parity-check matrices significantly reduces the complexity of encoding and decoding. Interestingly, the constructed regular cycle codes with row-weights $t$, $3\leq t \leq 20$, $t\neq 7, 15, 16$, have the best lengths among the known regular girth-12 cycle codes. In addition, the proposed cycle codes can be easily extended to some high rate column weight-3 LDPC codes with girth 6. Simulation results show that the constructed codes achieve excellent performances, specially the constructed column weight 3 LDPC codes outperform LDPC codes based on Steiner triple systems (STS).
Wireless Information and Power Transfer in Cooperative Networks with Spatially Random Relays
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the application of wireless information and power transfer to cooperative networks is investigated, where the relays in the network are randomly located and based on the decode-forward strategy. For the scenario with one source-destination pair, three different strategies for using the available relays are studied, and their impact on the outage probability and diversity gain is characterized by applying stochastic geometry. By using the assumptions that the path loss exponent is two and that the relay-destination distances are much larger than the source-relay distances, closed form analytical results can be developed to demonstrate that the use of energy harvesting relays can achieve the same diversity gain as the case with conventional self-powered relays. For the scenario with multiple sources, the relays can be viewed as a type of scarce resource, where the sources compete with each other to get help from the relays. Such a competition is modeled as a coalition formation game, and two distributed game theoretic algorithms are developed based on different payoff functions. Simulation results are provided to confirm the accuracy of the developed analytical results and facilitate a better performance comparison.
Infinitary Term Rewriting for Weakly Orthogonal Systems: Properties and Counterexamples
Venue: arXiv cs.LO 2014
Year: 2014

We present some contributions to the theory of infinitary rewriting for weakly orthogonal term rewrite systems, in which critical pairs may occur provided they are trivial. We show that the infinitary unique normal form property fails by an example of a weakly orthogonal TRS with two collapsing rules. By translating this example, we show that this property also fails for the infinitary lambda-beta-eta-calculus. As positive results we obtain the following: Infinitary confluence, and hence the infinitary unique normal forms property, holds for weakly orthogonal TRSs that do not contain collapsing rules. To this end we refine the compression lemma. Furthermore, we establish the triangle and diamond properties for infinitary multi-steps (complete developments) in weakly orthogonal TRSs, by refining an earlier cluster-analysis for the finite case.
Coherent Multi-Sentence Video Description with Variable Level of Detail
Venue: arXiv cs.CV 2014
Year: 2014

Humans can easily describe what they see in a coherent way and at varying level of detail. However, existing approaches for automatic video description are mainly focused on single sentence generation and produce descriptions at a fixed level of detail. In this paper, we address both of these limitations: for a variable level of detail we produce coherent multi-sentence descriptions of complex videos. We follow a two-step approach where we first learn to predict a semantic representation (SR) from video and then generate natural language descriptions from the SR. To produce consistent multi-sentence descriptions, we model across-sentence consistency at the level of the SR by enforcing a consistent topic. We also contribute both to the visual recognition of objects proposing a hand-centric approach as well as to the robust generation of sentences using a word lattice. Human judges rate our multi-sentence descriptions as more readable, correct, and relevant than related work. To understand the difference between more detailed and shorter descriptions, we collect and analyze a video description corpus of three levels of detail.
Embedding Cryptographic Features in Compressive Sensing
Venue: arXiv cs.CR 2014
Year: 2014

Compressive sensing (CS) has been widely studied and applied in many fields. Recently, the way to perform secure compressive sensing (SCS) has become a topic of growing interest. The existing works on SCS usually take the sensing matrix as a key and the resultant security level is not evaluated in depth. They can only be considered as a preliminary exploration on SCS, but a concrete and operable encipher model is not given yet. In this paper, we are going to investigate SCS in a systematic way. The relationship between CS and symmetric-key cipher indicates some possible encryption models. To this end, we propose the two-level protection models (TLPM) for SCS which are developed from measurements taking and something else, respectively. It is believed that these models will provide a new point of view and stimulate further research in both CS and cryptography. Specifically, an efficient and secure encryption scheme for parallel compressive sensing (PCS) is designed by embedding a two-layer protection in PCS using chaos. The first layer is undertaken by random permutation on a two-dimensional signal, which is proved to be an acceptable permutation with overwhelming probability. The other layer is to sample the permuted signal column by column with the same chaotic measurement matrix, which satisfies the restricted isometry property of PCS with overwhelming probability. Both the random permutation and the measurement matrix are constructed under the control of a chaotic system. Simulation results show that unlike the general joint compression and encryption schemes in which encryption always leads to the same or a lower compression ratio, the proposed approach of embedding encryption in PCS actually improves the compression performance. Besides, the proposed approach possesses high transmission robustness against additive Gaussian white noise and cropping attack.
Resolution in Linguistic First Order Logic based on Linear Symmetrical Hedge Algebra
Venue: arXiv cs.LO 2014
Year: 2014

This paper focuses on resolution in linguistic first order logic with truth value taken from linear symmetrical hedge algebra. We build the basic components of linguistic first order logic, including syntax and semantics. We present a resolution principle for our logic to resolve on two clauses having contradictory linguistic truth values. Since linguistic information is uncertain, inference in our linguistic logic is approximate. Therefore, we introduce the concept of reliability in order to capture the natural approximation of the resolution inference rule.