OpenRaiser/Intern-Atlas huggingface dataset:
Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms [Full Version]
Venue: arXiv cs.DS 2016
Year: 2016

The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of N jobs on M distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into M "subjobs" and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem.
Orthogonal Random Features
Venue: arXiv cs.LG 2016
Year: 2016

We present an intriguing discovery related to Random Fourier Features: in Gaussian kernel approximation, replacing the random Gaussian matrix by a properly scaled random orthogonal matrix significantly decreases kernel approximation error. We call this technique Orthogonal Random Features (ORF), and provide theoretical and empirical justification for this behavior. Motivated by this discovery, we further propose Structured Orthogonal Random Features (SORF), which uses a class of structured discrete orthogonal matrices to speed up the computation. The method reduces the time cost from $\mathcal{O}(d^2)$ to $\mathcal{O}(d \log d)$, where $d$ is the data dimensionality, with almost no compromise in kernel approximation quality compared to ORF. Experiments on several datasets verify the effectiveness of ORF and SORF over the existing methods. We also provide discussions on using the same type of discrete orthogonal structure for a broader range of applications.
A nonlinear state-space approach to hysteresis identification
Venue: arXiv cs.SY 2016
Year: 2016

Most studies tackling hysteresis identification in the technical literature follow white-box approaches, i.e. they rely on the assumption that measured data obey a specific hysteretic model. Such an assumption may be a hard requirement to handle in real applications, since hysteresis is a highly individualistic nonlinear behaviour. The present paper adopts a black-box approach based on nonlinear state-space models to identify hysteresis dynamics. This approach is shown to provide a general framework to hysteresis identification, featuring flexibility and parsimony of representation. Nonlinear model terms are constructed as a multivariate polynomial in the state variables, and parameter estimation is performed by minimising weighted least-squares cost functions. Technical issues, including the selection of the model order and the polynomial degree, are discussed, and model validation is achieved in both broadband and sine conditions. The study is carried out numerically by exploiting synthetic data generated via the Bouc-Wen equations.
Practical Privacy in WDM Networks with All-Optical Layered Encryption
Venue: arXiv cs.CR 2016
Year: 2016

Privacy in form of anonymous communication could be comparably both faster and harder to break in optical routers than in today's anonymous IP networks based on The Onion Routing (Tor). Implementing the practical privacy alloptically,however, is not straightforward, as it requires key generation in each anonymization node to avoid distribution of long keys, and layered encryption, both at the optical line rate. Due to the unavailability of cryptographically strong optical key generation and encryption components, not only a layered encryption is a challenge, but an optical encryption in general. In this paper, we address the challenges of optical anonymous networking for the first time from the system's perspective, and discuss options for practical implementation of all-optical layered encryption. To this end, we propose an optical anonymization component realized with the state-of-the-art optical XOR logic and optical Linear Feedback Shift Registers (oLFSRs). Given that LFSR alone is known for its weak cryptographic security due to its linear properties, we propose an implementation with parallel oLFSRs and analyze the resulting computational security. The results show that proposed optical anonymization component is promising as it can be practically realized to provide a high computational security against deanonymization (privacy) attack.
Sentiment Analysis of Twitter Data for Predicting Stock Market Movements
Venue: arXiv cs.IR 2016
Year: 2016

Predicting stock market movements is a well-known problem of interest. Now-a-days social media is perfectly representing the public sentiment and opinion about current events. Especially, twitter has attracted a lot of attention from researchers for studying the public sentiments. Stock market prediction on the basis of public sentiments expressed on twitter has been an intriguing field of research. Previous studies have concluded that the aggregate public mood collected from twitter may well be correlated with Dow Jones Industrial Average Index (DJIA). The thesis of this work is to observe how well the changes in stock prices of a company, the rises and falls, are correlated with the public opinions being expressed in tweets about that company. Understanding author's opinion from a piece of text is the objective of sentiment analysis. The present paper have employed two different textual representations, Word2vec and N-gram, for analyzing the public sentiments in tweets. In this paper, we have applied sentiment analysis and supervised machine learning principles to the tweets extracted from twitter and analyze the correlation between stock market movements of a company and sentiments in tweets. In an elaborate way, positive news and tweets in social media about a company would definitely encourage people to invest in the stocks of that company and as a result the stock price of that company would increase. At the end of the paper, it is shown that a strong correlation exists between the rise and falls in stock prices with the public sentiments in tweets.
Text Segmentation using Named Entity Recognition and Co-reference Resolution in English and Greek Texts
Venue: arXiv cs.CL 2016
Year: 2016

In this paper we examine the benefit of performing named entity recognition (NER) and co-reference resolution to an English and a Greek corpus used for text segmentation. The aim here is to examine whether the combination of text segmentation and information extraction can be beneficial for the identification of the various topics that appear in a document. NER was performed manually in the English corpus and was compared with the output produced by publicly available annotation tools while, an already existing tool was used for the Greek corpus. Produced annotations from both corpora were manually corrected and enriched to cover four types of named entities. Co-reference resolution i.e., substitution of every reference of the same instance with the same named entity identifier was subsequently performed. The evaluation, using five text segmentation algorithms for the English corpus and four for the Greek corpus leads to the conclusion that, the benefit highly depends on the segment's topic, the number of named entity instances appearing in it, as well as the segment's length.
A Tale of Two Turing Machines
Venue: arXiv cs.LO 2016
Year: 2016

Two Turing Machines may be able to answer questions about each other that they cannot answer about themselves.
Software Architecture Decision-Making Practices and Challenges: An Industrial Case Study
Venue: arXiv cs.SE 2016
Year: 2016

Software architecture decision-making is critical to the success of a software system as software architecture sets the structure of the system, determines its qualities, and has far-reaching consequences throughout the system life cycle. The complex nature of the software development context and the importance of the problem has led the research community to develop several techniques, tools, and processes to assist software architects in making better decisions. Despite these effort, the adoption of such systematic approaches appears to be quite limited in practice. In addition, the practitioners are also facing new challenges as different software development methods suggest different approaches for architecture design. In this paper, we study the current software architecture decision-making practices in the industry using a case study conducted among professional software architects in three different companies in Europe. As a result, we identified different software architecture decision-making practices followed by the software teams as well as their reasons for following them, the challenges associated with them, and the possible improvements from the software architects' point of view. Based on that, we recognized that improving software architecture knowledge management can address most of the identified challenges and would result in better software architecture decision-making.
Supporting novel biomedical research via multilayer collaboration networks
Venue: arXiv cs.SI 2016
Year: 2016

The value of research containing novel combinations of molecules can be seen in many innovative and award-winning research programs. Despite calls to use innovative approaches to address common diseases, an increasing majority of research funding goes toward "safe" incremental research. Counteracting this trend by nurturing novel and potentially transformative scientific research is challenging, it must be supported in competition with established research programs. Therefore, we propose a tool that helps to resolve the tension between safe but fundable research vs. high-risk but potentially transformational research. It does this by identifying hidden overlapping interest around novel molecular research topics. Specifically, it identifies paths of molecular interactions that connect research topics and hypotheses that would not typically be associated, as the basis for scientific collaboration. Because these collaborations are related to the scientists' present trajectory, they are low risk and can be initiated rapidly. Unlike most incremental steps, these collaborations have the potential for leaps in understanding, as they reposition research for novel disease applications. We demonstrate the use of this tool to identify scientists who could contribute to understanding the cellular role of genes with novel associations with Alzheimer's disease, which have not been thoroughly characterized, in part due to the funding emphasis on established research.
Novel Grid Topology Estimation Technique Exploiting PLC Modems
Venue: arXiv cs.OH 2016
Year: 2016

A fundamental requirement to develop routing strategies in power line networks is the knowledge of the network topology, which might not be complete. In this work, we present a novel method to derive the topology of a distribution network that exploits the capability of Power Line Communication modems to measure the network admittance, and we report the most significant results.
Asynchronous Stochastic Block Coordinate Descent with Variance Reduction
Venue: arXiv cs.LG 2016
Year: 2016

Asynchronous parallel implementations for stochastic optimization have received huge successes in theory and practice recently. Asynchronous implementations with lock-free are more efficient than the one with writing or reading lock. In this paper, we focus on a composite objective function consisting of a smooth convex function $f$ and a block separable convex function, which widely exists in machine learning and computer vision. We propose an asynchronous stochastic block coordinate descent algorithm with the accelerated technology of variance reduction (AsySBCDVR), which are with lock-free in the implementation and analysis. AsySBCDVR is particularly important because it can scale well with the sample size and dimension simultaneously. We prove that AsySBCDVR achieves a linear convergence rate when the function $f$ is with the optimal strong convexity property, and a sublinear rate when $f$ is with the general convexity. More importantly, a near-linear speedup on a parallel system with shared memory can be obtained.
KeystoneML: Optimizing Pipelines for Large-Scale Advanced Analytics
Venue: arXiv cs.LG 2016
Year: 2016

Modern advanced analytics applications make use of machine learning techniques and contain multiple steps of domain-specific and general-purpose processing with high resource requirements. We present KeystoneML, a system that captures and optimizes the end-to-end large-scale machine learning applications for high-throughput training in a distributed environment with a high-level API. This approach offers increased ease of use and higher performance over existing systems for large scale learning. We demonstrate the effectiveness of KeystoneML in achieving high quality statistical accuracy and scalable training using real world datasets in several domains. By optimizing execution KeystoneML achieves up to 15x training throughput over unoptimized execution on a real image classification application.
Building Energy Load Forecasting using Deep Neural Networks
Venue: arXiv cs.NE 2016
Year: 2016

Ensuring sustainability demands more efficient energy management with minimized energy wastage. Therefore, the power grid of the future should provide an unprecedented level of flexibility in energy management. To that end, intelligent decision making requires accurate predictions of future energy demand/load, both at aggregate and individual site level. Thus, energy load forecasting have received increased attention in the recent past, however has proven to be a difficult problem. This paper presents a novel energy load forecasting methodology based on Deep Neural Networks, specifically Long Short Term Memory (LSTM) algorithms. The presented work investigates two variants of the LSTM: 1) standard LSTM and 2) LSTM-based Sequence to Sequence (S2S) architecture. Both methods were implemented on a benchmark data set of electricity consumption data from one residential customer. Both architectures where trained and tested on one hour and one-minute time-step resolution datasets. Experimental results showed that the standard LSTM failed at one-minute resolution data while performing well in one-hour resolution data. It was shown that S2S architecture performed well on both datasets. Further, it was shown that the presented methods produced comparable results with the other deep learning methods for energy forecasting in literature.
A Theoretical Study of The Relationship Between Whole An ELM Network and Its Subnetworks
Venue: arXiv cs.LG 2016
Year: 2016

A biological neural network is constituted by numerous subnetworks and modules with different functionalities. For an artificial neural network, the relationship between a network and its subnetworks is also important and useful for both theoretical and algorithmic research, i.e. it can be exploited to develop incremental network training algorithm or parallel network training algorithm. In this paper we explore the relationship between an ELM neural network and its subnetworks. To the best of our knowledge, we are the first to prove a theorem that shows an ELM neural network can be scattered into subnetworks and its optimal solution can be constructed recursively by the optimal solutions of these subnetworks. Based on the theorem we also present two algorithms to train a large ELM neural network efficiently: one is a parallel network training algorithm and the other is an incremental network training algorithm. The experimental results demonstrate the usefulness of the theorem and the validity of the developed algorithms.
An Experimental Study on the Learning Outcome of Teaching Elementary Level Children using Lego Mindstorms EV3 Robotics Education Kit
Venue: arXiv cs.CY 2016
Year: 2016

Skills like computational thinking, problem solving, handling complexity, team-work and project management are essential for future careers and needs to be taught to students at the elementary level itself. Computer programming knowledge and skills, experiencing technology and conducting science and engineering experiments are also important for students at elementary level. However, teaching such skills effectively through active learning can be challenging for educators. In this paper, we present our approach and experiences in teaching such skills to several elementary level children using Lego Mindstorms EV3 robotics education kit. We describe our learning environment consisting of lessons, worksheets, hands-on activities and assessment. We taught students how to design, construct and program robots using components such as motors, sensors, wheels, axles, beams, connectors and gears. Students also gained knowledge on basic programming constructs such as control flow, loops, branches and conditions using a visual programming environment. We carefully observed how students performed various tasks and solved problems. We present experimental results which demonstrates that our teaching methodology consisting of both the course content and pedagogy was effective in imparting the desired skills and knowledge to elementary level children. The students also participated in a competitive World Robot Olympiad India event and qualified during the regional round which is an evidence of the effectiveness of the approach.
Compressed Learning: A Deep Neural Network Approach
Venue: arXiv cs.CV 2016
Year: 2016

Compressed Learning (CL) is a joint signal processing and machine learning framework for inference from a signal, using a small number of measurements obtained by linear projections of the signal. In this paper we present an end-to-end deep learning approach for CL, in which a network composed of fully-connected layers followed by convolutional layers perform the linear sensing and non-linear inference stages. During the training phase, the sensing matrix and the non-linear inference operator are jointly optimized, and the proposed approach outperforms state-of-the-art for the task of image classification. For example, at a sensing rate of 1% (only 8 measurements of 28 X 28 pixels images), the classification error for the MNIST handwritten digits dataset is 6.46% compared to 41.06% with state-of-the-art.
Compact Deep Convolutional Neural Networks With Coarse Pruning
Venue: arXiv cs.LG 2016
Year: 2016

The learning capability of a neural network improves with increasing depth at higher computational costs. Wider layers with dense kernel connectivity patterns furhter increase this cost and may hinder real-time inference. We propose feature map and kernel level pruning for reducing the computational complexity of a deep convolutional neural network. Pruning feature maps reduces the width of a layer and hence does not need any sparse representation. Further, kernel pruning converts the dense connectivity pattern into a sparse one. Due to coarse nature, these pruning granularities can be exploited by GPUs and VLSI based implementations. We propose a simple and generic strategy to choose the least adversarial pruning masks for both granularities. The pruned networks are retrained which compensates the loss in accuracy. We obtain the best pruning ratios when we prune a network with both granularities. Experiments with the CIFAR-10 dataset show that more than 85% sparsity can be induced in the convolution layers with less than 1% increase in the missclassification rate of the baseline network.
Deep Model Compression: Distilling Knowledge from Noisy Teachers
Venue: arXiv cs.LG 2016
Year: 2016

The remarkable successes of deep learning models across various applications have resulted in the design of deeper networks that can solve complex problems. However, the increasing depth of such models also results in a higher storage and runtime complexity, which restricts the deployability of such very deep models on mobile and portable devices, which have limited storage and battery capacity. While many methods have been proposed for deep model compression in recent years, almost all of them have focused on reducing storage complexity. In this work, we extend the teacher-student framework for deep model compression, since it has the potential to address runtime and train time complexity too. We propose a simple methodology to include a noise-based regularizer while training the student from the teacher, which provides a healthy improvement in the performance of the student network. Our experiments on the CIFAR-10, SVHN and MNIST datasets show promising improvement, with the best performance on the CIFAR-10 dataset. We also conduct a comprehensive empirical evaluation of the proposed method under related settings on the CIFAR-10 dataset to show the promise of the proposed approach.
On the Control of Affine Systems with Safety Constraints: Relaxed In-Block Controllability
Venue: arXiv cs.SY 2016
Year: 2016

We consider affine systems defined on polytopes and study the cases where the systems are not in-block controllable with respect to the given polytopes. That are the cases in which we cannot fully control the affine systems within the interior of a given polytope, representing the intersection of given safety constraints. Instead, we introduce in this paper the notion of relaxed in-block controllability (RIBC), which can be useful for the cases where one can distinguish between soft and hard safety constraints. In particular, we study whether all the states in the interior of a given polytope, formed by the intersection of soft safety constraints, are mutually accessible through the interior of a given bigger polytope, formed by the intersection of hard safety constraints, by applying uniformly bounded control inputs. By exploring the geometry of the problem, we provide necessary conditions for RIBC. We then show when these conditions are also sufficient. Several illustrative examples are also given to clarify the main results.
Represent, Aggregate, and Constrain: A Novel Architecture for Machine Reading from Noisy Sources
Venue: arXiv cs.CL 2016
Year: 2016

In order to extract event information from text, a machine reading model must learn to accurately read and interpret the ways in which that information is expressed. But it must also, as the human reader must, aggregate numerous individual value hypotheses into a single coherent global analysis, applying global constraints which reflect prior knowledge of the domain. In this work we focus on the task of extracting plane crash event information from clusters of related news articles whose labels are derived via distant supervision. Unlike previous machine reading work, we assume that while most target values will occur frequently in most clusters, they may also be missing or incorrect. We introduce a novel neural architecture to explicitly model the noisy nature of the data and to deal with these aforementioned learning issues. Our models are trained end-to-end and achieve an improvement of more than 12.1 F$_1$ over previous work, despite using far less linguistic annotation. We apply factor graph constraints to promote more coherent event analyses, with belief propagation inference formulated within the transitions of a recurrent neural network. We show this technique additionally improves maximum F$_1$ by up to 2.8 points, resulting in a relative improvement of $50\%$ over the previous state-of-the-art.