OpenRaiser/Intern-Atlas huggingface dataset:
Unregularized Online Learning Algorithms with General Loss Functions
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we consider unregularized online learning algorithms in a Reproducing Kernel Hilbert Spaces (RKHS). Firstly, we derive explicit convergence rates of the unregularized online learning algorithms for classification associated with a general gamma-activating loss (see Definition 1 in the paper). Our results extend and refine the results in Ying and Pontil (2008) for the least-square loss and the recent result in Bach and Moulines (2011) for the loss function with a Lipschitz-continuous gradient. Moreover, we establish a very general condition on the step sizes which guarantees the convergence of the last iterate of such algorithms. Secondly, we establish, for the first time, the convergence of the unregularized pairwise learning algorithm with a general loss function and derive explicit rates under the assumption of polynomially decaying step sizes. Concrete examples are used to illustrate our main results. The main techniques are tools from convex analysis, refined inequalities of Gaussian averages, and an induction approach.
Space-Constrained Massive MIMO: Hitting the Wall of Favorable Propagation
Venue: arXiv cs.IT 2015
Year: 2015

The recent development of the massive multiple-input multiple-output (MIMO) paradigm, has been extensively based on the pursuit of favorable propagation: in the asymptotic limit, the channel vectors become nearly orthogonal and inter-user interference tends to zero [1]. In this context, previous studies have considered fixed inter-antenna distance, which implies an increasing array aperture as the number of elements increases. Here, we focus on a practical, space-constrained topology, where an increase in the number of antenna elements in a fixed total space imposes an inversely proportional decrease in the inter-antenna distance. Our analysis shows that, contrary to existing studies, inter-user interference does not vanish in the massive MIMO regime, thereby creating a saturation effect on the achievable rate.
Some new insights into information decomposition in complex systems based on common information
Venue: arXiv cs.IT 2015
Year: 2015

We take a closer look at the structure of bivariate dependency induced by a pair of predictor random variables $(X_1, X_2)$ trying to synergistically, redundantly or uniquely encode a target random variable $Y$. We evaluate a recently proposed measure of redundancy based on the Gács-Körner common information (Griffith et al., Entropy 2014) and show that the measure, in spite of its elegance is degenerate for most non-trivial distributions. We show that Wyner's common information also fails to capture the notion of redundancy as it violates an intuitive monotonically non-increasing property. We identify a set of conditions when a conditional version of Gács and Körner's common information is an ideal measure of unique information. Finally, we show how the notions of approximately sufficient statistics and conditional information bottleneck can be used to quantify unique information.
No Small Linear Program Approximates Vertex Cover within a Factor $2 - ε$
Venue: arXiv cs.CC 2015
Year: 2015

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to approximate within a factor $2 - ε$, assuming the Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best inapproximability result for the problem is due to Dinur and Safra (2002): vertex cover is NP-hard to approximate within a factor 1.3606. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates vertex cover within a factor $2-ε$ has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as SDP relaxations) that approximate the independent set problem within any constant factor have super-polynomial size.
Constructing elastic distinguishability metrics for location privacy
Venue: arXiv cs.CR 2015
Year: 2015

With the increasing popularity of hand-held devices, location-based applications and services have access to accurate and real-time location information, raising serious privacy concerns for their users. The recently introduced notion of geo-indistinguishability tries to address this problem by adapting the well-known concept of differential privacy to the area of location-based systems. Although geo-indistinguishability presents various appealing aspects, it has the problem of treating space in a uniform way, imposing the addition of the same amount of noise everywhere on the map. In this paper we propose a novel elastic distinguishability metric that warps the geometrical distance, capturing the different degrees of density of each area. As a consequence, the obtained mechanism adapts the level of noise while achieving the same degree of privacy everywhere. We also show how such an elastic metric can easily incorporate the concept of a "geographic fence" that is commonly employed to protect the highly recurrent locations of a user, such as his home or work. We perform an extensive evaluation of our technique by building an elastic metric for Paris' wide metropolitan area, using semantic information from the OpenStreetMap database. We compare the resulting mechanism against the Planar Laplace mechanism satisfying standard geo-indistinguishability, using two real-world datasets from the Gowalla and Brightkite location-based social networks. The results show that the elastic mechanism adapts well to the semantics of each area, adjusting the noise as we move outside the city center, hence offering better overall privacy.
On the Impact of Antenna Topologies for Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Approximate expressions for the spatial correlation of cylindrical and uniform rectangular arrays (URA) are derived using measured distributions of angles of departure (AOD) for both the azimuth and zenith domains. We examine massive multiple-input-multiple-output (MIMO) convergence properties of the correlated channels by considering a number of convergence metrics. The per-user matched filter (MF) signal-to-interference-plus-noise ratio (SINR) performance and convergence rate, to respective limiting values, of the two antenna topologies is also explored.
Sparsity Aware Normalized Least Mean p-power Algorithms with Correntropy Induced Metric Penalty
Venue: arXiv cs.IT 2015
Year: 2015

For identifying the non-Gaussian impulsive noise systems, normalized LMP (NLMP) has been proposed to combat impulsive-inducing instability. However, the standard algorithm is without considering the inherent sparse structure distribution of unknown system. To exploit sparsity as well as to mitigate the impulsive noise, this paper proposes a sparse NLMP algorithm, i.e., Correntropy Induced Metric (CIM) constraint based NLMP (CIMNLMP). Based on the first proposed algorithm, moreover, we propose an improved CIM constraint variable regularized NLMP(CIMVRNLMP) algorithm by utilizing variable regularized parameter(VRP) selection method which can further adjust convergence speed and steady-state error. Numerical simulations are given to confirm the proposed algorithms.
Robustly Leveraging Prior Knowledge in Text Classification
Venue: arXiv cs.CL 2015
Year: 2015

Prior knowledge has been shown very useful to address many natural language processing tasks. Many approaches have been proposed to formalise a variety of knowledge, however, whether the proposed approach is robust or sensitive to the knowledge supplied to the model has rarely been discussed. In this paper, we propose three regularization terms on top of generalized expectation criteria, and conduct extensive experiments to justify the robustness of the proposed methods. Experimental results demonstrate that our proposed methods obtain remarkable improvements and are much more robust than baselines.
Connectionist-Symbolic Machine Intelligence using Cellular Automata based Reservoir-Hyperdimensional Computing
Venue: arXiv cs.ET 2015
Year: 2015

We introduce a novel framework of reservoir computing, that is capable of both connectionist machine intelligence and symbolic computation. Cellular automaton is used as the reservoir of dynamical systems. Input is randomly projected onto the initial conditions of automaton cells and nonlinear computation is performed on the input via application of a rule in the automaton for a period of time. The evolution of the automaton creates a space-time volume of the automaton state space, and it is used as the reservoir. The proposed framework is capable of long short-term memory and it requires orders of magnitude less computation compared to Echo State Networks. We prove that cellular automaton reservoir holds a distributed representation of attribute statistics, which provides a more effective computation than local representation. It is possible to estimate the kernel for linear cellular automata via metric learning, that enables a much more efficient distance computation in support vector machine framework. Also, binary reservoir feature vectors can be combined using Boolean operations as in hyperdimensional computing, paving a direct way for concept building and symbolic processing.
Stabilizer quantum codes from $J$-affine variety codes and a new Steane-like enlargement
Venue: arXiv cs.IT 2015
Year: 2015

New stabilizer codes with parameters better than the ones available in the literature are provided in this work, in particular quantum codes with parameters $[[127,63, \geq 12]]_2$ and $[[63,45, \geq 6]]_4$ that are records. These codes are constructed with a new generalization of the Steane's enlargement procedure and by considering orthogonal subfield-subcodes --with respect to the Euclidean and Hermitian inner product-- of a new family of linear codes, the $J$-affine variety codes.
Normalization based K means Clustering Algorithm
Venue: arXiv cs.LG 2015
Year: 2015

K-means is an effective clustering technique used to separate similar data into groups based on initial centroids of clusters. In this paper, Normalization based K-means clustering algorithm(N-K means) is proposed. Proposed N-K means clustering algorithm applies normalization prior to clustering on the available data as well as the proposed approach calculates initial centroids based on weights. Experimental results prove the betterment of proposed N-K means clustering algorithm over existing K-means clustering algorithm in terms of complexity and overall performance.
Morphological Detector for Multilevel Signals in epsilon-Noise
Venue: arXiv cs.IT 2015
Year: 2015

The novel approach was developed for multilevel signal detection in channels with impulsive non-Gaussian noise. This approach consists of using morphological nonlinear image filtration principles for two dimensional signals. It is a new method of signal demodulation, using three - dimensional image processing algorithms. Successful results of this morphological detector encourage more investigation towards using image processing theory and algorithms for two dimensional signal processing. As can be seen in the example in section IV, this new approach of reusing well developed and extensively developing image processing has significantly improved performance.
Projection onto the capped simplex
Venue: arXiv cs.LG 2015
Year: 2015

We provide a simple and efficient algorithm for computing the Euclidean projection of a point onto the capped simplex---a simplex with an additional uniform bound on each coordinate---together with an elementary proof. Both the MATLAB and C++ implementations of the proposed algorithm can be downloaded at https://eng.ucmerced.edu/people/wwang5.
An algorithm for multiplication of split-octonions
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we introduce efficient algorithm for the multiplication of split-octonions. The direct multiplication of two split-octonions requires 64 real multiplications and 56 real additions. More effective solutions still do not exist. We show how to compute a product of the split-octonions with 28 real multiplications and 92 real additions. During synthesis of the discussed algorithm we use the fact that product of two split-octonions may be represented as vector-matrix product. The matrix that participates in the product calculating has unique structural properties that allow performing its advantageous decomposition. Namely this decomposition leads to significant reducing of the multiplicative complexity of split-octonions multiplication.
Exploring Cultures through Pattern Mining - Practices from Generative Beauty Workshops
Venue: arXiv cs.CY 2015
Year: 2015

This paper presents a method for understanding personal ways of thinking and doing in daily lives among different countries by mining their ways as patterns in a sense of pattern language. Pattern language is a methodology of describing tacit practical knowledge, where each pattern consists of context, problem, and solution. In this paper, patterns mined from the workshops we held in the following three countries: Japan, Korea, and the United States, are analysed. The results demonstrate similarities and reflect characteristics of the patterns of each country. We anticipate that this workshop can be used as a method for better understanding of cultural similarities and features in the light of practical knowledge in daily lives.
A note on the longest common Abelian factor problem
Venue: arXiv cs.DS 2015
Year: 2015

Abelian string matching problems are becoming an object of considerable interest in last years. Very recently, Alatabbi et al. \cite{AILR2015} presented the first solution for the longest common Abelian factor problem for a pair of strings, reaching $O(σn^2)$ time with $O(σn \log n)$ bits of space, where $n$ is the length of the strings and $σ$ is the alphabet size. In this note we show how the time complexity can be preserved while the space is reduced by a factor of $σ$, and then how the time complexity can be improved, if the alphabet is not too small, when superlinear space is allowed.
Gradient Compared Lp-LMS Algorithms for Sparse System Identification
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we propose two novel p-norm penalty least mean square (Lp-LMS) algorithms as supplements of the conventional Lp-LMS algorithm established for sparse adaptive filtering recently. A gradient comparator is employed to selectively apply the zero attractor of p-norm constraint for only those taps that have the same polarity as that of the gradient of the squared instantaneous error, which leads to the new proposed gradient compared p-norm constraint LMS algorithm (LpGC-LMS). We explain that the LpGC-LMS can achieve lower mean square error than the standard Lp-LMS algorithm theoretically and experimentally. To further improve the performance of the filter, the LpNGC-LMS algorithm is derived using a new gradient comparator which takes the sign-smoothed version of the previous one. The performance of the LpNGC-LMS is superior to that of the LpGC-LMS in theory and in simulations. Moreover, these two comparators can be easily applied to other norm constraint LMS algorithms to derive some new approaches for sparse adaptive filtering. The numerical simulation results show that the two proposed algorithms achieve better performance than the standard LMS algorithm and Lp-LMS algorithm in terms of convergence rate and steady-state behavior in sparse system identification settings.
Physical Interpretations of Negative Imaginary Systems Theory
Venue: arXiv cs.SY 2015
Year: 2015

This paper presents some physical interpretations of recent stability results on the feedback interconnection of negative imaginary systems. These interpretations involve spring mass damper systems coupled together by springs or RLC electrical networks coupled together via inductors or capacitors.
p Norm Constraint Leaky LMS Algorithm for Sparse System Identification
Venue: arXiv cs.SY 2015
Year: 2015

This paper proposes a new leaky least mean square (leaky LMS, LLMS) algorithm in which a norm penalty is introduced to force the solution to be sparse in the application of system identification. The leaky LMS algorithm is derived because the performance ofthe standard LMS algorithm deteriorates when the input is highly correlated. However, both ofthem do not take the sparsity information into account to yield better behaviors. As a modification ofthe LLMS algorithm, the proposed algorithm, named Lp-LLMS, incorporates a p norm penalty into the cost function ofthe LLMS to obtain a shrinkage in the weight update equation, which then enhances the performance of the filter in system identification settings, especially when the impulse response is sparse. The simulation results verify that the proposed algorithm improves the performance ofthe filter in sparse system settings in the presence ofnoisy input signals.
Disaggregated and optically interconnected memory: when will it be cost effective?
Venue: arXiv cs.DC 2015
Year: 2015

The "Disaggregated Server" concept has been proposed for datacenters where the same type server resources are aggregated in their respective pools, for example a compute pool, memory pool, network pool, and a storage pool. Each server is constructed dynamically by allocating the right amount of resources from these pools according to the workload's requirements. Modularity, higher packaging and cooling efficiencies, and higher resource utilization are among the suggested benefits. With the emergence of very large datacenters, "clouds" containing tens of thousands of servers, datacenter efficiency has become an important topic. Few computer chip and systems vendors are working on and making frequent announcements on silicon photonics and disaggregated memory systems. In this paper we study the trade-off between cost and performance of building a disaggregated memory system where DRAM modules in the datacenter are pooled, for example in memory-only chassis and racks. The compute pool and the memory pool are interconnected by an optical interconnect to overcome the distance and bandwidth issues of electrical fabrics. We construct a simple cost model that includes the cost of latency, cost of bandwidth and the savings expected from a disaggregated memory system. We then identify the level at which a disaggregated memory system becomes cost competitive with a traditional direct attached memory system. Our analysis shows that a rack-scale disaggregated memory system will have a non-trivial performance penalty, and at the datacenter scale the penalty is impractically high, and the optical interconnect costs are at least a factor of 10 more expensive than where they should be when compared to the traditional direct attached memory systems.
p-norm-like Constraint Leaky LMS Algorithm for Sparse System Identification
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we propose a novel leaky least mean square (leaky LMS, LLMS) algorithm which employs a p-norm-like constraint to force the solution to be sparse in the application of system identification. As an extension of the LMS algorithm which is the most widely-used adaptive filtering technique, the LLMS algorithm has been proposed for decades, due to the deteriorated performance of the standard LMS algorithm with highly correlated input. However, both ofthem do not consider the sparsity information to have better behaviors. As a sparse-aware modification of the LLMS, our proposed Lplike-LLMS algorithm, incorporates a p-norm-like penalty into the cost function of the LLMS to obtain a shrinkage in the weight update, which then enhances the performance in sparse system identification settings. The simulation results show that the proposed algorithm improves the performance of the filter in sparse system settings in the presence of noisy input signals.
Deep Temporal Appearance-Geometry Network for Facial Expression Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Temporal information can provide useful features for recognizing facial expressions. However, to manually design useful features requires a lot of effort. In this paper, to reduce this effort, a deep learning technique which is regarded as a tool to automatically extract useful features from raw data, is adopted. Our deep network is based on two different models. The first deep network extracts temporal geometry features from temporal facial landmark points, while the other deep network extracts temporal appearance features from image sequences . These two models are combined in order to boost the performance of the facial expression recognition. Through several experiments, we showed that the two models cooperate with each other. As a result, we achieved superior performance to other state-of-the-art methods in CK+ and Oulu-CASIA databases. Furthermore, one of the main contributions of this paper is that our deep network catches the facial action points automatically.
Managing Relocation and Delay in Container Terminals with Flexible Service Policies
Venue: arXiv cs.DS 2015
Year: 2015

We introduce a new model and mathematical formulation for planning crane moves in the storage yard of container terminals. Our objective is to develop a tool that captures customer centric elements, especially service time, and helps operators to manage costly relocation moves. Our model incorporates several practical details and provides port operators with expanded capabilities including planning repositioning moves in off-peak hours, controlling wait times of each customer as well as total service time, optimizing the number of relocations and wait time jointly, and optimizing simultaneously the container stacking and retrieval process. We also study a class of flexible service policies which allow for out-of-order retrieval. We show that under such flexible policies, we can decrease the number of relocations and retrieval delays without creating inequities.
Decentralized Recommender Systems
Venue: arXiv cs.IR 2015
Year: 2015

This paper proposes a decentralized recommender system by formulating the popular collaborative filleting (CF) model into a decentralized matrix completion form over a set of users. In such a way, data storages and computations are fully distributed. Each user could exchange limited information with its local neighborhood, and thus it avoids the centralized fusion. Advantages of the proposed system include a protection on user privacy, as well as better scalability and robustness. We compare our proposed algorithm with several state-of-the-art algorithms on the FlickerUserFavor dataset, and demonstrate that the decentralized algorithm can gain a competitive performance to others.
Color Image Classification via Quaternion Principal Component Analysis Network
Venue: arXiv cs.CV 2015
Year: 2015

The Principal Component Analysis Network (PCANet), which is one of the recently proposed deep learning architectures, achieves the state-of-the-art classification accuracy in various databases. However, the performance of PCANet may be degraded when dealing with color images. In this paper, a Quaternion Principal Component Analysis Network (QPCANet), which is an extension of PCANet, is proposed for color images classification. Compared to PCANet, the proposed QPCANet takes into account the spatial distribution information of color images and ensures larger amount of intra-class invariance of color images. Experiments conducted on different color image datasets such as Caltech-101, UC Merced Land Use, Georgia Tech face and CURet have revealed that the proposed QPCANet achieves higher classification accuracy than PCANet.