OpenRaiser/Intern-Atlas huggingface dataset:
Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial
Venue: arXiv cs.NE 2018
Year: 2018

We analyse the performance of well-known evolutionary algorithms (1+1)EA and (1+$λ$)EA in the prior noise model, where in each fitness evaluation the search point is altered before evaluation with probability $p$. We present refined results for the expected optimisation time of the (1+1)EA and the (1+$λ$)EA on the function LeadingOnes, where bits have to be optimised in sequence. Previous work showed that the (1+1)EA on LeadingOnes runs in polynomial expected time if $p = O((\log n)/n^2)$ and needs superpolynomial expected time if $p = ω((\log n)/n)$, leaving a huge gap for which no results were known. We close this gap by showing that the expected optimisation time is $Θ(n^2) \cdot \exp(Θ(\min\{pn^2, n\}))$ for all $p \le 1/2$, allowing for the first time to locate the threshold between polynomial and superpolynomial expected times at $p = Θ((\log n)/n^2)$. Hence the (1+1)EA on LeadingOnes is much more sensitive to noise than previously thought. We also show that offspring populations of size $λ\ge 3.42\log n$ can effectively deal with much higher noise than known before. Finally, we present an example of a rugged landscape where prior noise can help to escape from local optima by blurring the landscape and allowing a hill climber to see the underlying gradient. We prove that in this particular setting noise can have a highly beneficial effect on performance.
A Brief survey on Smart Community and Smart Transportation
Venue: arXiv cs.CY 2018
Year: 2018

World population growing in conjunction with the preference to live in the cities; make the city management a challenging issue. Traditional Cities with their common features will not be able to handle the human needs. As a result, smart city and its beneficial outcomes will attract a lot of attention recently. In fact, Smart city/community that is the field of collecting and processing data from so many different areas while making proper decisions and feeding to all parts of the system will be the future style of the cities. In other words, smart community is a complex big data problem which should combine different fields of research to make a unit environment. This brief survey will deal with all aspects of the smart communities. There will also be explained different categories of the smart communities in addition to their future challenges. In this work we try to introduce some aspects of the smart transportation in more detail.
A high-level operational semantics for hardware weak memory models
Venue: arXiv cs.LO 2018
Year: 2018

Modern processors deploy a variety of weak memory models, which for efficiency reasons may execute instructions in an order different to that specified by the program text. The consequences of instruction reordering can be complex and subtle, and can impact on ensuring correctness. In this paper we build on extensive work elucidating the semantics of assembler-level languages on hardware architectures with weak memory models (specifically TSO, ARM and POWER) and lift the principles to a straightforward operational semantics which allows reasoning at a higher level of abstraction. To this end we introduce a wide-spectrum language that encompasses operations on abstract data types as well as low-level assembler code, define its operational semantics using a novel approach to allowing reordering of instructions, and derive some refinement laws that can be used to explain behaviours of real processors. In this framework memory models are mostly distinguished via a pair-wise static ordering on instruction types that determines when later instructions may be reordered before earlier instructions. In addition, memory models may use different types of storage systems. For instance, non-multicopy atomic systems allow sibling processes to see updates to different variables in different orders. We encode the semantics in the rewriting engine Maude as a model-checking tool, and develop confidence in our framework by validating our semantics against existing sets of \textit{litmus tests} -- small assembler programs -- comparing our results with those observed on hardware and in existing semantics. We also use the tool as a prototype to model check implementations of data structures from the literature against their abstract specifications.
On the Relationship Between Modularity and Stability in Software Packages
Venue: arXiv cs.SE 2018
Year: 2018

Modular and well-written software is an ideal that programmers strive to achieve. However, real-world project constraints limit the amount of reusable and modular code that programmers can produce. Many techniques exist that refactor code automatically using graph-based measurements and increase the quality and modularity of a codebase. While these measures work in the graph domain, their effect on the stability of software has been uncertain. In this work, we provide mathematical proof that modularity measures are indeed in favor of software stability.
Unleashing the Power of Hashtags in Tweet Analytics with Distributed Framework on Apache Storm
Venue: arXiv cs.DC 2018
Year: 2018

Twitter is a popular social network platform where users can interact and post texts of up to 280 characters called tweets. Hashtags, hyperlinked words in tweets, have increasingly become crucial for tweet retrieval and search. Using hashtags for tweet topic classification is a challenging problem because of context dependent among words, slangs, abbreviation and emoticons in a short tweet along with evolving use of hashtags. Since Twitter generates millions of tweets daily, tweet analytics is a fundamental problem of Big data stream that often requires a real-time Distributed processing. This paper proposes a distributed online approach to tweet topic classification with hashtags. Being implemented on Apache Storm, a distributed real time framework, our approach incrementally identifies and updates a set of strong predictors in the Naïve Bayes model for classifying each incoming tweet instance. Preliminary experiments show promising results with up to 97% accuracy and 37% increase in throughput on eight processors.
Rigid Foldability is NP-Hard
Venue: arXiv cs.CG 2018
Year: 2018

In this paper, we show that deciding rigid foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from Partition, and that deciding rigid foldability with optional creases is strongly NP-hard by a reduction from 1-in-3 SAT. Unlike flat foldability of origami or flexibility of other kinematic linkages, whose complexity originates in the complexity of the layer ordering and possible self-intersection of the material, rigid foldability from a planar state is hard even though there is no potential self-intersection. In fact, the complexity comes from the combinatorial behavior of the different possible rigid folding configurations at each vertex. The results underpin the fact that it is harder to fold from an unfolded sheet of paper than to unfold a folded state back to a plane, frequently encountered problem when realizing folding-based systems such as self-folding matter and reconfigurable robots.
Twitter-based traffic information system based on vector representations for words
Venue: arXiv cs.IR 2018
Year: 2018

Recently, researchers have shown an increased interest in harnessing Twitter data for dynamic monitoring of traffic conditions. Bag-of-words representation is a common method in literature for tweet modeling and retrieving traffic information, yet it suffers from the curse of dimensionality and sparsity. To address these issues, our specific objective is to propose a simple and robust framework on the top of word embedding for distinguishing traffic-related tweets against non-traffic-related ones. In our proposed model, a tweet is classified as traffic-related if semantic similarity between its words and a small set of traffic keywords exceeds a threshold value. Semantic similarity between words is captured by means of word-embedding models, which is an unsupervised learning tool. The proposed model is as simple as having only one trainable parameter. The model takes advantage of outstanding merits, which are demonstrated through several evaluation steps. The state-of-the-art test accuracy for our proposed model is 95.9%.
Practical Text Classification With Large Pre-Trained Language Models
Venue: arXiv cs.CL 2018
Year: 2018

Multi-emotion sentiment classification is a natural language processing (NLP) problem with valuable use cases on real-world data. We demonstrate that large-scale unsupervised language modeling combined with finetuning offers a practical solution to this task on difficult datasets, including those with label class imbalance and domain-specific context. By training an attention-based Transformer network (Vaswani et al. 2017) on 40GB of text (Amazon reviews) (McAuley et al. 2015) and fine-tuning on the training set, our model achieves a 0.69 F1 score on the SemEval Task 1:E-c multi-dimensional emotion classification problem (Mohammad et al. 2018), based on the Plutchik wheel of emotions (Plutchik 1979). These results are competitive with state of the art models, including strong F1 scores on difficult (emotion) categories such as Fear (0.73), Disgust (0.77) and Anger (0.78), as well as competitive results on rare categories such as Anticipation (0.42) and Surprise (0.37). Furthermore, we demonstrate our application on a real world text classification task. We create a narrowly collected text dataset of real tweets on several topics, and show that our finetuned model outperforms general purpose commercially available APIs for sentiment and multidimensional emotion classification on this dataset by a significant margin. We also perform a variety of additional studies, investigating properties of deep learning architectures, datasets and algorithms for achieving practical multidimensional sentiment classification. Overall, we find that unsupervised language modeling and finetuning is a simple framework for achieving high quality results on real-world sentiment classification.
Repairability Enhancement of Scalable Systems with Locally Shared Spares
Venue: arXiv cs.AR 2018
Year: 2018

Future systems based on nano-scale devices will provide great potentials for scaling up in system complexity, yet they will be highly susceptible to operational faults. While spare units can be generally used to enhance reliability, they must be shared in a limited way among functional units to ensure low-cost overheads when systems scale up. Furthermore, the efficiency of achieving reliability using spare units heavily depends on the replacement mechanisms of such spares. While global and chained replacement approaches can take advantage of the entire replacement capabilities in the network, they usually impose some sort of disturbance to all the functional units in the system during the repair process, thus are dreadfully expensive in terms of performance overhead for systems with high fault rates. In this paper, we focus on a low-cost, fast, immediate replacement mechanism that can be implemented locally with minimum disturbance to the system. The proposed schemes aim for maintaining the system with high fault rates in such a low-cost, fast repairable status for many faults before invoking the more expensive, yet optimal, approaches. First, we propose an online repair algorithm: as faults occur during the run-time of the system, the proposed algorithm makes a choice of a spare unit (among several candidates), such that the overall impact on system repairability in the future is minimized. Second, we propose a network enhancement approach, which identifies and connects the vulnerable units to the exploitable spares, thus strengthening the entire system at a low cost.
Inferring Remote Channel State Information: Cramér-Rao Lower Bound and Deep Learning Implementation
Venue: arXiv cs.IT 2018
Year: 2018

Channel state information (CSI) is of vital importance in wireless communication systems. Existing CSI acquisition methods usually rely on pilot transmissions, and geographically separated base stations (BSs) with non-correlated CSI need to be assigned with orthogonal pilots which occupy excessive system resources. Our previous work adopts a data-driven deep learning based approach which leverages the CSI at a local BS to infer the CSI remotely, however the relevance of CSI between separated BSs is not specified explicitly. In this paper, we exploit a model-based methodology to derive the Cramér-Rao lower bound (CRLB) of remote CSI inference given the local CSI. Although the model is simplified, the derived CRLB explicitly illustrates the relationship between the inference performance and several key system parameters, e.g., terminal distance and antenna array size. In particular, it shows that by leveraging multiple local BSs, the inference error exhibits a larger power-law decay rate (w.r.t. number of antennas), compared with a single local BS; this explains and validates our findings in evaluating the deep-neural-network-based (DNN-based) CSI inference. We further improve on the DNN-based method by employing dropout and deeper networks, and show an inference performance of approximately $90\%$ accuracy in a realistic scenario with CSI generated by a ray-tracing simulator.
Risk-averse Behavior Planning for Autonomous Driving under Uncertainty
Venue: arXiv cs.AI 2018
Year: 2018

Autonomous vehicles have to navigate the surrounding environment with partial observability of other objects sharing the road. Sources of uncertainty in autonomous vehicle measurements include sensor fusion errors, limited sensor range due to weather or object detection latency, occlusion, and hidden parameters such as other human driver intentions. Behavior planning must consider all sources of uncertainty in deciding future vehicle maneuvers. This paper presents a scalable framework for risk-averse behavior planning under uncertainty by incorporating QMDP, unscented transform, and Monte Carlo tree search (MCTS). It is shown that upper confidence bound (UCB) for expanding the tree results in noisy Q-value estimates by the MCTS and a degraded performance of QMDP. A modification to action selection procedure in MCTS is proposed to achieve robust performance.
Rare Event Detection using Disentangled Representation Learning
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a novel method for rare event detection from an image pair with class-imbalanced datasets. A straightforward approach for event detection tasks is to train a detection network from a large-scale dataset in an end-to-end manner. However, in many applications such as building change detection on satellite images, few positive samples are available for the training. Moreover, scene image pairs contain many trivial events, such as in illumination changes or background motions. These many trivial events and the class imbalance problem lead to false alarms for rare event detection. In order to overcome these difficulties, we propose a novel method to learn disentangled representations from only low-cost negative samples. The proposed method disentangles different aspects in a pair of observations: variant and invariant factors that represent trivial events and image contents, respectively. The effectiveness of the proposed approach is verified by the quantitative evaluations on four change detection datasets, and the qualitative analysis shows that the proposed method can acquire the representations that disentangle rare events from trivial ones.
FaceFeat-GAN: a Two-Stage Approach for Identity-Preserving Face Synthesis
Venue: arXiv cs.CV 2018
Year: 2018

The advance of Generative Adversarial Networks (GANs) enables realistic face image synthesis. However, synthesizing face images that preserve facial identity as well as have high diversity within each identity remains challenging. To address this problem, we present FaceFeat-GAN, a novel generative model that improves both image quality and diversity by using two stages. Unlike existing single-stage models that map random noise to image directly, our two-stage synthesis includes the first stage of diverse feature generation and the second stage of feature-to-image rendering. The competitions between generators and discriminators are carefully designed in both stages with different objective functions. Specially, in the first stage, they compete in the feature domain to synthesize various facial features rather than images. In the second stage, they compete in the image domain to render photo-realistic images that contain high diversity but preserve identity. Extensive experiments show that FaceFeat-GAN generates images that not only retain identity information but also have high diversity and quality, significantly outperforming previous methods.
Online scheduling of jobs with favorite machines
Venue: arXiv cs.DS 2018
Year: 2018

This work introduces a natural variant of the online machine scheduling problem on unrelated machines, which we refer to as the favorite machine model. In this model, each job has a minimum processing time on a certain set of machines, called favorite machines, and some longer processing times on other machines. This type of costs (processing times) arise quite naturally in many practical problems. In the online version, jobs arrive one by one and must be allocated irrevocably upon each arrival without knowing the future jobs. We consider online algorithms for allocating jobs in order to minimize the makespan. We obtain tight bounds on the competitive ratio of the greedy algorithm and characterize the optimal competitive ratio for the favorite machine model. Our bounds generalize the previous results of the greedy algorithm and the optimal algorithm for the unrelated machines and the identical machines. We also study a further restriction of the model, called the symmetric favorite machine model, where the machines are partitioned equally into two groups and each job has one of the groups as favorite machines. We obtain a 2.675-competitive algorithm for this case, and the best possible algorithm for the two machines case.
Automatic salt deposits segmentation: A deep learning approach
Venue: arXiv cs.LG 2018
Year: 2018

One of the most important applications of seismic reflection is the hydrocarbon exploration which is closely related to salt deposits analysis. This problem is very important even nowadays due to it's non-linear nature. Taking into account the recent developments in deep learning networks TGS-NOPEC Geophysical Company hosted the Kaggle competition for salt deposits segmentation problem in seismic image data. In this paper, we demonstrate the great performance of several novel deep learning techniques merged into a single neural network which achieved the 27th place (top 1%) in the mentioned competition. Using a U-Net with ResNeXt-50 encoder pre-trained on ImageNet as our base architecture, we implemented Spatial-Channel Squeeze & Excitation, Lovasz loss, CoordConv and Hypercolumn methods. The source code for our solution is made publicly available at https://github.com/K-Mike/Automatic-salt-deposits-segmentation.
Privacy-Preserving Distributed Deep Learning for Clinical Data
Venue: arXiv cs.LG 2018
Year: 2018

Deep learning with medical data often requires larger samples sizes than are available at single providers. While data sharing among institutions is desirable to train more accurate and sophisticated models, it can lead to severe privacy concerns due the sensitive nature of the data. This problem has motivated a number of studies on distributed training of neural networks that do not require direct sharing of the training data. However, simple distributed training does not offer provable privacy guarantees to satisfy technical safe standards and may reveal information about the underlying patients. We present a method to train neural networks for clinical data in a distributed fashion under differential privacy. We demonstrate these methods on two datasets that include information from multiple independent sites, the eICU collaborative Research Database and The Cancer Genome Atlas.
Localization and Tracking of an Acoustic Source using a Diagonal Unloading Beamforming and a Kalman Filter
Venue: arXiv cs.SD 2018
Year: 2018

We present the signal processing framework and some results for the IEEE AASP challenge on acoustic source localization and tracking (LOCATA). The system is designed for the direction of arrival (DOA) estimation in single-source scenarios. The proposed framework consists of four main building blocks: pre-processing, voice activity detection (VAD), localization, tracking. The signal pre-processing pipeline includes the short-time Fourier transform (STFT) of the multichannel input captured by the array and the cross power spectral density (CPSD) matrices estimation. The VAD is calculated with a trace-based threshold of the CPSD matrices. The localization is then computed using our recently proposed diagonal unloading (DU) beamforming, which has low-complexity and high resolution. The DOA estimation is finally smoothed with a Kalman filer (KF). Experimental results on the LOCATA development dataset are reported in terms of the root mean square error (RMSE) for a 7-microphone linear array, the 12-microphone pseudo-spherical array integrated in a prototype head for a humanoid robot, and the 32-microphone spherical array.
Towards generative adversarial networks as a new paradigm for radiology education
Venue: arXiv cs.CV 2018
Year: 2018

Medical students and radiology trainees typically view thousands of images in order to "train their eye" to detect the subtle visual patterns necessary for diagnosis. Nevertheless, infrastructural and legal constraints often make it difficult to access and quickly query an abundance of images with a user-specified feature set. In this paper, we use a conditional generative adversarial network (GAN) to synthesize $1024\times1024$ pixel pelvic radiographs that can be queried with conditioning on fracture status. We demonstrate that the conditional GAN learns features that distinguish fractures from non-fractures by training a convolutional neural network exclusively on images sampled from the GAN and achieving an AUC of $>0.95$ on a held-out set of real images. We conduct additional analysis of the images sampled from the GAN and describe ongoing work to validate educational efficacy.
Optimal Boolean Locality-Sensitive Hashing
Venue: arXiv cs.DM 2018
Year: 2018

For $0 \leq β< α< 1$ the distribution $\mathcal{H}$ over Boolean functions $h \colon \{-1, 1\}^d \to \{-1, 1\}$ that minimizes the expression \begin{equation*} ρ_{α, β} = \frac{\log(1/\Pr_{\substack{h \sim \mathcal{H} \\ (x, y) \text{ $α$-corr.}}}[h(x) = h(y)])}{\log(1/\Pr_{\substack{h \sim \mathcal{H} \\ (x, y) \text{ $β$-corr.}}}[h(x) = h(y)])} \end{equation*} assigns nonzero probability only to members of the set of dictator functions $h(x) = \pm x_i$.