OpenRaiser/Intern-Atlas huggingface dataset:
How Do Classifiers Induce Agents To Invest Effort Strategically?
Venue: arXiv cs.LG 2019
Year: 2019

Algorithms are often used to produce decision-making rules that classify or evaluate individuals. When these individuals have incentives to be classified a certain way, they may behave strategically to influence their outcomes. We develop a model for how strategic agents can invest effort in order to change the outcomes they receive, and we give a tight characterization of when such agents can be incentivized to invest specified forms of effort into improving their outcomes as opposed to "gaming" the classifier. We show that whenever any "reasonable" mechanism can do so, a simple linear mechanism suffices.
Token Sliding on Split Graphs
Venue: arXiv cs.DS 2019
Year: 2019

We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the $c$-Colorable Reconfiguration problem under the same rule, where the constraint is now to maintain the set $c$-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed $c\ge 1$ on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time ($n^{O(c)}$) algorithm for all fixed values of $c$, except $c=1$, for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that $c$-Colorable Reconfiguration is W[2]-hard on split graphs parameterized by $c$ and the length of the solution, as well as a tight ETH-based lower bound for both parameters.
Path Planning of an Autonomous Mobile Robot in a Dynamic Environment using Modified Bat Swarm Optimization
Venue: arXiv cs.RO 2019
Year: 2019

This paper outlines a modification on the Bat Algorithm (BA), a kind of swarm optimization algorithms with for the mobile robot navigation problem in a dynamic environment. The main objectives of this work are to obtain the collision-free, shortest, and safest path between starting point and end point assuming a dynamic environment with moving obstacles. A New modification on the frequency parameter of the standard BA has been proposed in this work, namely, the Modified Frequency Bat Algorithm (MFBA). The path planning problem for the mobile robot in a dynamic environment is carried out using the proposed MFBA. The path planning is achieved in two modes; the first mode is called path generation and is implemented using the MFBA, this mode is enabled when no obstacles near the mobile robot exist. When an obstacle close to the mobile robot is detected, the second mode, i.e., the obstacle avoidance (OA) is initiated. Simulation experiments have been conducted to check the validity and the efficiency of the suggested MFBA based path planning algorithm by comparing its performance with that of the standard BA. The simulation results showed that the MFBA outperforms the standard BA by planning a collision-free path with shorter, safer, and smoother than the path obtained by its BA counterpart.
Object Detection with Deep Learning: A Review
Venue: arXiv cs.CV 2019
Year: 2019

Due to object detection's close relationship with video analysis and image understanding, it has attracted much research attention in recent years. Traditional object detection methods are built on handcrafted features and shallow trainable architectures. Their performance easily stagnates by constructing complex ensembles which combine multiple low-level image features with high-level context from object detectors and scene classifiers. With the rapid development in deep learning, more powerful tools, which are able to learn semantic, high-level, deeper features, are introduced to address the problems existing in traditional architectures. These models behave differently in network architecture, training strategy and optimization function, etc. In this paper, we provide a review on deep learning based object detection frameworks. Our review begins with a brief introduction on the history of deep learning and its representative tool, namely Convolutional Neural Network (CNN). Then we focus on typical generic object detection architectures along with some modifications and useful tricks to improve detection performance further. As distinct specific detection tasks exhibit different characteristics, we also briefly survey several specific tasks, including salient object detection, face detection and pedestrian detection. Experimental analyses are also provided to compare various methods and draw some meaningful conclusions. Finally, several promising directions and tasks are provided to serve as guidelines for future work in both object detection and relevant neural network based learning systems.
Deep Clustering for Unsupervised Learning of Visual Features
Venue: arXiv cs.CV 2019
Year: 2019

Clustering is a class of unsupervised learning methods that has been extensively applied and studied in computer vision. Little work has been done to adapt it to the end-to-end training of visual features on large scale datasets. In this work, we present DeepCluster, a clustering method that jointly learns the parameters of a neural network and the cluster assignments of the resulting features. DeepCluster iteratively groups the features with a standard clustering algorithm, k-means, and uses the subsequent assignments as supervision to update the weights of the network. We apply DeepCluster to the unsupervised training of convolutional neural networks on large datasets like ImageNet and YFCC100M. The resulting model outperforms the current state of the art by a significant margin on all the standard benchmarks.
On the Fundamental Limits of MIMO Massive Multiple Access Channels
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we study the multiple-antenna wireless communication networks, where a large number of devices simultaneously communicate with an access point. The capacity region of multiple-input multiple-output massive multiple access channels (MIMO mMAC) is investigated. While joint typicality decoding is utilized to establish the achievability of capacity region for conventional MAC with fixed number of users, the technique is not directly applicable for MIMO mMAC. Instead, an information-theoretic approach based on Gallager's error exponent analysis is exploited to characterize the \textcolor[rgb]{0,0,0}{finite dimension region} of MIMO mMAC. Theoretical results reveal that the finite dimension region of MIMO mMAC is dominated by sum rate constraint only, and the individual user rate is determined by a specific factor that corresponds to the allocation of sum rate. The rate in conventional MAC is not achievable with massive multiple access, which is due to the fact that successive interference cancellation cannot guarantee an arbitrary small error decoding probability for MIMO mMAC. The results further imply that, asymptotically, the individual user rate is independent of the number of transmit antennas, and channel hardening makes the individual user rate close to that when only statistic knowledge of channel is available at receiver. The finite dimension region of MIMO mMAC is a generalization of the symmetric rate in Chen \emph{et al.} (2017).
Automated Data Slicing for Model Validation:A Big data - AI Integration Approach
Venue: arXiv cs.DB 2019
Year: 2019

As machine learning systems become democratized, it becomes increasingly important to help users easily debug their models. However, current data tools are still primitive when it comes to helping users trace model performance problems all the way to the data. We focus on the particular problem of slicing data to identify subsets of the validation data where the model performs poorly. This is an important problem in model validation because the overall model performance can fail to reflect that of the smaller subsets, and slicing allows users to analyze the model performance on a more granular-level. Unlike general techniques (e.g., clustering) that can find arbitrary slices, our goal is to find interpretable slices (which are easier to take action compared to arbitrary subsets) that are problematic and large. We propose Slice Finder, which is an interactive framework for identifying such slices using statistical techniques. Applications include diagnosing model fairness and fraud detection, where identifying slices that are interpretable to humans is crucial. This research is part of a larger trend of Big data and Artificial Intelligence (AI) integration and opens many opportunities for new research.
The Simplex Geometry of Graphs
Venue: arXiv cs.DM 2019
Year: 2019

Graphs are a central object of study in various scientific fields, such as discrete mathematics, theoretical computer science and network science. These graphs are typically studied using combinatorial, algebraic or probabilistic methods, each of which highlights the properties of graphs in a unique way. Here, we discuss a novel approach to study graphs: the simplex geometry (a simplex is a generalized triangle). This perspective, proposed by Miroslav Fiedler, introduces techniques from (simplex) geometry into the field of graph theory and conversely, via an exact correspondence. We introduce this graph-simplex correspondence, identify a number of basic connections between graph characteristics and simplex properties, and suggest some applications as example.
Information and Energy Transmission with Experimentally-Sampled Harvesting Functions
Venue: arXiv cs.IT 2019
Year: 2019

This paper considers the problem of simultaneous information and energy transmission (SIET), where the energy harvesting function is only known experimentally at sample points, e.g., due to nonlinearities and parameter uncertainties in harvesting circuits. We investigate the performance loss due to this partial knowledge of the harvesting function in terms of transmitted energy and information. In particular, we assume harvesting functions are a subclass of Sobolev space and consider two cases, where experimental samples are either taken noiselessly or in the presence of noise. Using constructive function approximation and regression methods for noiseless and noisy samples respectively, we show that the worst loss in energy transmission vanishes asymptotically as the number of samples increases. Similarly, the worst loss in information rate vanishes in the interior of the energy domain, however, does not always vanish at maximal energy. We further show the same principle applies in multicast settings such as medium access in the Wi-Fi protocol. We also consider the end-to-end source-channel communication problem under source distortion constraint and channel energy requirement, where distortion and harvesting functions both are known only at samples.
Cavity Filling: Pseudo-Feature Generation for Multi-Class Imbalanced Data Problems in Deep Learning
Venue: arXiv cs.LG 2019
Year: 2019

Herein, we generate pseudo-features based on the multivariate probability distributions obtained from the feature maps in layers of trained deep neural networks. Further, we augment the minor-class data based on these generated pseudo-features to overcome the imbalanced data problems. The proposed method, i.e., cavity filling, improves the deep learning capabilities in several problems because all the real-world data are observed to be imbalanced.
Using link and content over time for embedding generation in Dynamic Attributed Networks
Venue: arXiv cs.LG 2019
Year: 2019

In this work, we consider the problem of combining link, content and temporal analysis for community detection and prediction in evolving networks. Such temporal and content-rich networks occur in many real-life settings, such as bibliographic networks and question answering forums. Most of the work in the literature (that uses both content and structure) deals with static snapshots of networks, and they do not reflect the dynamic changes occurring over multiple snapshots. Incorporating dynamic changes in the communities into the analysis can also provide useful insights about the changes in the network such as the migration of authors across communities. In this work, we propose Chimera, a shared factorization model that can simultaneously account for graph links, content, and temporal analysis. This approach works by extracting the latent semantic structure of the network in multidimensional form, but in a way that takes into account the temporal continuity of these embeddings. Such an approach simplifies temporal analysis of the underlying network by using the embedding as a surrogate. A consequence of this simplification is that it is also possible to use this temporal sequence of embeddings to predict future communities. We present experimental results illustrating the effectiveness of the approach.
Defend Deep Neural Networks Against Adversarial Examples via Fixed and Dynamic Quantized Activation Functions
Venue: arXiv cs.LG 2019
Year: 2019

Recent studies have shown that deep neural networks (DNNs) are vulnerable to adversarial attacks. To this end, many defense approaches that attempt to improve the robustness of DNNs have been proposed. In a separate and yet related area, recent works have explored to quantize neural network weights and activation functions into low bit-width to compress model size and reduce computational complexity. In this work, we find that these two different tracks, namely the pursuit of network compactness and robustness, can be merged into one and give rise to networks of both advantages. To the best of our knowledge, this is the first work that uses quantization of activation functions to defend against adversarial examples. We also propose to train robust neural networks by using adaptive quantization techniques for the activation functions. Our proposed Dynamic Quantized Activation (DQA) is verified through a wide range of experiments with the MNIST and CIFAR-10 datasets under different white-box attack methods, including FGSM, PGD, and C & W attacks. Furthermore, Zeroth Order Optimization and substitute model-based black-box attacks are also considered in this work. The experimental results clearly show that the robustness of DNNs could be greatly improved using the proposed DQA.
Synthesis of Successful Actuator Attackers on Supervisors
Venue: arXiv cs.SY 2019
Year: 2019

In this work, we propose and develop a new discrete-event based actuator attack model on the closed-loop system formed by the plant and the supervisor. We assume the actuator attacker partially observes the execution of the closed-loop system and eavesdrops the control commands issued by the supervisor. The attacker can modify each control command on a specified subset of attackable events. The attack principle of the actuator attacker is to remain covert until it can establish a successful attack and lead the attacked closed-loop system into generating certain damaging strings. We present a characterization for the existence of a successful attacker, via a new notion of attackability, and prove the existence of the supremal successful actuator attacker, when both the supervisor and the attacker are normal (that is, unobservable events to the supervisor cannot be disabled by the supervisor and unobservable events to the attacker cannot be attacked by the attacker). Finally, we present an algorithm to synthesize the supremal successful attackers that are represented by Moore automata.
Slowly Synchronizing Automata with Idempotent Letters of Low Rank
Venue: arXiv cs.FL 2019
Year: 2019

We use a semigroup-theoretic construction by Peter Higgins in order to produce, for each even $n$, an $n$-state and 3-letter synchronizing automaton with the following two features: 1) all its input letters act as idempotent selfmaps of rank $\dfrac{n}2$; 2) its reset threshold is asymptotically equal to $\dfrac{n^2}2$. In the revised version a few inaccuracies (spotted by the anonymous referees of the previous version) have been removed and several relevant references have been added.
Automatic Identification of Ineffective Online Student Questions in Computing Education
Venue: arXiv cs.HC 2019
Year: 2019

This Research Full Paper explores automatic identification of ineffective learning questions in the context of large-scale computer science classes. The immediate and accurate identification of ineffective learning questions opens the door to possible automated facilitation on a large scale, such as alerting learners to revise questions and providing adaptive question revision suggestions. To achieve this, 983 questions were collected from a question & answer platform implemented by an introductory programming course over three semesters in a large research university in the Southeastern United States. Questions were firstly manually classified into three hierarchical categories: 1) learning-irrelevant questions, 2) effective learning-relevant questions, 3) ineffective learningrelevant questions. The inter-rater reliability of the manual classification (Cohen's Kappa) was .88. Four different machine learning algorithms were then used to automatically classify the questions, including Naive Bayes Multinomial, Logistic Regression, Support Vector Machines, and Boosted Decision Tree. Both flat and single path strategies were explored, and the most effective algorithms under both strategies were identified and discussed. This study contributes to the automatic determination of learning question quality in computer science, and provides evidence for the feasibility of automated facilitation of online question & answer in large scale computer science classes.
CPuS-IoT : A Cyber-Physical Microservice and IoT-based Framework for Manufacturing Assembly Systems
Venue: arXiv cs.SE 2019
Year: 2019

Today's customers are characterized by individual requirements that lead the manufacturing industry to increased product variety and volume reduction. Manufacturing systems and more specifically assembly systems (ASs) should allow quick adaptation of manufacturing assets so as to respond to the evolving market requirements that lead to mass customization. Meanwhile, the manufacturing era is changing due to the fourth industrial revolution, i.e., Industry 4.0, that will change the traditional manufacturing environment to an IoT-based one. In this context, this paper introduces the concept of cyber-physical microservice in the Manufacturing and the ASs domain and presents the Cyber-Physical microservice and IoT-based (CPuS-IoT) framework. The CPuS-IoT framework exploits the benefits of the microservice architectural style and the IoT technologies, but also utilizes the existing in this domain huge investment based on traditional technologies, to support the life cycle of evolvable ASs in the age of Industry 4.0. It provides a solid basis to capture domain knowledge that is used by a model-driven engineering (MDE) approach to semi-automate the development, evolution and operation of ASs, as well as, to establish a common vocabulary for assembly system experts and IoT ones. The CPuS-IoT approach and framework effectively combines MDE with IoT and the microservice architectural paradigm. A case study for the assembly of an everyday life product is adopted to demonstrate the approach even to non-experts of this domain.
Unsupervised Metric Learning in Presence of Missing Data
Venue: arXiv cs.LG 2019
Year: 2019

For many machine learning tasks, the input data lie on a low-dimensional manifold embedded in a high dimensional space and, because of this high-dimensional structure, most algorithms are inefficient. The typical solution is to reduce the dimension of the input data using standard dimension reduction algorithms such as ISOMAP, LAPLACIAN EIGENMAPS or LLES. This approach, however, does not always work in practice as these algorithms require that we have somewhat ideal data. Unfortunately, most data sets either have missing entries or unacceptably noisy values. That is, real data are far from ideal and we cannot use these algorithms directly. In this paper, we focus on the case when we have missing data. Some techniques, such as matrix completion, can be used to fill in missing data but these methods do not capture the non-linear structure of the manifold. Here, we present a new algorithm MR-MISSING that extends these previous algorithms and can be used to compute low dimensional representation on data sets with missing entries. We demonstrate the effectiveness of our algorithm by running three different experiments. We visually verify the effectiveness of our algorithm on synthetic manifolds, we numerically compare our projections against those computed by first filling in data using nlPCA and mDRUR on the MNIST data set, and we also show that we can do classification on MNIST with missing data. We also provide a theoretical guarantee for MR-MISSING under some simplifying assumptions.
TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Time
Venue: arXiv cs.CR 2019
Year: 2019

Is Android malware classification a solved problem? Published F1 scores of up to 0.99 appear to leave very little room for improvement. In this paper, we argue that results are commonly inflated due to two pervasive sources of experimental bias: "spatial bias" caused by distributions of training and testing data that are not representative of a real-world deployment; and "temporal bias" caused by incorrect time splits of training and testing sets, leading to impossible configurations. We propose a set of space and time constraints for experiment design that eliminates both sources of bias. We introduce a new metric that summarizes the expected robustness of a classifier in a real-world setting, and we present an algorithm to tune its performance. Finally, we demonstrate how this allows us to evaluate mitigation strategies for time decay such as active learning. We have implemented our solutions in TESSERACT, an open source evaluation framework for comparing malware classifiers in a realistic setting. We used TESSERACT to evaluate three Android malware classifiers from the literature on a dataset of 129K applications spanning over three years. Our evaluation confirms that earlier published results are biased, while also revealing counter-intuitive performance and showing that appropriate tuning can lead to significant improvements.