OpenRaiser/Intern-Atlas huggingface dataset:
A Mathematical Theory of Learning
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, a mathematical theory of learning is proposed that has many parallels with information theory. We consider Vapnik's General Setting of Learning in which the learning process is defined to be the act of selecting a hypothesis in response to a given training set. Such hypothesis can, for example, be a decision boundary in classification, a set of centroids in clustering, or a set of frequent item-sets in association rule mining. Depending on the hypothesis space and how the final hypothesis is selected, we show that a learning process can be assigned a numeric score, called learning capacity, which is analogous to Shannon's channel capacity and satisfies similar interesting properties as well such as the data-processing inequality and the information-cannot-hurt inequality. In addition, learning capacity provides the tightest possible bound on the difference between true risk and empirical risk of the learning process for all loss functions that are parametrized by the chosen hypothesis. It is also shown that the notion of learning capacity equivalently quantifies how sensitive the choice of the final hypothesis is to a small perturbation in the training set. Consequently, algorithmic stability is both necessary and sufficient for generalization. While the theory does not rely on concentration inequalities, we finally show that analogs to classical results in learning theory using the Probably Approximately Correct (PAC) model can be immediately deduced using this theory, and conclude with information-theoretic bounds to learning capacity.
Existence of Secure Equilibrium in Multi-Player Games with Perfect Information
Venue: arXiv cs.GT 2014
Year: 2014

Secure equilibrium is a refinement of Nash equilibrium, which provides some security to the players against deviations when a player changes his strategy to another best response strategy. The concept of secure equilibrium is specifically developed for assume-guarantee synthesis and has already been applied in this context. Yet, not much is known about its existence in games with more than two players. In this paper, we establish the existence of secure equilibrium in two classes of multi-player perfect information turn-based games: (1) in games with possibly probabilistic transitions, having countable state and finite action spaces and bounded and continuous payoff functions, and (2) in games with only deterministic transitions, having arbitrary state and action spaces and Borel payoff functions with a finite range (in particular, qualitative Borel payoff functions). We show that these results apply to several types of games studied in the literature.
Abstractions and sensor design in partial-information, reactive controller synthesis
Venue: arXiv cs.SY 2014
Year: 2014

Automated synthesis of reactive control protocols from temporal logic specifications has recently attracted considerable attention in various applications in, for example, robotic motion planning, network management, and hardware design. An implicit and often unrealistic assumption in this past work is the availability of complete and precise sensing information during the execution of the controllers. In this paper, we use an abstraction procedure for systems with partial observation and propose a formalism to investigate effects of limitations in sensing. The abstraction procedure enables the existing synthesis methods with partial observation to be applicable and efficient for systems with infinite (or finite but large number of) states. This formalism enables us to systematically discover sensing modalities necessary in order to render the underlying synthesis problems feasible. We use counterexamples, which witness unrealizability potentially due to the limitations in sensing and the coarseness in the abstract system, and interpolation-based techniques to refine the model and the sensing modalities, i.e., to identify new sensors to be included, in such synthesis problems. We demonstrate the method on examples from robotic motion planning.
Distributed Symmetry Breaking in Hypergraphs
Venue: arXiv cs.DC 2014
Year: 2014

Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e., logarithmic run time) randomized algorithms are well-established for MIS and $Δ+1$-coloring in both the LOCAL and CONGEST distributed computing models. On the other hand, comparatively much less is known on the complexity of distributed symmetry breaking in {\em hypergraphs}. In particular, a key question is whether a fast (randomized) algorithm for MIS exists for hypergraphs. In this paper, we study the distributed complexity of symmetry breaking in hypergraphs by presenting distributed randomized algorithms for a variety of fundamental problems under a natural distributed computing model for hypergraphs. We first show that MIS in hypergraphs (of arbitrary dimension) can be solved in $O(\log^2 n)$ rounds ($n$ is the number of nodes of the hypergraph) in the LOCAL model. We then present a key result of this paper --- an $O(Δ^ε\text{polylog}(n))$-round hypergraph MIS algorithm in the CONGEST model where $Δ$ is the maximum node degree of the hypergraph and $ε> 0$ is any arbitrarily small constant. To demonstrate the usefulness of hypergraph MIS, we present applications of our hypergraph algorithm to solving problems in (standard) graphs. In particular, the hypergraph MIS yields fast distributed algorithms for the {\em balanced minimal dominating set} problem (left open in Harris et al. [ICALP 2013]) and the {\em minimal connected dominating set problem}. We also present distributed algorithms for coloring, maximal matching, and maximal clique in hypergraphs.
What Cost Knowledge Management? The Example of Infosys
Venue: arXiv cs.CY 2014
Year: 2014

The term knowledge management (KM) first came to prominence in the late 1990s. Although initially dismissed as a fad, KM continues to be featured in articles concerning business productivity and innovation. And yet, clear-cut examples that demonstrate the success of KM are few and far between. A brief examination of the history of KM explores the reasons for this and looks at some of the assumptions about what KM can achieve. A subsequent analysis of the experiences of Infosys with KM shows that for KM to be successful, organizational leaders need to engage in a continuous process of modification and maintenance. Although KM initiatives can be made to yield worthwhile returns over an extended period, there are often substantial ongoing costs associated with them.
Turkish Text Retrieval Experiments Using Lemur Toolkit
Venue: arXiv cs.IR 2014
Year: 2014

We used Lemur Toolkit, an open source toolkit designed for Information Retrieval (IR) research, for our automated indexing and retrieval experiments on a TREC-like test collection for Turkish. We study and compare three retrieval models Lemur supports, especially Language modeling approach to IR, combined with language specific preprocessing techniques. Our experiments show that all retrieval models benefits from language specific preprocessing in terms of retrieval quality. Also Language Modeling approach is the best performing retrieval model when language specific preprocessing applied.
On Landau's eigenvalue theorem and information cut-sets
Venue: arXiv cs.IT 2014
Year: 2014

A variation of Landau's eigenvalue theorem describing the phase transition of the eigenvalues of a time-frequency limiting, self adjoint operator is presented. The total number of degrees of freedom of square-integrable, multi-dimensional, bandlimited functions is defined in terms of Kolmogorov's $n$-width and computed in some limiting regimes where the original theorem cannot be directly applied. Results are used to characterize up to order the total amount of information that can be transported in time and space by multiple-scattered electromagnetic waves, rigorously addressing a question originally posed in the early works of Toraldo di Francia and Gabor. Applications in the context of wireless communication and electromagnetic sensing are discussed.
Implementation And Performance Evaluation Of Background Subtraction Algorithms
Venue: arXiv cs.CV 2014
Year: 2014

The study evaluates three background subtraction techniques. The techniques ranges from very basic algorithm to state of the art published techniques categorized based on speed, memory requirements and accuracy. Such a review can effectively guide the designer to select the most suitable method for a given application in a principled way. The algorithms used in the study ranges from varying levels of accuracy and computational complexity. Few of them can also deal with real time challenges like rain, snow, hails, swaying branches, objects overlapping, varying light intensity or slow moving objects.
Robust Tracking Control for Constrained Robots
Venue: arXiv cs.RO 2014
Year: 2014

In this paper, a novel robust tracking control law is proposed for constrained robots under unknown stiffness environment. The stability and the robustness of the controller are proved using a Lyapunov-based approach where the relationship between the error dynamics of the robotic system and its energy is investigated. Finally, a 3DOF constrained robotic arm is used to prove the stability, the robustness and the safety of the proposed approach.
Deterministic and probabilistic algorithms for stabilizing discrete-time switched linear systems
Venue: arXiv cs.SY 2014
Year: 2014

In this article we study algorithmic synthesis of the class of stabilizing switching signals for discrete-time switched linear systems proposed in [12]. A weighted digraph is associated in a natural way to a switched system, and the switching signal is expressed as an infinite walk on this weighted digraph. We employ graph-theoretic tools and discuss different algorithms for designing walks whose corresponding switching signals satisfy the stabilizing switching conditions proposed in [12]. We also address the issue of how likely/generic it is for a family of systems to admit stabilizing switching signals, and under mild assumptions give sufficient conditions for the same. Our solutions have both deterministic and probabilistic flavours.
A Round-Robin Type Protocol for Distributed Estimation with $H_\infty$ Consensus
Venue: arXiv cs.SY 2014
Year: 2014

The paper considers a distributed robust estimation problem over a network with directed topology involving continuous time observers. While measurements are available to the observers continuously, the nodes interact according to a Round-Robin rule, at discrete time instances. The results of the paper are sufficient conditions which guarantee a suboptimal $H_\infty$ level of consensus between observers with sampled interconnections.
Halving Balls in Deterministic Linear Time
Venue: arXiv cs.CG 2014
Year: 2014

Let $\D$ be a set of $n$ pairwise disjoint unit balls in $\R^d$ and $P$ the set of their center points. A hyperplane $\Hy$ is an \emph{$m$-separator} for $\D$ if each closed halfspace bounded by $\Hy$ contains at least $m$ points from $P$. This generalizes the notion of halving hyperplanes, which correspond to $n/2$-separators. The analogous notion for point sets has been well studied. Separators have various applications, for instance, in divide-and-conquer schemes. In such a scheme any ball that is intersected by the separating hyperplane may still interact with both sides of the partition. Therefore it is desirable that the separating hyperplane intersects a small number of balls only. We present three deterministic algorithms to bisect or approximately bisect a given set of disjoint unit balls by a hyperplane: Firstly, we present a simple linear-time algorithm to construct an $αn$-separator for balls in $\R^d$, for any $0<α<1/2$, that intersects at most $cn^{(d-1)/d}$ balls, for some constant $c$ that depends on $d$ and $α$. The number of intersected balls is best possible up to the constant $c$. Secondly, we present a near-linear time algorithm to construct an $(n/2-o(n))$-separator in $\R^d$ that intersects $o(n)$ balls. Finally, we give a linear-time algorithm to construct a halving line in $\R^2$ that intersects $O(n^{(5/6)+ε})$ disks. Our results improve the runtime of a disk sliding algorithm by Bereg, Dumitrescu and Pach. In addition, our results improve and derandomize an algorithm to construct a space decomposition used by L{ö}ffler and Mulzer to construct an onion (convex layer) decomposition for imprecise points (any point resides at an unknown location within a given disk).
Proofs of two Theorems concerning Sparse Spacetime Constraints
Venue: arXiv cs.GR 2014
Year: 2014

In the SIGGRAPH 2014 paper [SvTSH14] an approach for animating deformable objects using sparse spacetime constraints is introduced. This report contains the proofs of two theorems presented in the paper.
Towards Cloud Computing: A SWOT Analysis on its Adoption in SMEs
Venue: arXiv cs.DC 2014
Year: 2014

Over the past few years, emergence of cloud computing has notably made an evolution in the IT industry by putting forward an "everything as a service" idea .Cloud Computing is of growing interest to companies throughout the world, but there are many barriers associated with its adoption which should be eliminated. This paper aims to investigate Cloud Computing and discusses the drivers and inhibitors of its adoption. Moreover, an attempt has been made to identify the key stakeholders of Cloud Computing and outline the current security challenges. A SWOT analysis which consists of strengths, weaknesses, opportunities and threats has also carried out in which Cloud Computing adoption for SMEs (Small and Medium-sized Enterprises) is evaluated. Finally, the paper concludes with some further research areas in the field of Cloud Computing.
Distributed Interference-Aware Energy-Efficient Resource Allocation for Device-to-Device Communications Underlaying Cellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

The introduction of device-to-device (D2D) into cellular networks poses many new challenges in the resource allocation design due to the co-channel interference caused by spectrum reuse and limited battery life of user equipments (UEs). In this paper, we propose a distributed interference-aware energy-efficient resource allocation algorithm to maximize each UE's energy efficiency (EE) subject to its specific quality of service (QoS) and maximum transmission power constraints. We model the resource allocation problem as a noncooperative game, in which each player is self-interested and wants to maximize its own EE. The formulated EE maximization problem is a non-convex problem and is transformed into a convex optimization problem by exploiting the properties of the nonlinear fractional programming. An iterative optimization algorithm is proposed and verified through computer simulations.
Texture Based Image Segmentation of Chili Pepper X-Ray Images Using Gabor Filter
Venue: arXiv cs.CV 2014
Year: 2014

Texture segmentation is the process of partitioning an image into regions with different textures containing a similar group of pixels. Detecting the discontinuity of the filter's output and their statistical properties help in segmenting and classifying a given image with different texture regions. In this proposed paper, chili x-ray image texture segmentation is performed by using Gabor filter. The texture segmented result obtained from Gabor filter fed into three texture filters, namely Entropy, Standard Deviation and Range filter. After performing texture analysis, features can be extracted by using Statistical methods. In this paper Gray Level Co-occurrence Matrices and First order statistics are used as feature extraction methods. Features extracted from statistical methods are given to Support Vector Machine (SVM) classifier. Using this methodology, it is found that texture segmentation is followed by the Gray Level Co-occurrence Matrix feature extraction method gives a higher accuracy rate of 84% when compared with First order feature extraction method. Key Words: Texture segmentation, Texture filter, Gabor filter, Feature extraction methods, SVM classifier.
OSCMAC_Duty_Cycle_with_Multi_Helpers_CT_Mode_WILEM_Technology_in_Wireless_Sensor_Networks
Venue: arXiv cs.NI 2014
Year: 2014

Recently, Wireless Sensor Networks (WSNs) grow to be one of the dominant technology trends; new needs are continuously emerging and demanding more complex constraints in a duty cycle, such as extend the life time communication . The MAC layer plays a crucial role in these networks; it controls the communication module and manages the medium sharing. In this work we use OSC-MAC tackles combining with the performance of cooperative transmission (CT) in multi-hop WSN and the Wi-Lem technology
Tier-Aware Resource Allocation in OFDMA Macrocell-Small Cell Networks
Venue: arXiv cs.NI 2014
Year: 2014

We present a joint sub-channel and power allocation framework for downlink transmission an orthogonal frequency-division multiple access (OFDMA)-based cellular network composed of a macrocell overlaid by small cells. In this framework, the resource allocation (RA) problems for both the macrocell and small cells are formulated as optimization problems. Numerical results confirm the performance gains of our proposed RA formulation for the macrocell over the traditional resource allocation based on minimizing the transmission power. Besides, it is shown that the formulation based on convex relaxation yields a similar behavior to the MINLP formulation. Also, the distributed solution converges to the same solution obtained by solving the corresponding convex optimization problem in a centralized fashion.
On the "cracking" scheme in the paper "A directional coupler attack against the Kish key distribution system" by Gunn, Allison and Abbott
Venue: arXiv cs.CR 2014
Year: 2014

Recently, Gunn, Allison and Abbott (GAA) [http://arxiv.org/pdf/1402.2709v2.pdf] proposed a new scheme to utilize electromagnetic waves for eavesdropping on the Kirchhoff-law-Johnson-noise (KLJN) secure key distribution. We proved in a former paper [Fluct. Noise Lett. 13 (2014) 1450016] that GAA's mathematical model is unphysical. Here we analyze GAA's cracking scheme and show that, in the case of a loss-free cable, it provides less eavesdropping information than in the earlier (Bergou)-Scheuer-Yariv mean-square-based attack [Kish LB, Scheuer J, Phys. Lett. A 374 (2010) 2140-2142], while it offers no information in the case of a lossy cable. We also investigate GAA's claim to be experimentally capable of distinguishing - using statistics over a few correlation times only - the distributions of two Gaussian noises with a relative variance difference of less than 10^-8. Normally such distinctions would require hundreds of millions of correlations times to be observable. We identify several potential experimental artifacts as results of poor KLJN design, which can lead to GAA's assertions: deterministic currents due to spurious harmonic components caused by ground loops, DC offset, aliasing, non-Gaussian features including non-linearities and other non-idealities in generators, and the time-derivative nature of GAA's scheme which tends to enhance all of these artifacts.
Improving Image Clustering using Sparse Text and the Wisdom of the Crowds
Venue: arXiv cs.LG 2014
Year: 2014

We propose a method to improve image clustering using sparse text and the wisdom of the crowds. In particular, we present a method to fuse two different kinds of document features, image and text features, and use a common dictionary or "wisdom of the crowds" as the connection between the two different kinds of documents. With the proposed fusion matrix, we use topic modeling via non-negative matrix factorization to cluster documents.
Introduction to RIMEP2: A Multi-Expression Programming System for the Design of Reversible Digital Circuits
Venue: arXiv cs.ET 2014
Year: 2014

Quantum computers are considered as a future alternative to circumvent the heat dissipation problem of VLSI circuits. The synthesis of reversible circuits is a very promising area of study considering the expected further technological advances towards quantum computing. In this report, we propose a linear genetic programming system to design reversible circuits -RIMEP2-. The system has evolved reversible circuits starting from scratch without resorting to a pre-existing library. The results show that among the 26 considered benchmarks, RIMEP2 outperformed the best published solutions for 20 of them and matched the remaining 6. RIMEP2 is presented in this report as a promising method with a considerable potential for reversible circuit design. It will be considered as work reference for future studies based on this method.
Training Deep Fourier Neural Networks To Fit Time-Series Data
Venue: arXiv cs.NE 2014
Year: 2014

We present a method for training a deep neural network containing sinusoidal activation functions to fit to time-series data. Weights are initialized using a fast Fourier transform, then trained with regularization to improve generalization. A simple dynamic parameter tuning method is employed to adjust both the learning rate and regularization term, such that stability and efficient training are both achieved. We show how deeper layers can be utilized to model the observed sequence using a sparser set of sinusoid units, and how non-uniform regularization can improve generalization by promoting the shifting of weight toward simpler units. The method is demonstrated with time-series problems to show that it leads to effective extrapolation of nonlinear trends.
A sampling-based approach to scalable constraint satisfaction in linear sampled-data systems---Part I: Computation
Venue: arXiv cs.SY 2014
Year: 2014

Sampled-data (SD) systems, which are composed of both discrete- and continuous-time components, are arguably one of the most common classes of cyberphysical systems in practice; most modern controllers are implemented on digital platforms while the plant dynamics that are being controlled evolve continuously in time. As with all cyberphysical systems, ensuring hard constraint satisfaction is key in the safe operation of SD systems. A powerful analytical tool for guaranteeing such constraint satisfaction is the viability kernel: the set of all initial conditions for which a safety-preserving control law (that is, a control law that satisfies all input and state constraints) exists. In this paper we present a novel sampling-based algorithm that tightly approximates the viability kernel for high-dimensional sampled-data linear time-invariant (LTI) systems. Unlike prior work in this area, our algorithm formally handles both the discrete and continuous characteristics of SD systems. We prove the correctness and convergence of our approximation technique, provide discussions on heuristic methods to optimally bias the sampling process, and demonstrate the results on a twelve-dimensional flight envelope protection problem.
Predicting Central Topics in a Blog Corpus from a Networks Perspective
Venue: arXiv cs.IR 2014
Year: 2014

In today's content-centric Internet, blogs are becoming increasingly popular and important from a data analysis perspective. According to Wikipedia, there were over 156 million public blogs on the Internet as of February 2011. Blogs are a reflection of our contemporary society. The contents of different blog posts are important from social, psychological, economical and political perspectives. Discovery of important topics in the blogosphere is an area which still needs much exploring. We try to come up with a procedure using probabilistic topic modeling and network centrality measures which identifies the central topics in a blog corpus.