OpenRaiser/Intern-Atlas huggingface dataset:
Online Ranking: Discrete Choice, Spearman Correlation and Other Feedback
Venue: arXiv cs.LG 2013
Year: 2013

Given a set $V$ of $n$ objects, an online ranking system outputs at each time step a full ranking of the set, observes a feedback of some form and suffers a loss. We study the setting in which the (adversarial) feedback is an element in $V$, and the loss is the position (0th, 1st, 2nd...) of the item in the outputted ranking. More generally, we study a setting in which the feedback is a subset $U$ of at most $k$ elements in $V$, and the loss is the sum of the positions of those elements. We present an algorithm of expected regret $O(n^{3/2}\sqrt{Tk})$ over a time horizon of $T$ steps with respect to the best single ranking in hindsight. This improves previous algorithms and analyses either by a factor of either $Ω(\sqrt{k})$, a factor of $Ω(\sqrt{\log n})$ or by improving running time from quadratic to $O(n\log n)$ per round. We also prove a matching lower bound. Our techniques also imply an improved regret bound for online rank aggregation over the Spearman correlation measure, and to other more complex ranking loss functions.
A Combination of Flow Shop Scheduling and the Shortest Path Problem
Venue: arXiv cs.DS 2013
Year: 2013

This paper studies a combinatorial optimization problem which is obtained by combining the flow shop scheduling problem and the shortest path problem. The objective of the obtained problem is to select a subset of jobs that constitutes a feasible solution to the shortest path problem, and to execute the selected jobs on the flow shop machines to minimize the makespan. We argue that this problem is NP-hard even if the number of machines is two, and is NP-hard in the strong sense for the general case. We propose an intuitive approximation algorithm for the case where the number of machines is an input, and an improved approximation algorithm for fixed number of machines.
On time-reversibility of linear stochastic models
Venue: arXiv cs.SY 2013
Year: 2013

Reversal of the time direction in stochastic systems driven by white noise has been central throughout the development of stochastic realization theory, filtering and smoothing. Similar ideas were developed in connection with certain problems in the theory of moments, where a duality induced by time reversal was introduced to parametrize solutions. In this latter work it was shown that stochastic systems driven by arbitrary second-order stationary processes can be similarly time-reversed. By combining these two sets of ideas we present herein a generalization of time-reversal in stochastic realization theory.
Online Regenerator Placement
Venue: arXiv cs.NI 2013
Year: 2013

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most $d$ hops, for some given positive integer $d$. A regenerator can serve only one lightpath. The placement of regenerators has become an active area of research during recent years, and various optimization problems have been studied. The first such problem is the Regeneration Location Problem ($\prb$), where the goal is to place the regenerators so as to minimize the total number of nodes containing them. We consider two extreme cases of online $\prb$ regarding the value of $d$ and the number $k$ of regenerators that can be used in any single node. (1) $d$ is arbitrary and $k$ unbounded. In this case a feasible solution always exists. We show an $O(\log \abs{X} \cdot \log d)$-competitive randomized algorithm for any network topology, where $X$ is the set of paths of length $d$. The algorithm can be made deterministic in some cases. We show a deterministic lower bound of $Ω\lb$, where $E$ is the edge set. (2) $d=2$ and $k=1$. In this case there is not necessarily a solution for a given input. We distinguish between feasible inputs (for which there is a solution) and infeasible ones. In the latter case, the objective is to satisfy the maximum number of lightpaths. For a path topology we show a lower bound of $\sqrt{l}/2$ for the competitive ratio (where $l$ is the number of internal nodes of the longest lightpath) on infeasible inputs, and a tight bound of 3 for the competitive ratio on feasible inputs.
API design for machine learning software: experiences from the scikit-learn project
Venue: arXiv cs.LG 2013
Year: 2013

Scikit-learn is an increasingly popular machine learning li- brary. Written in Python, it is designed to be simple and efficient, accessible to non-experts, and reusable in various contexts. In this paper, we present and discuss our design choices for the application programming interface (API) of the project. In particular, we describe the simple and elegant interface shared by all learning and processing units in the library and then discuss its advantages in terms of composition and reusability. The paper also comments on implementation details specific to the Python ecosystem and analyzes obstacles faced by users and developers of the library.
Multi-Column Deep Neural Networks for Offline Handwritten Chinese Character Classification
Venue: arXiv cs.CV 2013
Year: 2013

Our Multi-Column Deep Neural Networks achieve best known recognition rates on Chinese characters from the ICDAR 2011 and 2013 offline handwriting competitions, approaching human performance.
A Study on Unsupervised Dictionary Learning and Feature Encoding for Action Classification
Venue: arXiv cs.CV 2013
Year: 2013

Many efforts have been devoted to develop alternative methods to traditional vector quantization in image domain such as sparse coding and soft-assignment. These approaches can be split into a dictionary learning phase and a feature encoding phase which are often closely connected. In this paper, we investigate the effects of these phases by separating them for video-based action classification. We compare several dictionary learning methods and feature encoding schemes through extensive experiments on KTH and HMDB51 datasets. Experimental results indicate that sparse coding performs consistently better than the other encoding methods in large complex dataset (i.e., HMDB51), and it is robust to different dictionaries. For small simple dataset (i.e., KTH) with less variation, however, all the encoding strategies perform competitively. In addition, we note that the strength of sophisticated encoding approaches comes not from their corresponding dictionaries but the encoding mechanisms, and we can just use randomly selected exemplars as dictionaries for video-based action classification.
Throughput Optimal Flow Allocation on Multiple Paths for Random Access Wireless Multi-hop Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we consider random access wireless multi-hop mesh networks with multi-packet reception capabilities where multiple flows are forwarded to the gateways through node disjoint paths. We address the issue of aggregate throughput-optimal flow rate allocation with bounded delay guarantees. We propose a distributed flow rate allocation scheme that formulates flow rate allocation as an optimization problem and derive the conditions for non-convexity for an illustrative topology. We also employ a simple model for the average aggregate throughput achieved by all flows that captures both intra- and inter-path interference. The proposed scheme is evaluated through NS-2 simulations. Our preliminary results are derived from a grid topology and show that the proposed flow allocation scheme slightly underestimates the average aggregate throughput observed in two simulated scenarios with two and three flows respectively. Moreover it achieves significantly higher average aggregate throughput than single path utilization in two different traffic scenarios examined.
Guaranteed Cost Tracking for Uncertain Coupled Multi-agent Systems Using Consensus over a Directed Graph
Venue: arXiv cs.SY 2013
Year: 2013

This paper considers the leader-follower control problem for a linear multi-agent system with directed communication topology and linear nonidentical uncertain coupling subject to integral quadratic constraints (IQCs). A consensus-type control protocol is proposed based on each agent's states relative to its neighbors and leader's state relative to agents which observe the leader. A sufficient condition is obtained by overbounding the cost function. Based on this sufficient condition, a computational algorithm is introduced to minimize the proposed guaranteed bound on tracking performance, which yields a suboptimal bound on the system consensus control and tracking performance. The effectiveness of the proposed method is demonstrated using a simulation example.
Capacity of Non-Malleable Codes
Venue: arXiv cs.IT 2013
Year: 2013

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ in a manner so that tampering the codeword causes the decoder to either output $s$ or a message that is independent of $s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family $F$ of tampering functions that is not too large (for instance, when $|F| \le \exp(2^{αn})$ for some $α\in [0, 1)$ where $n$ is the number of bits in a codeword). In this work, we study the "capacity of non-malleable coding", and establish optimal bounds on the achievable rate as a function of the family size, answering an open problem from Dziembowski et al. (ICS 2010). Specifically, 1. We prove that for every family $F$ with $|F| \le \exp(2^{αn})$, there exist non-malleable codes against $F$ with rate arbitrarily close to $1-α$ (this is achieved w.h.p. by a randomized construction). 2. We show the existence of families of size $\exp(n^{O(1)} 2^{αn})$ against which there is no non-malleable code of rate $1-α$ (in fact this is the case w.h.p for a random family of this size). 3. We also show that $1-α$ is the best achievable rate for the family of functions which are only allowed to tamper the first $αn$ bits of the codeword, which is of special interest. As a corollary, this implies that the capacity of non-malleable coding in the split-state model (where the tampering function acts independently but arbitrarily on the two halves of the codeword) equals 1/2. We also give an efficient Monte Carlo construction of codes of rate close to 1 with polynomial time encoding and decoding that is non-malleable against any fixed $c > 0$ and family $F$ of size $\exp(n^c)$, in particular tampering functions with, say, cubic size circuits.
Machines are benchmarked by code, not algorithms
Venue: arXiv cs.SE 2013
Year: 2013

This article highlights how small modifications to either the source code of a benchmark program or the compilation options may impact its behavior on a specific machine. It argues that for evaluating machines, benchmark providers and users be careful to ensure reproducibility of results based on the machine code actually running on the hardware and not just source code. The article uses color to grayscale conversion of digital images as a running example.
Denoising Using Projection Onto Convex Sets (POCS) Based Framework
Venue: arXiv cs.DS 2013
Year: 2013

Two new optimization techniques based on projections onto convex space (POCS) framework for solving convex optimization problems are presented. The dimension of the minimization problem is lifted by one and sets corresponding to the cost function are defined. If the cost function is a convex function in R^N the corresponding set is also a convex set in R^{N+1}. The iterative optimization approach starts with an arbitrary initial estimate in R^{N+1} and an orthogonal projection is performed onto one of the sets in a sequential manner at each step of the optimization problem. The method provides globally optimal solutions in total-variation (TV), filtered variation (FV), L_1, and entropic cost functions. A new denoising algorithm using the TV framework is developed. The new algorithm does not require any of the regularization parameter adjustment. Simulation examples are presented.
A Case-Study on Teaching Undergraduate-Level Software Engineering Course Using Inverted-Classroom, Large-Group, Real-Client and Studio-Based Instruction Model
Venue: arXiv cs.CY 2013
Year: 2013

We present a case-study on teaching an undergraduate level course on Software Engineering (second year and fifth semester of bachelors program in Computer Science) at a State University (New Delhi, India) using a novel teaching instruction model. Our approach has four main elements: inverted or flipped classroom, studio-based learning, real-client projects and deployment, large team and peer evaluation. We present our motivation and approach, challenges encountered, pedagogical benefits, findings (both positive and negative) and recommendations. Our motivation was to teach Software Engineering using an active learning (significantly increasing the engagement and collaboration with the Instructor and other students in the class), team-work, balance between theory and practice, imparting both technical and managerial skills encountered in real-world and problem-based learning (through an intensive semester-long project). We conduct a detailed survey (anonymous, optional and online) and present the results of student responses. Survey results reveal that for nearly every students (class size: 89) the instruction model was new, interesting and had a positive impact on the motivation in addition to meeting the learning outcome of the course.
Exploring the Dynamics of Mass Action Systems
Venue: arXiv cs.CE 2013
Year: 2013

We present the Populus toolkit for exploring the dynamics of mass action systems under different assumptions.
The Fixed-Point Theory of Strictly Contracting Functions on Generalized Ultrametric Semilattices
Venue: arXiv cs.LO 2013
Year: 2013

We introduce a new class of abstract structures, which we call generalized ultrametric semilattices, and in which the meet operation of the semilattice coexists with a generalized distance function in a tightly coordinated way. We prove a constructive fixed-point theorem for strictly contracting functions on directed-complete generalized ultrametric semilattices, and introduce a corresponding induction principle. We cite examples of application in the semantics of logic programming and timed computation, where, until now, the only tool available has been the non-constructive fixed-point theorem of Priess-Crampe and Ribenboim for strictly contracting functions on spherically complete generalized ultrametric semilattices.
Dynamics of Open-Source Software Developer's Commit Behavior: An Empirical Investigation of Subversion
Venue: arXiv cs.SE 2013
Year: 2013

Commit is an important operation of revision control for open-source software (OSS). Recent research has been pursued to explore the statistical laws of such an operation, but few of those papers conduct empirical investigations on commit interval (i.e., the waiting time between two consecutive commits). In this paper, we investigated software developer's collective and individual commit behavior in terms of the distribution of commit intervals, and found that 1) the data sets of project-level commit interval within both the lifecycle and each release of the projects analyzed roughly follow power-law distributions; and 2) lifecycle- and release-level collective commit interval on class files can also be best fitted with power laws. These findings reveal some general (collective) collaborative development patterns of OSS projects, e.g., most of the waiting times between two consecutive commits to a central repository are short, but only a few of them experience a long duration of waiting. Then, the implications of what we found for OSS research were outlined, which could provide an insight into understanding OSS development processes better based on software developers' historical commit behavior.
Detecting induced subgraphs
Venue: arXiv cs.DM 2013
Year: 2013

An \emph{s-graph} is a graph with two kinds of edges: \emph{subdivisible} edges and \emph{real} edges. A \emph{realisation} of an s-graph $B$ is any graph obtained by subdividing subdivisible edges of $B$ into paths of arbitrary length (at least one). Given an s-graph $B$, we study the decision problem $Π_B$ whose instance is a graph $G$ and question is "Does $G$ contain a realisation of $B$ as an induced subgraph?". For several $B$'s, the complexity of $Π_B$ is known and here we give the complexity for several more. Our NP-completeness proofs for $Π_B$'s rely on the NP-completeness proof of the following problem. Let $\cal S$ be a set of graphs and $d$ be an integer. Let $Γ_{\cal S}^d$ be the problem whose instance is $(G, x, y)$ where $G$ is a graph whose maximum degree is at most d, with no induced subgraph in $\cal S$ and $x, y \in V(G)$ are two non-adjacent vertices of degree 2. The question is "Does $G$ contain an induced cycle passing through $x, y$?". Among several results, we prove that $Γ^3_{\emptyset}$ is NP-complete. We give a simple criterion on a connected graph $H$ to decide whether $Γ^{+\infty}_{\{H\}}$ is polynomial or NP-complete. The polynomial cases rely on the algorithm three-in-a-tree, due to Chudnovsky and Seymour.
A Comparative Study of Human thermal face recognition based on Haar wavelet transform (HWT) and Local Binary Pattern (LBP)
Venue: arXiv cs.CV 2013
Year: 2013

Thermal infra-red (IR) images focus on changes of temperature distribution on facial muscles and blood vessels. These temperature changes can be regarded as texture features of images. A comparative study of face recognition methods working in thermal spectrum is carried out in this paper. In these study two local-matching methods based on Haar wavelet transform and Local Binary Pattern (LBP) are analyzed. Wavelet transform is a good tool to analyze multi-scale, multi-direction changes of texture. Local binary patterns (LBP) are a type of feature used for classification in computer vision. Firstly, human thermal IR face image is preprocessed and cropped the face region only from the entire image. Secondly, two different approaches are used to extract the features from the cropped face region. In the first approach, the training images and the test images are processed with Haar wavelet transform and the LL band and the average of LH/HL/HH bands sub-images are created for each face image. Then a total confidence matrix is formed for each face image by taking a weighted sum of the corresponding pixel values of the LL band and average band. For LBP feature extraction, each of the face images in training and test datasets is divided into 161 numbers of sub images, each of size 8X8 pixels. For each such sub images, LBP features are extracted which are concatenated in row wise manner. PCA is performed separately on the individual feature set for dimensionality reeducation. Finally two different classifiers are used to classify face images. One such classifier multi-layer feed forward neural network and another classifier is minimum distance classifier. The Experiments have been performed on the database created at our own laboratory and Terravic Facial IR Database.
Randomness-efficient Curve Samplers
Venue: arXiv cs.CC 2013
Year: 2013

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the sampled curve is still low-degree. This property is often used in combination with the sampling property and has found many applications, including PCP constructions, local decoding of codes, and algebraic PRG constructions. The randomness complexity of curve samplers is a crucial parameter for its applications. It is known that (non-explicit) curve samplers using $O(\log N+\log(1/δ))$ random bits exist, where $N$ is the domain size and $δ$ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in \cite{TU06} where they obtained curve samplers with near-optimal randomness complexity. We present an explicit construction of low-degree curve samplers with {\em optimal} randomness complexity (up to a constant factor), sampling curves of degree $\left(m\log_q(1/δ)\right)^{O(1)}$ in $\mathbb{F}_q^m$. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.
Planning and Optimization of Wireless LANs through Field Measurements
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, the field measurements of signal strength taken at the frequency of 2432 MHz in indoor & outdoor environments are presented and analyzed. The received signal levels from the base station were monitored manually. Total coverage area considered for the measurement campaign consisted of a mixture of different propagation environments. Based on the experimental data obtained, path loss exponent and standard deviation of signal strength variability are derived. It is shown that the values of these parameters vary from region to region in the coverage area. The analysis is purely statistical & is compared with the existing propagation model to determine the path loss exponent & deviation.
Optimal Ternary Cyclic Codes with Minimum Distance Four and Five
Venue: arXiv cs.IT 2013
Year: 2013

Cyclic codes are an important subclass of linear codes and have wide applications in data storage systems, communication systems and consumer electronics. In this paper, two families of optimal ternary cyclic codes are presented. The first family of cyclic codes has parameters $[3^m-1, 3^m-1-2m, 4]$ and contains a class of conjectured cyclic codes and several new classes of optimal cyclic codes. The second family of cyclic codes has parameters $[3^m-1, 3^m-2-2m, 5]$ and contains a number of classes of cyclic codes that are obtained from perfect nonlinear functions over $\fthreem$, where $m>1$ and is a positive integer.
Pattern Matching via Choice Existential Quantifications in Imperative Languages
Venue: arXiv cs.PL 2013
Year: 2013

Selection statements -- if-then-else, switch and try-catch -- are commonly used in modern imperative programming languages. We propose another selection statement called a {\it choice existentially quantified statement}. This statement turns out to be quite useful for pattern matching among several merits. Examples will be provided for this statement.
Strong Normalization for HA + EM1 by Non-Deterministic Choice
Venue: arXiv cs.LO 2013
Year: 2013

We study the strong normalization of a new Curry-Howard correspondence for HA + EM1, constructive Heyting Arithmetic with the excluded middle on Sigma01-formulas. The proof-term language of HA + EM1 consists in the lambda calculus plus an operator ||_a which represents, from the viewpoint of programming, an exception operator with a delimited scope, and from the viewpoint of logic, a restricted version of the excluded middle. We give a strong normalization proof for the system based on a technique of "non-deterministic immersion".
Reversible Logic Elements with Memory and Their Universality
Venue: arXiv cs.FL 2013
Year: 2013

Reversible computing is a paradigm of computation that reflects physical reversibility, one of the fundamental microscopic laws of Nature. In this survey, we discuss topics on reversible logic elements with memory (RLEM), which can be used to build reversible computing systems, and their universality. An RLEM is called universal, if any reversible sequential machine (RSM) can be realized as a circuit composed only of it. Since a finite-state control and a tape cell of a reversible Turing machine (RTM) are formalized as RSMs, any RTM can be constructed from a universal RLEM. Here, we investigate 2-state RLEMs, and show that infinitely many kinds of non-degenerate RLEMs are all universal besides only four exceptions. Non-universality of these exceptional RLEMs is also argued.