OpenRaiser/Intern-Atlas huggingface dataset:
Joint cross-domain classification and subspace learning for unsupervised adaptation
Venue: arXiv cs.CV 2015
Year: 2015

Domain adaptation aims at adapting the knowledge acquired on a source domain to a new different but related target domain. Several approaches have beenproposed for classification tasks in the unsupervised scenario, where no labeled target data are available. Most of the attention has been dedicated to searching a new domain-invariant representation, leaving the definition of the prediction function to a second stage. Here we propose to learn both jointly. Specifically we learn the source subspace that best matches the target subspace while at the same time minimizing a regularized misclassification loss. We provide an alternating optimization technique based on stochastic sub-gradient descent to solve the learning problem and we demonstrate its performance on several domain adaptation tasks.
Number field lattices achieve Gaussian and Rayleigh channel capacity within a constant gap
Venue: arXiv cs.IT 2015
Year: 2015

This paper proves that a family of number field lattice codes simultaneously achieves a constant gap to capacity in Rayleigh fast fading and Gaussian channels. The key property in the proof is the existence of infinite towers of Hilbert class fields with bounded root discriminant. The gap to capacity of the proposed families is determined by the root discriminant. The comparison between the Gaussian and fading case reveals that in Rayleigh fading channels the normalized minimum product distance plays an analogous role to the Hermite invariant in Gaussian channels.
Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
Venue: arXiv cs.ET 2015
Year: 2015

Memcomputing is a novel non-Turing paradigm of computation that uses interacting memory cells (memprocessors for short) to store and process information on the same physical platform. It was recently proved mathematically that memcomputing machines have the same computational power of non-deterministic Turing machines. Therefore, they can solve NP-complete problems in polynomial time and, using the appropriate architecture, with resources that only grow polynomially with the input size. The reason for this computational power stems from properties inspired by the brain and shared by any universal memcomputing machine, in particular intrinsic parallelism and information overhead, namely the capability of compressing information in the collective state of the memprocessor network. Here, we show an experimental demonstration of an actual memcomputing architecture that solves the NP-complete version of the subset-sum problem in only one step and is composed of a number of memprocessors that scales linearly with the size of the problem. We have fabricated this architecture using standard microelectronic technology so that it can be easily realized in any laboratory setting. Even though the particular machine presented here is eventually limited by noise--and will thus require error-correcting codes to scale to an arbitrary number of memprocessors--it represents the first proof-of-concept of a machine capable of working with the collective state of interacting memory cells, unlike the present-day single-state machines built using the von Neumann architecture.
Counting K_4-Subdivisions
Venue: arXiv cs.DM 2015
Year: 2015

A fundamental theorem in graph theory states that any 3-connected graph contains a subdivision of $K_4$. As a generalization, we ask for the minimum number of $K_4$-subdivisions that are contained in every $3$-connected graph on $n$ vertices. We prove that there are $Ω(n^3)$ such $K_4$-subdivisions and show that the order of this bound is tight for infinitely many graphs. We further investigate a better bound in dependence on $m$ and prove that the computational complexity of the problem of counting the exact number of $K_4$-subdivisions is $\#P$-hard.
Reaching Approximate Byzantine Consensus with Multi-hop Communication
Venue: arXiv cs.DC 2015
Year: 2015

We address the problem of reaching consensus in the presence of Byzantine faults. In particular, we are interested in investigating the impact of messages relay on the network connectivity for a correct iterative approximate Byzantine consensus algorithm to exist. The network is modeled by a simple directed graph. We assume a node can send messages to another node that is up to $l$ hops away via forwarding by the intermediate nodes on the routes, where $l\in \mathbb{N}$ is a natural number. We characterize the necessary and sufficient topological conditions on the network structure. The tight conditions we found are consistent with the tight conditions identified for $l=1$, where only local communication is allowed, and are strictly weaker for $l>1$. Let $l^*$ denote the length of a longest path in the given network. For $l\ge l^*$ and undirected graphs, our conditions hold if and only if $n\ge 3f+1$ and the node-connectivity of the given graph is at least $2f+1$ , where $n$ is the total number of nodes and $f$ is the maximal number of Byzantine nodes; and for $l\ge l^*$ and directed graphs, our conditions is equivalent to the tight condition found for exact Byzantine consensus. Our sufficiency is shown by constructing a correct algorithm, wherein the trim function is constructed based on investigating a newly introduced minimal messages cover property. The trim function proposed also works over multi-graphs.
$β$-skeletons for a set of line segments in $R^2$
Venue: arXiv cs.CG 2015
Year: 2015

$β$-skeletons are well-known neighborhood graphs for a set of points. We extend this notion to sets of line segments in the Euclidean plane and present algorithms computing such skeletons for the entire range of $β$ values. The main reason of such extension is the possibility to study $β$-skeletons for points moving along given line segments. We show that relations between $β$-skeletons for $β> 1$, $1$-skeleton (Gabriel Graph), and the Delaunay triangulation for sets of points hold also for sets of segments. We present algorithms for computing circle-based and lune-based $β$-skeletons. We describe an algorithm that for $β\geq 1$ computes the $β$-skeleton for a set $S$ of $n$ segments in the Euclidean plane in $O(n^2 α(n) \log n)$ time in the circle-based case and in $O(n^2 λ_4(n))$ in the lune-based one, where the construction relies on the Delaunay triangulation for $S$, $α$ is a functional inverse of Ackermann function and $λ_4(n)$ denotes the maximum possible length of a $(n,4)$ Davenport-Schinzel sequence. When $0 < β< 1$, the $β$-skeleton can be constructed in a $O(n^3 λ_4(n))$ time. In the special case of $β= 1$, which is a generalization of Gabriel Graph, the construction can be carried out in a $O(n \log n)$ time.
Optimal Coding Schemes for the Three-Receiver AWGN Broadcast Channel with Receiver Message Side Information
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the capacity region of the three-receiver AWGN broadcast channel where the receivers (i) have private-message requests and (ii) may know some of the messages requested by other receivers as side information. We first classify all 64 possible side information configurations into eight groups, each consisting of eight members. We next construct transmission schemes, and derive new inner and outer bounds for the groups. This establishes the capacity region for 52 out of 64 possible side information configurations. For six groups (i.e., groups 1, 2, 3, 5, 6, and 8 in our terminology), we establish the capacity region for all their members, and show that it tightens both the best known inner and outer bounds. For group 4, our inner and outer bounds tighten the best known inner bound and/or outer bound for all the group members. Moreover, our bounds coincide at certain regions, which can be characterized by two thresholds. For group 7, our inner and outer bounds coincide for four members, thereby establishing the capacity region. For the remaining four members, our bounds tighten both the best known inner and outer bounds.
Predicting triadic closure in networks using communicability distance functions
Venue: arXiv cs.SI 2015
Year: 2015

We propose a communication-driven mechanism for predicting triadic closure in complex networks. It is mathematically formulated on the basis of communicability distance functions that account for the quality of communication between nodes in the network. We study $25$ real-world networks and show that the proposed method predicts correctly $20\%$ of triadic closures in these networks, in contrast to the $7.6\%$ predicted by a random mechanism. We also show that the communication-driven method outperforms the random mechanism in explaining the clustering coefficient, average path length, and average communicability. The new method also displays some interesting features with regards to optimizing communication in networks.
Semi-supervised Feature Analysis by Mining Correlations among Multiple Tasks
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we propose a novel semi-supervised feature selection framework by mining correlations among multiple tasks and apply it to different multimedia applications. Instead of independently computing the importance of features for each task, our algorithm leverages shared knowledge from multiple related tasks, thus, improving the performance of feature selection. Note that we build our algorithm on assumption that different tasks share common structures. The proposed algorithm selects features in a batch mode, by which the correlations between different features are taken into consideration. Besides, considering the fact that labeling a large amount of training data in real world is both time-consuming and tedious, we adopt manifold learning which exploits both labeled and unlabeled training data for feature space analysis. Since the objective function is non-smooth and difficult to solve, we propose an iterative algorithm with fast convergence. Extensive experiments on different applications demonstrate that our algorithm outperforms other state-of-the-art feature selection algorithms.
Deep convolutional filter banks for texture recognition and segmentation
Venue: arXiv cs.CV 2015
Year: 2015

Research in texture recognition often concentrates on the problem of material recognition in uncluttered conditions, an assumption rarely met by applications. In this work we conduct a first study of material and describable texture at- tributes recognition in clutter, using a new dataset derived from the OpenSurface texture repository. Motivated by the challenge posed by this problem, we propose a new texture descriptor, D-CNN, obtained by Fisher Vector pooling of a Convolutional Neural Network (CNN) filter bank. D-CNN substantially improves the state-of-the-art in texture, mate- rial and scene recognition. Our approach achieves 82.3% accuracy on Flickr material dataset and 81.1% accuracy on MIT indoor scenes, providing absolute gains of more than 10% over existing approaches. D-CNN easily trans- fers across domains without requiring feature adaptation as for methods that build on the fully-connected layers of CNNs. Furthermore, D-CNN can seamlessly incorporate multi-scale information and describe regions of arbitrary shapes and sizes. Our approach is particularly suited at lo- calizing stuff categories and obtains state-of-the-art re- sults on MSRC segmentation dataset, as well as promising results on recognizing materials and surface attributes in clutter on the OpenSurfaces dataset.
Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs
Venue: arXiv cs.CC 2015
Year: 2015

A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity $n^{O(\log n)}$. In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-$3$ circuits. The prior results for the sum of constantly many set-multilinear depth-$3$ circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).
Fisher Vectors Derived from Hybrid Gaussian-Laplacian Mixture Models for Image Annotation
Venue: arXiv cs.CV 2015
Year: 2015

In the traditional object recognition pipeline, descriptors are densely sampled over an image, pooled into a high dimensional non-linear representation and then passed to a classifier. In recent years, Fisher Vectors have proven empirically to be the leading representation for a large variety of applications. The Fisher Vector is typically taken as the gradients of the log-likelihood of descriptors, with respect to the parameters of a Gaussian Mixture Model (GMM). Motivated by the assumption that different distributions should be applied for different datasets, we present two other Mixture Models and derive their Expectation-Maximization and Fisher Vector expressions. The first is a Laplacian Mixture Model (LMM), which is based on the Laplacian distribution. The second Mixture Model presented is a Hybrid Gaussian-Laplacian Mixture Model (HGLMM) which is based on a weighted geometric mean of the Gaussian and Laplacian distribution. An interesting property of the Expectation-Maximization algorithm for the latter is that in the maximization step, each dimension in each component is chosen to be either a Gaussian or a Laplacian. Finally, by using the new Fisher Vectors derived from HGLMMs, we achieve state-of-the-art results for both the image annotation and the image search by a sentence tasks.
Usability Evaluation of Learning Management Systems in Sri Lankan Universities
Venue: arXiv cs.HC 2015
Year: 2015

As far as Learning Management System is concerned, it offers an integrated platform for educational materials, distribution and management of learning as well as accessibility by a range of users including teachers, learners and content makers especially for distance learning. Usability evaluation is considered as one approach to assess the efficiency of e-Learning systems. It is used to evaluate how well technology and tools are working for users. There are some factors contributing as major reason why LMS is not used effectively and regularly. Learning Management Systems, as major part of e-Learning systems, can benefit from usability research to evaluate the LMS ease of use and satisfaction among its handlers. Many academic institutions worldwide prefer using their own customized Learning Management Systems; this is the case with Moodle, an open source Learning Management Systems platform designed and operated by most of the universities in Sri Lanka. This paper gives an overview of Learning Management Systems used in Sri Lankan universities, and evaluates its usability using some pre-defined usability standards. In addition it measures the effectiveness of Learning Management System by testing the Learning Management Systems. The findings and result of this study as well as the testing are discussed and presented.
The Loss Surfaces of Multilayer Networks
Venue: arXiv cs.LG 2015
Year: 2015

We study the connection between the highly non-convex loss function of a simple model of the fully-connected feed-forward neural network and the Hamiltonian of the spherical spin-glass model under the assumptions of: i) variable independence, ii) redundancy in network parametrization, and iii) uniformity. These assumptions enable us to explain the complexity of the fully decoupled neural network through the prism of the results from random matrix theory. We show that for large-size decoupled networks the lowest critical values of the random loss function form a layered structure and they are located in a well-defined band lower-bounded by the global minimum. The number of local minima outside that band diminishes exponentially with the size of the network. We empirically verify that the mathematical model exhibits similar behavior as the computer simulations, despite the presence of high dependencies in real networks. We conjecture that both simulated annealing and SGD converge to the band of low critical points, and that all critical points found there are local minima of high quality measured by the test error. This emphasizes a major difference between large- and small-size networks where for the latter poor quality local minima have non-zero probability of being recovered. Finally, we prove that recovering the global minimum becomes harder as the network size increases and that it is in practice irrelevant as global minimum often leads to overfitting.
Canonical Logic Programs are Succinctly Incomparable with Propositional Formulas
Venue: arXiv cs.LO 2015
Year: 2015

\emph{Canonical (logic) programs} (CP) refer to normal logic programs augmented with connective $not\ not$. In this paper we address the question of whether CP are \emph{succinctly incomparable} with \emph{propositional formulas} (PF). Our main result shows that the PARITY problem, which can be polynomially represented in PF but \emph{only} has exponential representations in CP. In other words, PARITY \emph{separates} PF from CP. Simply speaking, this means that exponential size blowup is generally inevitable when translating a set of formulas in PF into an equivalent program in CP (without introducing new variables). Furthermore, since it has been shown by Lifschitz and Razborov that there is also a problem that separates CP from PF (assuming $\mathsf{P}\nsubseteq \mathsf{NC^1/poly}$), it follows that CP and PF are indeed succinctly incomparable. From the view of the theory of computation, the above result may also be considered as the separation of two \emph{models of computation}, i.e., we identify a language in $\mathsf{NC^1/poly}$ which is not in the set of languages computable by polynomial size CP programs.
Still Simpler Way of Introducing Interior-Point method for Linear Programming
Venue: arXiv cs.DS 2015
Year: 2015

Linear Programming is now included in Algorithm undergraduate and postgraduate courses for Computer Science majors. It is possible to teach interior-point methods directly with just minimal knowledge of Algebra and Matrices.
Robust Stability Assessment in the Presence of Load Dynamics Uncertainty
Venue: arXiv cs.SY 2015
Year: 2015

Dynamic response of loads has a significant effect on system stability and directly determines the stability margin of the operating point. Inherent uncertainty and natural variability of load models make the stability assessment especially difficult and may compromise the security of the system. We propose a novel mathematical "robust stability" criterion for the assessment of small-signal stability of operating points. Whenever the criterion is satisfied for a given operating point, it provides mathematical guarantees that the operating point will be stable with respect to small disturbances for any dynamic response of the loads. The criterion can be naturally used for identification of operating regions secure from the occurrence of Hopf bifurcation. Several possible applications of the criterion are discussed, most importantly the concept of Robust Stability Assessment (RSA) that could be integrated in dynamic security assessment packages and used in contingency screening and other planning and operational studies.
Skip-gram Language Modeling Using Sparse Non-negative Matrix Probability Estimation
Venue: arXiv cs.LG 2015
Year: 2015

We present a novel family of language model (LM) estimation techniques named Sparse Non-negative Matrix (SNM) estimation. A first set of experiments empirically evaluating it on the One Billion Word Benchmark shows that SNM $n$-gram LMs perform almost as well as the well-established Kneser-Ney (KN) models. When using skip-gram features the models are able to match the state-of-the-art recurrent neural network (RNN) LMs; combining the two modeling techniques yields the best known result on the benchmark. The computational advantages of SNM over both maximum entropy and RNN LM estimation are probably its main strength, promising an approach that has the same flexibility in combining arbitrary features effectively and yet should scale to very large amounts of data as gracefully as $n$-gram LMs do.
Event Retrieval Using Motion Barcodes
Venue: arXiv cs.CV 2015
Year: 2015

We introduce a simple and effective method for retrieval of videos showing a specific event, even when the videos of that event were captured from significantly different viewpoints. Appearance-based methods fail in such cases, as appearances change with large changes of viewpoints. Our method is based on a pixel-based feature, "motion barcode", which records the existence/non-existence of motion as a function of time. While appearance, motion magnitude, and motion direction can vary greatly between disparate viewpoints, the existence of motion is viewpoint invariant. Based on the motion barcode, a similarity measure is developed for videos of the same event taken from very different viewpoints. This measure is robust to occlusions common under different viewpoints, and can be computed efficiently. Event retrieval is demonstrated using challenging videos from stationary and hand held cameras.
Background Modelling using Octree Color Quantization
Venue: arXiv cs.CV 2015
Year: 2015

By assuming that the most frequently occuring color in a video or a region of a video I propose a new algorithm for detecting foreground objects in a video. The process of detecting the foreground objects is complicated because of the fact that there may be swaying trees, objects of the background being moved around or lighting changes in the video. To deal with such complexities many have come up with solutions which heavily rely on expensive floating point operations. In this paper I used a data structure called Octree which is implemented only using binary operations. Traditionally octrees were used for color quantization but here in this paper I used it as a data structure to store the most frequently occuring colors in a video as well. For each of the starting few video frames, I constructed a Octree using all the colors of that frame. Next I pruned all the trees by removing nodes below a certain height and gave the leaf nodes a color which is dependant on the topological path from that node to its parent. Hence any two leaf nodes in two different octrees with the same topological path from themselves to the root will represent the same color. Next I merged all these individual trees into a single tree retaining only those nodes whose topological path to itself from the root is most common among all the trees. The colors represented by the leaf nodes in the resultant tree will be the most frequently occuring colors in the starting video frames of the video. Hence any color of an incomming frame that is not close to any of the colors represented by the leaf node of the merged tree can be regarded as belonging to a foreground object. As an Octree is constructed using only binary operations, it is very fast compared to other leading algorithms.