OpenRaiser/Intern-Atlas huggingface dataset:
Riesz Logic
Venue: arXiv cs.LO 2014
Year: 2014

We introduce Riesz Logic, whose models are abelian lattice ordered groups, which generalise Riesz spaces (vector lattices), and show soundness and completeness. Our motivation is to provide a logic for distributional semantics of natural language, where words are typically represented as elements of a vector space whose dimensions correspond to contexts in which words may occur. This basis provides a lattice ordering on the space, and this ordering may be interpreted as "distributional entailment". Several axioms of Riesz Logic are familiar from Basic Fuzzy Logic, and we show how the models of these two logics may be related; Riesz Logic may thus be considered a new fuzzy logic. In addition to applications in natural language processing, there is potential for applying the theory to neuro-fuzzy systems.
Power allocation with stackelberg game in femtocell networks: a self-learning approach
Venue: arXiv cs.NI 2014
Year: 2014

This paper investigates the energy-efficient power allocation for a two-tier, underlaid femtocell network. The behaviors of the Macrocell Base Station (MBS) and the Femtocell Users (FUs) are modeled hierarchically as a Stackelberg game. The MBS guarantees its own QoS requirement by charging the FUs individually according to the cross-tier interference, and the FUs responds by controlling the local transmit power non-cooperatively. Due to the limit of information exchange in intra- and inter-tiers, a self-learning based strategy-updating mechanism is proposed for each user to learn the equilibrium strategies. In the same Stackelberg-game framework, two different scenarios based on the continuous and discrete power profiles for the FUs are studied, respectively. The self-learning schemes in the two scenarios are designed based on the local best response. By studying the properties of the proposed game in the two situations, the convergence property of the learning schemes is provided. The simulation results are provided to support the theoretical finding in different situations of the proposed game, and the efficiency of the learning schemes is validated.
$(1,j)$-set problem in graphs
Venue: arXiv cs.DM 2014
Year: 2014

A subset $D \subseteq V $of a graph $G = (V, E)$ is a $(1, j)$-set if every vertex $v \in V \setminus D$ is adjacent to at least $1$ but not more than $j$ vertices in D. The cardinality of a minimum $(1, j)$-set of $G$, denoted as $γ_{(1,j)} (G)$, is called the $(1, j)$-domination number of $G$. Given a graph $G = (V, E)$ and an integer $k$, the decision version of the $(1, j)$-set problem is to decide whether $G$ has a $(1, j)$-set of cardinality at most $k$. In this paper, we first obtain an upper bound on $γ_{(1,j)} (G)$ using probabilistic methods, for bounded minimum and maximum degree graphs. Our bound is constructive, by the randomized algorithm of Moser and Tardos [MT10], We also show that the $(1, j)$- set problem is NP-complete for chordal graphs. Finally, we design two algorithms for finding $γ_{(1,j)} (G)$ of a tree and a split graph, for any fixed $j$, which answers an open question posed in [CHHM13].
Energy-Efficient and Thermal-Aware Resource Management for Heterogeneous Datacenters
Venue: arXiv cs.DC 2014
Year: 2014

We propose in this paper to study the energy-, thermal- and performance-aware resource management in heterogeneous datacenters. Witnessing the continuous development of heterogeneity in datacenters, we are confronted with their different behaviors in terms of performance, power consumption and thermal dissipation: Indeed, heterogeneity at server level lies both in the computing infrastructure (computing power, electrical power consumption) and in the heat removal systems (different enclosure, fans, thermal sinks). Also the physical locations of the servers become important with heterogeneity since some servers can (over)heat others. While many studies address independently these parameters (most of the time performance and power or energy), we show in this paper the necessity to tackle all these aspects for an optimal resource management of the computing resources. This leads to improved energy usage in a heterogeneous datacenter including the cooling of the computer rooms. We build our approach on the concept of heat distribution matrix to handle the mutual influence of the servers, in heterogeneous environments, which is novel in this context. We propose a heuristic to solve the server placement problem and we design a generic greedy framework for the online scheduling problem. We derive several single-objective heuristics (for performance, energy, cooling) and a novel fuzzy-based priority mechanism to handle their tradeoffs. Finally, we show results using extensive simulations fed with actual measurements on heterogeneous servers.
An Efficient Bit Plane X-OR Algorithm for Irreversible Image Steganography
Venue: arXiv cs.MM 2014
Year: 2014

The science of hiding secret information in another message is known as Steganography; hence the presence of secret information is concealed. It is the method of hiding cognitive content in same or another media to avoid recognition by the intruders. This paper introduces new method wherein irreversible steganography is used to hide an image in the same medium so that the secret data is masked. The secret image is known as payload and the carrier is known as cover image. X-OR operation is used amongst mid level bit planes of carrier image and high level bit planes of data image to generate new low level bit planes of the stego image. Recovery process includes the X-ORing of low level bit planes and mid level bit planes of the stego image. Based on the result of the recovery, subsequent data image is generated. A RGB color image is used as carrier and the data image is a grayscale image of dimensions less than or equal to the dimensions of the carrier image. The proposed method greatly increases the embedding capacity without significantly decreasing the PSNR value.
Machine Learning Techniques in Cognitive Radio Networks
Venue: arXiv cs.LG 2014
Year: 2014

Cognitive radio is an intelligent radio that can be programmed and configured dynamically to fully use the frequency resources that are not used by licensed users. It defines the radio devices that are capable of learning and adapting to their transmission to the external radio environment, which means it has some kind of intelligence for monitoring the radio environment, learning the environment and make smart decisions. In this paper, we are reviewing some examples of the usage of machine learning techniques in cognitive radio networks for implementing the intelligent radio.
Symbolic Solving of Extended Regular Expression Inequalities
Venue: arXiv cs.FL 2014
Year: 2014

This paper presents a new solution to the containment problem for extended regular expressions that extends basic regular expressions with intersection and complement operators and consider regular expressions on infinite alphabets based on potentially infinite character sets. Standard approaches deciding the containment do not take extended operators or character sets into account. The algorithm avoids the translation to an expression-equivalent automaton and provides a purely symbolic term rewriting systems for solving regular expressions inequalities. We give a new symbolic decision procedure for the containment problem based on Brzozowski's regular expression derivatives and Antimirov's rewriting approach to check containment. We generalize Brzozowski's syntactic derivative operator to two derivative operators that work with respect to (potentially infinite) representable character sets.
Generalization Analysis for Game-Theoretic Machine Learning
Venue: arXiv cs.LG 2014
Year: 2014

For Internet applications like sponsored search, cautions need to be taken when using machine learning to optimize their mechanisms (e.g., auction) since self-interested agents in these applications may change their behaviors (and thus the data distribution) in response to the mechanisms. To tackle this problem, a framework called game-theoretic machine learning (GTML) was recently proposed, which first learns a Markov behavior model to characterize agents' behaviors, and then learns the optimal mechanism by simulating agents' behavior changes in response to the mechanism. While GTML has demonstrated practical success, its generalization analysis is challenging because the behavior data are non-i.i.d. and dependent on the mechanism. To address this challenge, first, we decompose the generalization error for GTML into the behavior learning error and the mechanism learning error; second, for the behavior learning error, we obtain novel non-asymptotic error bounds for both parametric and non-parametric behavior learning methods; third, for the mechanism learning error, we derive a uniform convergence bound based on a new concept called nested covering number of the mechanism space and the generalization analysis techniques developed for mixing sequences. To the best of our knowledge, this is the first work on the generalization analysis of GTML, and we believe it has general implications to the theoretical analysis of other complicated machine learning problems.
Optimal steering of a linear stochastic system to a final probability distribution, part II
Venue: arXiv cs.SY 2014
Year: 2014

We consider the problem of minimum energy steering of a linear stochastic system to a final prescribed distribution over a finite horizon and to maintain a stationary distribution over an infinite horizon. We present sufficient conditions for optimality in terms of a system of dynamically coupled Riccati equations in the finite horizon case and algebraic in the stationary case. We then address the question of feasibility for both problems. For the finite-horizon case, provided the system is controllable, we prove that without any restriction on the directionality of the stochastic disturbance it is always possible to steer the state to any arbitrary Gaussian distribution over any specified finite time-interval. For the stationary infinite horizon case, it is not always possible to maintain the state at an arbitrary Gaussian distribution through constant state-feedback. It is shown that covariances of admissible stationary Gaussian distributions are characterized by a certain Lyapunov-like equation. We finally present an alternative to solving the system of coupled Riccati equations, by expressing the optimal controls in the form of solutions to (convex) semi-definite programs for both cases. We conclude with an example to steer the state covariance of the distribution of inertial particles to an admissible stationary Gaussian distribution over a finite interval, to be maintained at that stationary distribution thereafter by constant-gain state-feedback control.
Compute-and-Forward: Finding the Best Equation
Venue: arXiv cs.IT 2014
Year: 2014

Compute-and-Forward is an emerging technique to deal with interference. It allows the receiver to decode a suitably chosen integer linear combination of the transmitted messages. The integer coefficients should be adapted to the channel fading state. Optimizing these coefficients is a Shortest Lattice Vector (SLV) problem. In general, the SLV problem is known to be prohibitively complex. In this paper, we show that the particular SLV instance resulting from the Compute-and-Forward problem can be solved in low polynomial complexity and give an explicit deterministic algorithm that is guaranteed to find the optimal solution.
Enhanced Random Forest with Image/Patch-Level Learning for Image Understanding
Venue: arXiv cs.CV 2014
Year: 2014

Image understanding is an important research domain in the computer vision due to its wide real-world applications. For an image understanding framework that uses the Bag-of-Words model representation, the visual codebook is an essential part. Random forest (RF) as a tree-structure discriminative codebook has been a popular choice. However, the performance of the RF can be degraded if the local patch labels are poorly assigned. In this paper, we tackle this problem by a novel way to update the RF codebook learning for a more discriminative codebook with the introduction of the soft class labels, estimated from the pLSA model based on a feedback scheme. The feedback scheme is performed on both the image and patch levels respectively, which is in contrast to the state- of-the-art RF codebook learning that focused on either image or patch level only. Experiments on 15-Scene and C-Pascal datasets had shown the effectiveness of the proposed method in image understanding task.
Polar Coding for the General Wiretap Channel
Venue: arXiv cs.IT 2014
Year: 2014

Information-theoretic work for wiretap channels is mostly based on random coding schemes. Designing practical coding schemes to achieve information-theoretic security is an important problem. By applying the two recently developed techniques for polar codes, we propose a polar coding scheme to achieve the secrecy capacity of the general wiretap channel.
Multi-Agent Shape Formation and Tracking Inspired from a Social Foraging Dynamics
Venue: arXiv cs.NE 2014
Year: 2014

Principle of Swarm Intelligence has recently found widespread application in formation control and automated tracking by the automated multi-agent system. This article proposes an elegant and effective method inspired by foraging dynamics to produce geometric-patterns by the search agents. Starting from a random initial orientation, it is investigated how the foraging dynamics can be modified to achieve convergence of the agents on the desired pattern with almost uniform density. Guided through the proposed dynamics, the agents can also track a moving point by continuously circulating around the point. An analytical treatment supported with computer simulation results is provided to better understand the convergence behaviour of the system.
Tighter Low-rank Approximation via Sampling the Leveraged Element
Venue: arXiv cs.DS 2014
Year: 2014

In this work, we propose a new randomized algorithm for computing a low-rank approximation to a given matrix. Taking an approach different from existing literature, our method first involves a specific biased sampling, with an element being chosen based on the leverage scores of its row and column, and then involves weighted alternating minimization over the factored form of the intended low-rank matrix, to minimize error only on these samples. Our method can leverage input sparsity, yet produce approximations in {\em spectral} (as opposed to the weaker Frobenius) norm; this combines the best aspects of otherwise disparate current results, but with a dependence on the condition number $κ= σ_1/σ_r$. In particular we require $O(nnz(M) + \frac{nκ^2 r^5}{ε^2})$ computations to generate a rank-$r$ approximation to $M$ in spectral norm. In contrast, the best existing method requires $O(nnz(M)+ \frac{nr^2}{ε^4})$ time to compute an approximation in Frobenius norm. Besides the tightness in spectral norm, we have a better dependence on the error $ε$. Our method is naturally and highly parallelizable. Our new approach enables two extensions that are interesting on their own. The first is a new method to directly compute a low-rank approximation (in efficient factored form) to the product of two given matrices; it computes a small random set of entries of the product, and then executes weighted alternating minimization (as before) on these. The sampling strategy is different because now we cannot access leverage scores of the product matrix (but instead have to work with input matrices). The second extension is an improved algorithm with smaller communication complexity for the distributed PCA setting (where each server has small set of rows of the matrix, and want to compute low rank approximation with small amount of communication with other servers).
Novel Degree Distribution Function for LT codes over Finite Field
Venue: arXiv cs.IT 2014
Year: 2014

Luby Transform (LT) code over finite field is a recent research topic. In order to find out the properties of LT codes over finite field, a novel degree distribution function is proposed in this paper. The main thinking of our developed distribution function is to improve the decoding success rate with the same overhead, and still to keep the sparse property for the encoding matrix. Numerical simulations are used to show the general performance of our novel function. Various simulation results show that in the environment of LT codes over finite field, our new degree distribution function performs much better than the degree distribution functions proposed by Luby as the field size increasing. In conclusion, our novel degree distribution function is more suitable to be used in LT codes over finite field.
Multi-View 3D Video Multicast for Broadband IP Networks
Venue: arXiv cs.MM 2014
Year: 2014

With the recent emergence of 3D-supported TVs, video service providers now face an opportunity to provide high resolution multi-view 3D videos over IP networks. One simple way to support efficient communications between a video server and multiple clients is to deliver each desired view in a multicast stream. Nevertheless, it is expected that significantly increased bandwidth will be required to support the transmission of all views in multi-view 3D videos. However, the recent emergence of a new video synthesis technique called Depth-Image-Based Rendering (DIBR) suggests that multi-view 3D video does not necessarily require the transmission of all views. Therefore, we formulate a new problem, named Multi-view and Multicast Delivery Selection Problem (MMDS), and design an algorithm, called MMDEA, to find the optimal solution. Simulation results manifest that using DIBR can effectively reduce bandwidth consumption by 35% compared to the original multicast delivery scheme.
Capacity of Diffusion based Molecular Communication Networks over LTI-Poisson Channels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the capacity of a diffusion based molecular communication network under the model of a Linear Time Invarient-Poisson (LTI-Poisson) channel is studied. Introduced in the context of molecular communication, the LTI-Poisson model is a natural extension of the conventional memoryless Poisson channel to include memory. Exploiting prior art on linear ISI channels, a computable finite-letter characterization of the capacity of single-hop LTI-Poisson networks is provided. Then, the problem of finding more explicit bounds on the capacity is examined, where lower and upper bounds for the point to point case are provided. Furthermore, an approach for bounding mutual information in the low SNR regime using the symmetrized KL divergence is introduced and its applicability to Poisson channels is shown. To best of our knowledge, the first non-trivial upper bound on the capacity of Poisson channel with a maximum transmission constraint in the low SNR regime is found. Numerical results show that the proposed upper bound is of the same order as the capacity in the low SNR regime.
Analysing oscillatory trends of discrete-state stochastic processes through HASL statistical model checking
Venue: arXiv cs.FL 2014
Year: 2014

The application of formal methods to the analysis of stochastic oscillators has been at the focus of several research works in recent times. In this paper we provide insights on the application of an expressive temporal logic formalism, namely the Hybrid Automata Stochastic Logic (HASL), to that issue. We show how one can take advantage of the expressive power of the HASL logic to define and assess relevant characteristics of (stochastic) oscillators.
Softwaretechnische Absicherung intelligenter Systeme im Fahrzeug
Venue: arXiv cs.SE 2014
Year: 2014

"This article describes software engineering techniques to be used in order to ensure the necessary quality of intelligent and therefore massive software-based systems in vehicles. Quality assurance for intelligent software is achieved through a bundle of modern software engineering methods. Architecture and design patterns for securing the software components are supplemented by test concepts and frameworks for validation and checks of robustness of the implementation. These patterns describe established and therefore consolidated solutions for certain problems as for instance reliability or efficient execution. -- Dieser Artikel skizziert, welche Software-Entwurfstechniken heute zum Einsatz kommen können, um intelligente, Software-lastige Systeme im Fahrzeug abzusichern. Dabei spielt zunächst das Qualitätsmanagement durch Software-technische Maßnahmen eine zentrale Rolle. Architektur- und Entwurfmuster für die Software-technische Absicherung von Komponenten werden ergänzt um Test-Konzepte zur Validierung von Spezifikationen und der Robustheit der Implementierung. Architekturen und Entwurfs-Muster beschreiben erprobte und damit konsolidierte Lösungen für bestimmte Problemklassen wie etwa Zuverlässigkeit oder effiziente Ausführung.
Product Line Annotations with UML-F
Venue: arXiv cs.SE 2014
Year: 2014

The Unified Modeling Language (UML) community has started to define so-called profiles in order to better suit the needs of specific domains or settings. Product lines1 represent a special breed of systems they are extensible semi-finished pieces of software. Completing the semi-finished software leads to various software pieces, typically specific applications, which share the same core. Though product lines have been developed for a wide range of domains, they apply common construction principles. The intention of the UML-F profile (for framework architectures) is the definition of a UML subset, enriched with a few UML-compliant extensions, which allows the annotation of such artifacts. This paper presents aspects of the profile with a focus on patterns and exemplifies the profile's usage.
Higher Order Differentiation over Finite Fields with Applications to Generalising the Cube Attack
Venue: arXiv cs.CR 2014
Year: 2014

Higher order differentiation was introduced in a cryptographic context by Lai. Several attacks can be viewed in the context of higher order differentiations, amongst them the cube attack and the AIDA attack. All of the above have been developed for the binary case. We examine differentiation in larger fields, starting with the field $GF(p)$ of integers modulo a prime $p$. We prove a number of results on differentiating polynomials over such fields and then apply these techniques to generalising the cube attack to $GF(p)$. The crucial difference is that now the degree in each variable can be higher than one, and our proposed attack will differentiate several times with respect to each variable (unlike the classical cube attack and its larger field version described by Dinur and Shamir, both of which differentiate at most once with respect to each variable). Finally we describe differentiation over finite fields $GF(p^m)$ with $p^m$ elements and prove that it can be reduced to differentiation over $GF(p)$, so a cube attack over $GF(p^m)$ would be equivalent to cube attacks over $GF(p)$.