OpenRaiser/Intern-Atlas huggingface dataset:
Fundamental Limits of Blind Deconvolution Part II: Sparsity-Ambiguity Trade-offs
Venue: arXiv cs.IT 2015
Year: 2015

Blind deconvolution is an ubiquitous non-linear inverse problem in applications like wireless communications and image processing. This problem is generally ill-posed since signal identifiability is a key concern, and there have been efforts to use sparse models for regularizing blind deconvolution to promote signal identifiability. Part I of this two-part paper establishes a measure theoretically tight characterization of the ambiguity space for blind deconvolution and unidentifiability of this inverse problem under unconstrained inputs. Part II of this paper analyzes the identifiability of the canonical-sparse blind deconvolution problem and establishes surprisingly strong negative results on the sparsity-ambiguity trade-off scaling laws. Specifically, the ill-posedness of canonical-sparse blind deconvolution is quantified by exemplifying the dimension of the unidentifiable signal sets. An important conclusion of the paper is that canonical sparsity occurring naturally in applications is insufficient and that coding is necessary for signal identifiability in blind deconvolution. The methods developed herein are applied to a second-hop channel estimation problem to show that a family of subspace coded signals (including repetition coding and geometrically decaying signals) are unidentifiable under blind deconvolution.
Scalable Discovery of Time-Series Shapelets
Venue: arXiv cs.LG 2015
Year: 2015

Time-series classification is an important problem for the data mining community due to the wide range of application domains involving time-series data. A recent paradigm, called shapelets, represents patterns that are highly predictive for the target variable. Shapelets are discovered by measuring the prediction accuracy of a set of potential (shapelet) candidates. The candidates typically consist of all the segments of a dataset, therefore, the discovery of shapelets is computationally expensive. This paper proposes a novel method that avoids measuring the prediction accuracy of similar candidates in Euclidean distance space, through an online clustering pruning technique. In addition, our algorithm incorporates a supervised shapelet selection that filters out only those candidates that improve classification accuracy. Empirical evidence on 45 datasets from the UCR collection demonstrate that our method is 3-4 orders of magnitudes faster than the fastest existing shapelet-discovery method, while providing better prediction accuracy.
A Novel Hybrid CNN-AIS Visual Pattern Recognition Engine
Venue: arXiv cs.CV 2015
Year: 2015

Machine learning methods are used today for most recognition problems. Convolutional Neural Networks (CNN) have time and again proved successful for many image processing tasks primarily for their architecture. In this paper we propose to apply CNN to small data sets like for example, personal albums or other similar environs where the size of training dataset is a limitation, within the framework of a proposed hybrid CNN-AIS model. We use Artificial Immune System Principles to enhance small size of training data set. A layer of Clonal Selection is added to the local filtering and max pooling of CNN Architecture. The proposed Architecture is evaluated using the standard MNIST dataset by limiting the data size and also with a small personal data sample belonging to two different classes. Experimental results show that the proposed hybrid CNN-AIS based recognition engine works well when the size of training data is limited in size
Stochastic Texture Difference for Scale-Dependent Data Analysis
Venue: arXiv cs.CV 2015
Year: 2015

This article introduces the Stochastic Texture Difference method for analyzing data at prescribed spatial and value scales. This method relies on constrained random walks around each pixel, describing how nearby image values typically evolve on each side of this pixel. Textures are represented as probability distributions of such random walks, so a texture difference operator is statistically defined as a distance between these distributions in a suitable reproducing kernel Hilbert space. The method is thus not limited to scalar pixel values: any data type for which a kernel is available may be considered, from color triplets and multispectral vector data to strings, graphs, and more. By adjusting the size of the neighborhoods that are compared, the method is implicitly scale-dependent. It is also able to focus on either small changes or large gradients. We demonstrate how it can be used to infer spatial and data value characteristic scales in measured signals and natural images.
An Exploration of Rotating Leadership in a Knowledge Building Community
Venue: arXiv cs.SI 2015
Year: 2015

This study aims to investigate the COINs concept of rotating leadership within a Knowledge Building context. Individual and group level leadership patterns in a grade 4 science class were explored through temporal visualization of betweenness centrality. Results indicate that the student network was relatively decentralized, with almost all students leading the group at different points in time. Rotating leadership appears to be an emergent phenomenon of Knowledge Building, and we suggest that it has the potential to be an indicator of collective cognitive responsibility.
The Kinetic Basis of Morphogenesis
Venue: arXiv cs.FL 2015
Year: 2015

It has been shown recently (Shalygo, 2014) that stationary and dynamic patterns can arise in the proposed one-component model of the analog (continuous state) kinetic automaton, or kinon for short, defined as a reflexive dynamical system with active transport. This paper presents extensions of the model, which increase further its complexity and tunability, and shows that the extended kinon model can produce spatio-temporal patterns pertaining not only to pattern formation but also to morphogenesis in real physical and biological systems. The possible applicability of the model to morphogenetic engineering and swarm robotics is also discussed.
Toward Reverse Engineering of VBA Based Excel Spreadsheet Applications
Venue: arXiv cs.SE 2015
Year: 2015

Modern spreadsheet systems can be used to implement complex spreadsheet applications including data sheets, customized user forms and executable procedures written in a scripting language. These applications are often developed by practitioners that do not follow any software engineering practice and do not produce any design documentation. Thus, spreadsheet applications may be very difficult to be maintained or restructured. In this position paper we present in a nutshell two reverse engineering techniques and a tool that we are currently realizing for the abstraction of conceptual data models and business logic models.
On Using Monolingual Corpora in Neural Machine Translation
Venue: arXiv cs.CL 2015
Year: 2015

Recent work on end-to-end neural network-based architectures for machine translation has shown promising results for En-Fr and En-De translation. Arguably, one of the major factors behind this success has been the availability of high quality parallel corpora. In this work, we investigate how to leverage abundant monolingual corpora for neural machine translation. Compared to a phrase-based and hierarchical baseline, we obtain up to $1.96$ BLEU improvement on the low-resource language pair Turkish-English, and $1.59$ BLEU on the focused domain task of Chinese-English chat messages. While our method was initially targeted toward such tasks with less parallel data, we show that it also extends to high resource languages such as Cs-En and De-En where we obtain an improvement of $0.39$ and $0.47$ BLEU scores over the neural machine translation baselines, respectively.
Accelerating DEM simulations on GPUs by reducing the impact of warp divergences
Venue: arXiv cs.DC 2015
Year: 2015

A way to accelerate DEM calculations on the GPUs is developed. We examined how warp divergences take place in the contact detection and the force calculations taking account of the GPU architecture. Then we showed a strategy to reduce the impact of the warp divergences on the runtime of the DEM force calculations.
Optimal Resource Allocation in Multicast Device-to-Device Communications Underlaying LTE Networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we present a framework for resource allocations for multicast device-to-device (D2D) communications underlaying a cellular network. The objective is to maximize the sum throughput of active cellular users (CUs) and feasible D2D groups in a cell, while meeting a certain signal-to-interferenceplus- noise ratio (SINR) constraint for both the CUs and D2D groups. We formulate the problem of power and channel allocation as a mixed integer nonlinear programming (MINLP) problem where one D2D group can reuse the channels of multiple CUs and the channel of each CU can be reused by multiple D2D groups. Distinct from existing approaches in the literature, our formulation and solution methods provide an effective and flexible means to utilize radio resources in cellular networks and share them with multicast groups without causing harmful interference to each other. A variant of the generalized bender decomposition (GBD) is applied to optimally solve the MINLP problem. A greedy algorithm and a low-complexity heuristic solution are then devised. The performance of all schemes is evaluated through extensive simulations. Numerical results demonstrate that the proposed greedy algorithm can achieve closeto- optimal performance, and the heuristic algorithm provides good performance, though inferior than that of the greedy, with much lower complexity.
Low-Level Features for Image Retrieval Based on Extraction of Directional Binary Patterns and Its Oriented Gradients Histogram
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we present a novel approach for image retrieval based on extraction of low level features using techniques such as Directional Binary Code, Haar Wavelet transform and Histogram of Oriented Gradients. The DBC texture descriptor captures the spatial relationship between any pair of neighbourhood pixels in a local region along a given direction, while Local Binary Patterns descriptor considers the relationship between a given pixel and its surrounding neighbours. Therefore, DBC captures more spatial information than LBP and its variants, also it can extract more edge information than LBP. Hence, we employ DBC technique in order to extract grey level texture feature from each RGB channels individually and computed texture maps are further combined which represents colour texture features of an image. Then, we decomposed the extracted colour texture map and original image using Haar wavelet transform. Finally, we encode the shape and local features of wavelet transformed images using Histogram of Oriented Gradients for content based image retrieval. The performance of proposed method is compared with existing methods on two databases such as Wang's corel image and Caltech 256. The evaluation results show that our approach outperforms the existing methods for image retrieval.
Regularization Parameter Selection Method for Sign LMS with Reweighted L1-Norm Constriant Algorithm
Venue: arXiv cs.IT 2015
Year: 2015

Broadband frequency-selective fading channels usually have the inherent sparse nature. By exploiting the sparsity, adaptive sparse channel estimation (ASCE) algorithms, e.g., least mean square with reweighted L1-norm constraint (LMS-RL1) algorithm, could bring a considerable performance gain under assumption of additive white Gaussian noise (AWGN). In practical scenario of wireless systems, however, channel estimation performance is often deteriorated by unexpected non-Gaussian mixture noises which include AWGN and impulsive noises. To design stable communication systems, sign LMS-RL1 (SLMS-RL1) algorithm is proposed to remove the impulsive noise and to exploit channel sparsity simultaneously. It is well known that regularization parameter (REPA) selection of SLMS-RL1 is a very challenging issue. In the worst case, inappropriate REPA may even result in unexpected instable convergence of SLMS-RL1 algorithm. In this paper, Monte Carlo based selection method is proposed to select suitable REPA so that SLMS-RL1 can achieve two goals: stable convergence as well as usage sparsity information. Simulation results are provided to corroborate our studies.
Android based Portable Hand Sign Recognition System
Venue: arXiv cs.HC 2015
Year: 2015

These days mobile devices like phones or tablets are very common among people of all age. They are connected with network and provide seamless communications through internet or cellular services. These devices can be a big help for the people who are not able to communicate properly and even in emergency conditions. A disabled person who is not able to speak or a person who speak a different language, these devices can be a boon for them as understanding, translating and speaking systems for these people. This chapter discusses a portable android based hand sign recognition system which can be used by disabled people. This chapter shows a part of on-going project. Computer Vision based techniques were used for image analysis and PCA was used after image tokenizer for recognition. This method was tested with webcam results to make system more robust.
Scalable Facility Location for Massive Graphs on Pregel-like Systems
Venue: arXiv cs.DC 2015
Year: 2015

We propose a new scalable algorithm for facility location. Facility location is a classic problem, where the goal is to select a subset of facilities to open, from a set of candidate facilities F , in order to serve a set of clients C. The objective is to minimize the total cost of opening facilities plus the cost of serving each client from the facility it is assigned to. In this work, we are interested in the graph setting, where the cost of serving a client from a facility is represented by the shortest-path distance on the graph. This setting allows to model natural problems arising in the Web and in social media applications. It also allows to leverage the inherent sparsity of such graphs, as the input is much smaller than the full pairwise distances between all vertices. To obtain truly scalable performance, we design a parallel algorithm that operates on clusters of shared-nothing machines. In particular, we target modern Pregel-like architectures, and we implement our algorithm on Apache Giraph. Our solution makes use of a recent result to build sketches for massive graphs, and of a fast parallel algorithm to find maximal independent sets, as building blocks. In so doing, we show how these problems can be solved on a Pregel-like architecture, and we investigate the properties of these algorithms. Extensive experimental results show that our algorithm scales gracefully to graphs with billions of edges, while obtaining values of the objective function that are competitive with a state-of-the-art sequential algorithm.
DGCC:A New Dependency Graph based Concurrency Control Protocol for Multicore Database Systems
Venue: arXiv cs.DB 2015
Year: 2015

Multicore CPUs and large memories are increasingly becoming the norm in modern computer systems. However, current database management systems (DBMSs) are generally ineffective in exploiting the parallelism of such systems. In particular, contention can lead to a dramatic fall in performance. In this paper, we propose a new concurrency control protocol called DGCC (Dependency Graph based Concurrency Control) that separates concurrency control from execution. DGCC builds dependency graphs for batched transactions before executing them. Using these graphs, contentions within the same batch of transactions are resolved before execution. As a result, the execution of the transactions does not need to deal with contention while maintaining full equivalence to that of serialized execution. This better exploits multicore hardware and achieves higher level of parallelism. To facilitate DGCC, we have also proposed a system architecture that does not have certain centralized control components yielding better scalability, as well as supports a more efficient recovery mechanism. Our extensive experimental study shows that DGCC achieves up to four times higher throughput compared to that of state-of-the-art concurrency control protocols for high contention workloads.
Price of Stability in Games of Incomplete Information
Venue: arXiv cs.GT 2015
Year: 2015

We address the question of whether price of stability results (existence of equilibria with low social cost) are robust to incomplete information. We show that this is the case in potential games, if the underlying algorithmic social cost minimization problem admits a constant factor approximation algorithm via strict cost-sharing schemes. Roughly, if the existence of an $α$-approximate equilibrium in the complete information setting was proven via the potential method, then there also exists a $α\cdot β$-approximate Bayes-Nash equilibrium in the incomplete information setting, where $β$ is the approximation factor of the strict-cost sharing scheme algorithm. We apply our approach to Bayesian versions of the archetypal, in the price of stability analysis, network design models and show the existence of $O(\log(n))$-approximate Bayes-Nash equilibria in several games whose complete information counterparts have been well-studied, such as undirected network design games, multi-cast games and covering games.
Exploiting Near Time Forecasting From Social Network To Decongest Traffic
Venue: arXiv cs.MA 2015
Year: 2015

Preventing traffic congestion by forecasting near time traffic flows is an important problem as it leads to effective use of transport resources. Social network provides information about activities of humans and social events. Thus, with the help of social network, we can extract which humans will attend a particular event (in near time) and can estimate flow of traffic based on it. This opens up a wide area of research which poses need to have a framework for traffic management that can capture essential parameters of real-life behaviour and provide a way to iterate upon and evaluate new ideas. In this paper, we present building blocks of a framework and a system to simulate a city with its transport system, humans and their social network. We emphasize on relevant parameters selected and modular design of the framework. Our framework defines metrics to evaluate congestion avoidance strategies. To show utility of the framework, we present experimental studies of few strategies on a public transport system.
Fusing Text and Image for Event Detection in Twitter
Venue: arXiv cs.IR 2015
Year: 2015

In this contribution, we develop an accurate and effective event detection method to detect events from a Twitter stream, which uses visual and textual information to improve the performance of the mining process. The method monitors a Twitter stream to pick up tweets having texts and images and stores them into a database. This is followed by applying a mining algorithm to detect an event. The procedure starts with detecting events based on text only by using the feature of the bag-of-words which is calculated using the term frequency-inverse document frequency (TF-IDF) method. Then it detects the event based on image only by using visual features including histogram of oriented gradients (HOG) descriptors, grey-level cooccurrence matrix (GLCM), and color histogram. K nearest neighbours (Knn) classification is used in the detection. The final decision of the event detection is made based on the reliabilities of text only detection and image only detection. The experiment result showed that the proposed method achieved high accuracy of 0.94, comparing with 0.89 with texts only, and 0.86 with images only.
Sparse Code Formation with Linear Inhibition
Venue: arXiv cs.CV 2015
Year: 2015

Sparse code formation in the primary visual cortex (V1) has been inspiration for many state-of-the-art visual recognition systems. To stimulate this behavior, networks are trained networks under mathematical constraint of sparsity or selectivity. In this paper, the authors exploit another approach which uses lateral interconnections in feature learning networks. However, instead of adding direct lateral interconnections among neurons, we introduce an inhibitory layer placed right after normal encoding layer. This idea overcomes the challenge of computational cost and complexity on lateral networks while preserving crucial objective of sparse code formation. To demonstrate this idea, we use sparse autoencoder as normal encoding layer and apply inhibitory layer. Early experiments in visual recognition show relative improvements over traditional approach on CIFAR-10 dataset. Moreover, simple installment and training process using Hebbian rule allow inhibitory layer to be integrated into existing networks, which enables further analysis in the future.
Spreadsheets for Stream Partitions and Windows
Venue: arXiv cs.SE 2015
Year: 2015

We discuss the suitability of spreadsheet processors as tools for programming streaming systems. We argue that, while spreadsheets can function as powerful models for stream operators, their fundamental boundedness limits their scope of application. We propose two extensions to the spreadsheet model and argue their utility in the context of programming streaming systems.
Fuzzy Mixed Integer Linear Programming for Air Vehicles Operations Optimization
Venue: arXiv cs.AI 2015
Year: 2015

Multiple Air Vehicles (AVs) to prosecute geographically dispersed targets is an important optimization problem. Associated multiple tasks viz., target classification, attack and verification are successively performed on each target. The optimal minimum time performance of these tasks requires cooperation among vehicles such that critical time constraints are satisfied i.e. target must be classified before it can be attacked and AV is sent to target area to verify its destruction after target has been attacked. Here, optimal task scheduling problem from Indian Air Force is formulated as Fuzzy Mixed Integer Linear Programming (FMILP) problem. The solution assigns all tasks to vehicles and performs scheduling in an optimal manner including scheduled staged departure times. Coupled tasks involving time and task order constraints are addressed. When AVs have sufficient endurance, existence of optimal solution is guaranteed. The solution developed can serve as an effective heuristic for different categories of AV optimization problems.