OpenRaiser/Intern-Atlas huggingface dataset:
Unsupervised Feature Learning with C-SVDDNet
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we investigate the problem of learning feature representation from unlabeled data using a single-layer K-means network. A K-means network maps the input data into a feature representation by finding the nearest centroid for each input point, which has attracted researchers' great attention recently due to its simplicity, effectiveness, and scalability. However, one drawback of this feature mapping is that it tends to be unreliable when the training data contains noise. To address this issue, we propose a SVDD based feature learning algorithm that describes the density and distribution of each cluster from K-means with an SVDD ball for more robust feature representation. For this purpose, we present a new SVDD algorithm called C-SVDD that centers the SVDD ball towards the mode of local density of each cluster, and we show that the objective of C-SVDD can be solved very efficiently as a linear programming problem. Additionally, traditional unsupervised feature learning methods usually take an average or sum of local representations to obtain global representation which ignore spatial relationship among them. To use spatial information we propose a global representation with a variant of SIFT descriptor. The architecture is also extended with multiple receptive field scales and multiple pooling sizes. Extensive experiments on several popular object recognition benchmarks, such as STL-10, MINST, Holiday and Copydays shows that the proposed C-SVDDNet method yields comparable or better performance than that of the previous state of the art methods.
Distributed Parameter Estimation with Quantized Communication via Running Average
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we consider the parameter estimation problem over sensor networks in the presence of quantized data and directed communication links. We propose a two-stage algorithm aiming at achieving the centralized sample mean estimate in a distributed manner. Different from the existing algorithms, a running average technique is utilized in the proposed algorithm to smear out the randomness caused by the probabilistic quantization scheme. With the running average technique, it is shown that the centralized sample mean estimate can be achieved both in the mean square and almost sure senses, which is not observed in the conventional consensus algorithms. In addition, the rates of convergence are given to quantify the mean square and almost sure performances. Finally, simulation results are presented to illustrate the effectiveness of the proposed algorithm and highlight the improvements by using running average technique.
Division algebra codes achieve MIMO block fading channel capacity within a constant gap
Venue: arXiv cs.IT 2015
Year: 2015

This work addresses the question of achieving capacity with lattice codes in multi-antenna block fading channels when the number of fading blocks tends to infinity. In contrast to the standard approach in the literature which employs random lattice ensembles, the existence results in this paper are derived from number theory. It is shown that a multiblock construction based on division algebras achieves rates within a constant gap from block fading capacity both under maximum likelihood decoding and naive lattice decoding. First the gap to capacity is shown to depend on the discriminant of the chosen division algebra; then class field theory is applied to build families of algebras with small discriminants. The key element in the construction is the choice of a sequence of division algebras whose centers are number fields with small root discriminants.
Automatic Photo Adjustment Using Deep Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Photo retouching enables photographers to invoke dramatic visual impressions by artistically enhancing their photos through stylistic color and tone adjustments. However, it is also a time-consuming and challenging task that requires advanced skills beyond the abilities of casual photographers. Using an automated algorithm is an appealing alternative to manual work but such an algorithm faces many hurdles. Many photographic styles rely on subtle adjustments that depend on the image content and even its semantics. Further, these adjustments are often spatially varying. Because of these characteristics, existing automatic algorithms are still limited and cover only a subset of these challenges. Recently, deep machine learning has shown unique abilities to address hard problems that resisted machine algorithms for long. This motivated us to explore the use of deep learning in the context of photo editing. In this paper, we explain how to formulate the automatic photo adjustment problem in a way suitable for this approach. We also introduce an image descriptor that accounts for the local semantics of an image. Our experiments demonstrate that our deep learning formulation applied using these descriptors successfully capture sophisticated photographic styles. In particular and unlike previous techniques, it can model local adjustments that depend on the image semantics. We show on several examples that this yields results that are qualitatively and quantitatively better than previous work.
Pattern Backtracking Algorithm for the Workflow Satisfiability Problem
Venue: arXiv cs.DS 2015
Year: 2015

The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorised users to the steps in a workflow specification, subject to certain constraints on the assignment. (Such an assignment is called valid.) The problem is NP-hard even when restricted to the large class of user-independent constraints. Since the number of steps $k$ is relatively small in practice, it is natural to consider a parametrisation of the WSP by $k$. We propose a new fixed-parameter algorithm to solve the WSP with user-independent constraints. The assignments in our method are partitioned into equivalence classes such that the number of classes is exponential in $k$ only. We show that one can decide, in polynomial time, whether there is a valid assignment in an equivalence class. By exploiting this property, our algorithm reduces the search space to the space of equivalence classes, which it browses within a backtracking framework, hence emerging as an efficient yet relatively simple-to-implement or generalise solution method. We empirically evaluate our algorithm against the state-of-the-art methods and show that it clearly wins the competition on the whole range of our test problems and significantly extends the domain of practically solvable instances of the WSP.
Metacarpal Bones Localization in X-ray Imagery Using Particle Filter Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

Statistical methods such as sequential Monte Carlo Methods were proposed for detection, segmentation and tracking of objects in digital images. A similar approach, called Shape Particle Filters was introduced for the segmentation of vertebra, lungs and hearts [1]. In this contribution, a global shape and a local appearance model are derived from specific object annotated X-ray images of the metacarpal bones. In the test data a unique labeling of the bone boundary and the background points and a manual annotation is given. Using a set of local features (Haar-like) in the neighborhood of each pixel a probabilistic pixel classifier is built using the random forest algorithm. To fit the shape model to a new image, a label probability map is extracted and then the optimal shape is obtained by maximizing the probability of each landmark with the Differential Evolution algorithm.
A Fundamental Scale of Descriptions for Analyzing Information Content of Communication Systems
Venue: arXiv cs.IT 2015
Year: 2015

The complexity of a system description is a function of the entropy of its symbolic description. Prior to computing the entropy of the system description, an observation scale has to be assumed. In natural language texts, typical scales are binary, characters, and words. However, considering languages as structures built around certain preconceived set of symbols, like words or characters, is only a presumption. This study depicts the notion of the Description Fundamental Scale as a set of symbols which serves to analyze the essence a language structure. The concept of Fundamental Scale is tested using English and MIDI music texts by means of an algorithm developed to search for a set of symbols, which minimizes the system observed entropy, and therefore best expresses the fundamental scale of the language employed. Test results show that it is possible to find the Fundamental Scale of some languages. The concept of Fundamental Scale, and the method for its determination, emerges as an interesting tool to facilitate the study of languages and complex systems.
Spy vs. Spy: Rumor Source Obfuscation
Venue: arXiv cs.SI 2015
Year: 2015

Anonymous messaging platforms, such as Secret and Whisper, have emerged as important social media for sharing one's thoughts without the fear of being judged by friends, family, or the public. Further, such anonymous platforms are crucial in nations with authoritarian governments; the right to free expression and sometimes the personal safety of the author of the message depend on anonymity. Whether for fear of judgment or personal endangerment, it is crucial to keep anonymous the identity of the user who initially posted a sensitive message. In this paper, we consider an adversary who observes a snapshot of the spread of a message at a certain time. Recent advances in rumor source detection shows that the existing messaging protocols are vulnerable against such an adversary. We introduce a novel messaging protocol, which we call adaptive diffusion, and show that it spreads the messages fast and achieves a perfect obfuscation of the source when the underlying contact network is an infinite regular tree: all users with the message are nearly equally likely to have been the origin of the message. Experiments on a sampled Facebook network show that it effectively hides the location of the source even when the graph is finite, irregular and has cycles. We further consider a stronger adversarial model where a subset of colluding users track the reception of messages. We show that the adaptive diffusion provides a strong protection of the anonymity of the source even under this scenario.
A note about the generalisation of the C-tests
Venue: arXiv cs.AI 2015
Year: 2015

In this exploratory note we ask the question of what a measure of performance for all tasks is like if we use a weighting of tasks based on a difficulty function. This difficulty function depends on the complexity of the (acceptable) solution for the task (instead of a universal distribution over tasks or an adaptive test). The resulting aggregations and decompositions are (now retrospectively) seen as the natural (and trivial) interactive generalisation of the C-tests.
Crash-Tolerant Consensus in Directed Graphs
Venue: arXiv cs.DC 2015
Year: 2015

This work considers a point-to-point network of n nodes connected by directed links, and proves tight necessary and sufficient conditions on the underlying communication graphs for achieving consensus among these nodes under crash faults. We identify the conditions in both synchronous and asynchronous systems
Consistent Classification Algorithms for Multi-class Non-Decomposable Performance Metrics
Venue: arXiv cs.LG 2015
Year: 2015

We study consistency of learning algorithms for a multi-class performance metric that is a non-decomposable function of the confusion matrix of a classifier and cannot be expressed as a sum of losses on individual data points; examples of such performance metrics include the macro F-measure popular in information retrieval and the G-mean metric used in class-imbalanced problems. While there has been much work in recent years in understanding the consistency properties of learning algorithms for `binary' non-decomposable metrics, little is known either about the form of the optimal classifier for a general multi-class non-decomposable metric, or about how these learning algorithms generalize to the multi-class case. In this paper, we provide a unified framework for analysing a multi-class non-decomposable performance metric, where the problem of finding the optimal classifier for the performance metric is viewed as an optimization problem over the space of all confusion matrices achievable under the given distribution. Using this framework, we show that (under a continuous distribution) the optimal classifier for a multi-class performance metric can be obtained as the solution of a cost-sensitive classification problem, thus generalizing several previous results on specific binary non-decomposable metrics. We then design a consistent learning algorithm for concave multi-class performance metrics that proceeds via a sequence of cost-sensitive classification problems, and can be seen as applying the conditional gradient (CG) optimization method over the space of feasible confusion matrices. To our knowledge, this is the first efficient learning algorithm (whose running time is polynomial in the number of classes) that is consistent for a large family of multi-class non-decomposable metrics. Our consistency proof uses a novel technique based on the convergence analysis of the CG method.
A robust sub-linear time R-FFAST algorithm for computing a sparse DFT
Venue: arXiv cs.IT 2015
Year: 2015

The Fast Fourier Transform (FFT) is the most efficiently known way to compute the Discrete Fourier Transform (DFT) of an arbitrary n-length signal, and has a computational complexity of O(n log n). If the DFT X of the signal x has only k non-zero coefficients (where k < n), can we do better? In [1], we addressed this question and presented a novel FFAST (Fast Fourier Aliasing-based Sparse Transform) algorithm that cleverly induces sparse graph alias codes in the DFT domain, via a Chinese-Remainder-Theorem (CRT)-guided sub-sampling operation of the time-domain samples. The resulting sparse graph alias codes are then exploited to devise a fast and iterative onion-peeling style decoder that computes an n length DFT of a signal using only O(k) time-domain samples and O(klog k) computations. The FFAST algorithm is applicable whenever k is sub-linear in n (i.e. k = o(n)), but is obviously most attractive when k is much smaller than n. In this paper, we adapt the FFAST framework of [1] to the case where the time-domain samples are corrupted by a white Gaussian noise. In particular, we show that the extended noise robust algorithm R-FFAST computes an n-length k-sparse DFT X using O(klog ^3 n) noise-corrupted time-domain samples, in O(klog^4n) computations, i.e., sub-linear time complexity. While our theoretical results are for signals with a uniformly random support of the non-zero DFT coefficients and additive white Gaussian noise, we provide simulation results which demonstrates that the R-FFAST algorithm performs well even for signals like MR images, that have an approximately sparse Fourier spectrum with a non-uniform support for the dominant DFT coefficients.
A New Sparse Matrix Vector Multiplication GPU Algorithm Designed for Finite Element Problems
Venue: arXiv cs.MS 2015
Year: 2015

Recently, graphics processors (GPUs) have been increasingly leveraged in a variety of scientific computing applications. However, architectural differences between CPUs and GPUs necessitate the development of algorithms that take advantage of GPU hardware. As sparse matrix vector multiplication (SPMV) operations are commonly used in finite element analysis, a new SPMV algorithm and several variations are developed for unstructured finite element meshes on GPUs. The effective bandwidth of current GPU algorithms and the newly proposed algorithms are measured and analyzed for 15 sparse matrices of varying sizes and varying sparsity structures. The effects of optimization and differences between the new GPU algorithm and its variants are then subsequently studied. Lastly, both new and current SPMV GPU algorithms are utilized in the GPU CG Solver in GPU finite element simulations of the heart. These results are then compared against parallel PETSc finite element implementation results. The effective bandwidth tests indicate that the new algorithms compare very favorably with current algorithms for a wide variety of sparse matrices and can yield very notable benefits. GPU finite element simulation results demonstrate the benefit of using GPUs for finite element analysis, and also show that the proposed algorithms can yield speedup factors up to 12-fold for real finite element applications.
A Data Transparency Framework for Mobile Applications
Venue: arXiv cs.CY 2015
Year: 2015

In today's mobile application marketplace, the ability of consumers to make informed choices regarding their privacy is extremely limited. Consumers largely rely on privacy policies and app permission mechanisms, but these do an inadequate job of conveying how information will be collected, used, stored, and shared. Mobile application developers go largely unrewarded for making apps more privacy conscious as it is difficult to communicate these features to consumers while they are searching for a new app. This paper provides an overview of a framework designed to help consumers make informed choices, and an incentive mechanism to encourage app developers to implement it. This framework includes machine readable privacy policies encouraged by mobile app stores and enhanced by user software agents. Such a framework would provide the foundation required for more advanced forms of privacy management to develop.
Campaign Management under Approval-Driven Voting Rules
Venue: arXiv cs.GT 2015
Year: 2015

Approval-like voting rules, such as Sincere-Strategy Preference-Based Approval voting (SP-AV), the Bucklin rule (an adaptive variant of $k$-Approval voting), and the Fallback rule (an adaptive variant of SP-AV) have many desirable properties: for example, they are easy to understand and encourage the candidates to choose electoral platforms that have a broad appeal. In this paper, we investigate both classic and parameterized computational complexity of electoral campaign management under such rules. We focus on two methods that can be used to promote a given candidate: asking voters to move this candidate upwards in their preference order or asking them to change the number of candidates they approve of. We show that finding an optimal campaign management strategy of the first type is easy for both Bucklin and Fallback. In contrast, the second method is computationally hard even if the degree to which we need to affect the votes is small. Nevertheless, we identify a large class of scenarios that admit fixed-parameter tractable algorithms.
Adaptive Control of 4-DoF Robot manipulator
Venue: arXiv cs.SY 2015
Year: 2015

In experimental robotics, researchers may face uncertainties in parameters of a robot manipulator that they are working with. This uncertainty may be caused by deviations in the manufacturing process of a manipulator, or changes applied to manipulator in the lab for sake of experiments. Another situation when dynamical and inertial parameters of a robot are uncertain arises, is the grasping of objects by a manipulator. In all these situations there is a need for adaptive control strategies that would identify changes in dynamical properties of manipulator and adjust for them. This article presents a work on designing of an adaptive control strategy for 4-DoF manipulator with uncertain dynamical properties, and outcomes of testing of this strategy applied to control of simulator of robot.
Influence of Facebook in Academic Performance of Sri Lankan University Students
Venue: arXiv cs.CY 2015
Year: 2015

Facebook is only an electronic communication between human but unfortunately it has become an addiction for all. This paper examines the usage of Facebook among university students and its influence in their academic performance. The impact of Facebook can either be good or bad on university students and in their academic activities. Even though a closer look on the real impact of Facebook reveals that it leads to several problems in university students academic performances. Today Facebook is somehow destroying the future and academic carrier of university students. At the same time also intended to find the significance of use of Facebook by University students in their academic success with the help of a survey conducted to collect the data among more than 250 students of different Universities in Sri Lanka.
Maximum Rényi Entropy Rate
Venue: arXiv cs.IT 2015
Year: 2015

Two maximization problems of Rényi entropy rate are investigated: the maximization over all stochastic processes whose marginals satisfy a linear constraint, and the Burg-like maximization over all stochastic processes whose autocovariance function begins with some given values. The solutions are related to the solutions to the analogous maximization problems of Shannon entropy rate.
Spotting Trees with Few Leaves
Venue: arXiv cs.DS 2015
Year: 2015

We show two results related to the Hamiltonicity and $k$-Path algorithms in undirected graphs by Björklund [FOCS'10], and Björklund et al., [arXiv'10]. First, we demonstrate that the technique used can be generalized to finding some $k$-vertex tree with $l$ leaves in an $n$-vertex undirected graph in $O^*(1.657^k2^{l/2})$ time. It can be applied as a subroutine to solve the $k$-Internal Spanning Tree ($k$-IST) problem in $O^*(\min(3.455^k, 1.946^n))$ time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time we break the natural barrier of $O^*(2^n)$. Second, we show that the iterated random bipartition employed by the algorithm can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for $k$-Path and Hamiltonicity in any graph of maximum degree $Δ=4,\ldots,12$ or with vector chromatic number at most 8.
A Review on the Tree Edit Distance Problem and Related Path-Decomposition Algorithms
Venue: arXiv cs.DS 2015
Year: 2015

An ordered labeled tree is a tree in which the nodes are labeled and the left-to-right order among siblings is relevant. The edit distance between two ordered labeled trees is the minimum cost of changing one tree into the other through a sequence of edit steps. In the literature, there are a class of algorithms based on different yet closely related path-decomposition schemes. This article reviews the principles of these algorithms, and studies the concepts related to the algorithmic complexities as a consequence of the decomposition schemes.