OpenRaiser/Intern-Atlas huggingface dataset:
VERIFAI: A Toolkit for the Design and Analysis of Artificial Intelligence-Based Systems
Venue: arXiv cs.AI 2019
Year: 2019

We present VERIFAI, a software toolkit for the formal design and analysis of systems that include artificial intelligence (AI) and machine learning (ML) components. VERIFAI particularly seeks to address challenges with applying formal methods to perception and ML components, including those based on neural networks, and to model and analyze system behavior in the presence of environment uncertainty. We describe the initial version of VERIFAI which centers on simulation guided by formal models and specifications. Several use cases are illustrated with examples, including temporal-logic falsification, model-based systematic fuzz testing, parameter synthesis, counterexample analysis, and data set augmentation.
NAIL: A General Interactive Fiction Agent
Venue: arXiv cs.AI 2019
Year: 2019

Interactive Fiction (IF) games are complex textual decision making problems. This paper introduces NAIL, an autonomous agent for general parser-based IF games. NAIL won the 2018 Text Adventure AI Competition, where it was evaluated on twenty unseen games. This paper describes the architecture, development, and insights underpinning NAIL's performance.
Table2answer: Read the database and answer without SQL
Venue: arXiv cs.CL 2019
Year: 2019

Semantic parsing is the task of mapping natural language to logic form. In question answering, semantic parsing can be used to map the question to logic form and execute the logic form to get the answer. One key problem for semantic parsing is the hard label work. We study this problem in another way: we do not use the logic form any more. Instead we only use the schema and answer info. We think that the logic form step can be injected into the deep model. The reason why we think removing the logic form step is possible is that human can do the task without explicit logic form. We use BERT-based model and do the experiment in the WikiSQL dataset, which is a large natural language to SQL dataset. Our experimental evaluations that show that our model can achieves the baseline results in WikiSQL dataset.
Towards Self-Supervised High Level Sensor Fusion
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we present a framework to control a self-driving car by fusing raw information from RGB images and depth maps. A deep neural network architecture is used for mapping the vision and depth information, respectively, to steering commands. This fusion of information from two sensor sources allows to provide redundancy and fault tolerance in the presence of sensor failures. Even if one of the input sensors fails to produce the correct output, the other functioning sensor would still be able to maneuver the car. Such redundancy is crucial in the critical application of self-driving cars. The experimental results have showed that our method is capable of learning to use the relevant sensor information even when one of the sensors fail without any explicit signal.
WikiLinkGraphs: A Complete, Longitudinal and Multi-Language Dataset of the Wikipedia Link Networks
Venue: arXiv cs.SI 2019
Year: 2019

Wikipedia articles contain multiple links connecting a subject to other pages of the encyclopedia. In Wikipedia parlance, these links are called internal links or wikilinks. We present a complete dataset of the network of internal Wikipedia links for the $9$ largest language editions. The dataset contains yearly snapshots of the network and spans $17$ years, from the creation of Wikipedia in 2001 to March 1st, 2018. While previous work has mostly focused on the complete hyperlink graph which includes also links automatically generated by templates, we parsed each revision of each article to track links appearing in the main text. In this way we obtained a cleaner network, discarding more than half of the links and representing all and only the links intentionally added by editors. We describe in detail how the Wikipedia dumps have been processed and the challenges we have encountered, including the need to handle special pages such as redirects, i.e., alternative article titles. We present descriptive statistics of several snapshots of this network. Finally, we propose several research opportunities that can be explored using this new dataset.
Envy-freeness up to any item with high Nash welfare: The virtue of donating items
Venue: arXiv cs.GT 2019
Year: 2019

Several fairness concepts have been proposed recently in attempts to approximate envy-freeness in settings with indivisible goods. Among them, the concept of envy-freeness up to any item (EFX) is arguably the closest to envy-freeness. Unfortunately, EFX allocations are not known to exist except in a few special cases. We make significant progress in this direction. We show that for every instance with additive valuations, there is an EFX allocation of a subset of items with a Nash welfare that is at least half of the maximum possible Nash welfare for the original set of items. That is, after donating some items to a charity, one can distribute the remaining items in a fair way with high efficiency. This bound is proved to be best possible. Our proof is constructive and highlights the importance of maximum Nash welfare allocation. Starting with such an allocation, our algorithm decides which items to donate and redistributes the initial bundles to the agents, eventually obtaining an allocation with the claimed efficiency guarantee. The application of our algorithm to large markets, where the valuations of an agent for every item is relatively small, yields EFX with almost optimal Nash welfare. To the best of our knowledge, this is the first use of large market assumptions in the fair division literature. We also show that our algorithm can be modified to compute, in polynomial-time, EFX allocations that approximate optimal Nash welfare within a factor of at most $2ρ$, using a $ρ$-approximate allocation on input instead of the maximum Nash welfare one.
Gaussian Mean Field Regularizes by Limiting Learned Information
Venue: arXiv cs.LG 2019
Year: 2019

Variational inference with a factorized Gaussian posterior estimate is a widely used approach for learning parameters and hidden variables. Empirically, a regularizing effect can be observed that is poorly understood. In this work, we show how mean field inference improves generalization by limiting mutual information between learned parameters and the data through noise. We quantify a maximum capacity when the posterior variance is either fixed or learned and connect it to generalization error, even when the KL-divergence in the objective is rescaled. Our experiments demonstrate that bounding information between parameters and data effectively regularizes neural networks on both supervised and unsupervised tasks.
Manifestation of Image Contrast in Deep Networks
Venue: arXiv cs.CV 2019
Year: 2019

Contrast is subject to dramatic changes across the visual field, depending on the source of light and scene configurations. Hence, the human visual system has evolved to be more sensitive to contrast than absolute luminance. This feature is equally desired for machine vision: the ability to recognise patterns even when aspects of them are transformed due to variation in local and global contrast. In this work, we thoroughly investigate the impact of image contrast on prominent deep convolutional networks, both during the training and testing phase. The results of conducted experiments testify to an evident deterioration in the accuracy of all state-of-the-art networks at low-contrast images. We demonstrate that "contrast-augmentation" is a sufficient condition to endow a network with invariance to contrast. This practice shows no negative side effects, quite the contrary, it might allow a model to refrain from other illuminance related over-fittings. This ability can also be achieved by a short fine-tuning procedure, which opens new lines of investigation on mechanisms involved in two networks whose weights are over 99.9% correlated, yet astonishingly produce utterly different outcomes. Our further analysis suggests that the optimisation algorithm is an influential factor, however with a significantly lower effect; and while the choice of an architecture manifests a negligible impact on this phenomenon, the first layers appear to be more critical.
Multitask Learning for Polyphonic Piano Transcription, a Case Study
Venue: arXiv cs.SD 2019
Year: 2019

Viewing polyphonic piano transcription as a multitask learning problem, where we need to simultaneously predict onsets, intermediate frames and offsets of notes, we investigate the performance impact of additional prediction targets, using a variety of suitable convolutional neural network architectures. We quantify performance differences of additional objectives on the large MAESTRO dataset.
Evaluating Older Users' Experiences with Commercial Dialogue Systems: Implications for Future Design and Development
Venue: arXiv cs.HC 2019
Year: 2019

Understanding the needs of a variety of distinct user groups is vital in designing effective, desirable dialogue systems that will be adopted by the largest possible segment of the population. Despite the increasing popularity of dialogue systems in both mobile and home formats, user studies remain relatively infrequent and often sample a segment of the user population that is not representative of the needs of the potential user population as a whole. This is especially the case for users who may be more reluctant adopters, such as older adults. In this paper we discuss the results of a recent user study performed over a large population of age 50 and over adults in the Midwestern United States that have experience using a variety of commercial dialogue systems. We show the common preferences, use cases, and feature gaps identified by older adult users in interacting with these systems. Based on these results, we propose a new, robust user modeling framework that addresses common issues facing older adult users, which can then be generalized to the wider user population.
Examining Adversarial Learning against Graph-based IoT Malware Detection Systems
Venue: arXiv cs.CR 2019
Year: 2019

The main goal of this study is to investigate the robustness of graph-based Deep Learning (DL) models used for Internet of Things (IoT) malware classification against Adversarial Learning (AL). We designed two approaches to craft adversarial IoT software, including Off-the-Shelf Adversarial Attack (OSAA) methods, using six different AL attack approaches, and Graph Embedding and Augmentation (GEA). The GEA approach aims to preserve the functionality and practicality of the generated adversarial sample through a careful embedding of a benign sample to a malicious one. Our evaluations demonstrate that OSAAs are able to achieve a misclassification rate (MR) of 100%. Moreover, we observed that the GEA approach is able to misclassify all IoT malware samples as benign.
A Novel Data Encryption Algorithm Design and Implementation in Information Security Scope
Venue: arXiv cs.CR 2019
Year: 2019

Today, the protection of information, ensuring of the safety and the recall in lossless in case of need is highly significant and it is seen as a major threat in the field. Information security is possible by hiding the available data, by encrypting, saving, transmitting and sharing. At this point, cryptology subject comes up. Cryptology called as password science includes with the encrypting according to a certain technique of different texts and the transmitting these messages to the recipient in a secure environment. In this study, in information security scope, an original data encryption algorithm was developed. Algorithm developed according to the "Single Characters Relocation" technique is designed. In the creation process of the algorithm, was also utilized from Caesar encryption algorithm, multi-alphabet algorithms and Enigma. The purpose of the study is to store the text written in a safe manner and thus to ensure information security is by deciphering upon request. In the study, an algorithm that is very difficult for its decryption was developed and this is clearly emerging when considering the number used passwords alphabet. This study is expected to contribute to the field of information security.
Compressed Range Minimum Queries
Venue: arXiv cs.DS 2019
Year: 2019

Given a string $S$ of $n$ integers in $[0,σ)$, a range minimum query RMQ$(i, j)$ asks for the index of the smallest integer in $S[i \dots j]$. It is well known that the problem can be solved with a succinct data structure of size $2n + o(n)$ and constant query-time. In this paper we show how to preprocess $S$ into a compressed representation that allows fast range minimum queries. This allows for sublinear size data structures with logarithmic query time. The most natural approach is to use string compression and construct a data structure for answering range minimum queries directly on the compressed string. We investigate this approach in the context of grammar compression. We then consider an alternative approach. Instead of compressing $S$ using string compression, we compress the Cartesian tree of $S$ using tree compression. We show that this approach can be exponentially better than the former, is never worse by more than an $O(σ)$ factor (i.e. for constant alphabets it is never asymptotically worse), and can in fact be worse by an $Ω(σ)$ factor.
A Novel Communication Cost Aware Load Balancing in Content Delivery Networks using Honeybee Algorithm
Venue: arXiv cs.NI 2019
Year: 2019

Modern web services rely on Content Delivery Networks (CDNs) to efficiently deliver contents to end users. In order to minimize the experienced communication cost, it is necessary to send the end user's requests to the nearest servers. However, it is shown that this naive method causes some servers to get overloaded. Similarly, when distributing the requests to avoid overloading, the communication cost increases. This is a well-known trade-off between communication cost and load balancing in CDNs. In this work, by introducing a new meta-heuristic algorithm, we try to optimize this trade-off, that is, to have less-loaded servers at lower experienced communication cost. This trade-off is even better managed when we optimize the way servers update their information of each others' load. The proposed scheme, which is based on Honeybee algorithm, is an implementation of bees algorithm which is known for solving continuous optimization problems. Our proposed version for CDNs is a combination of a request redirecting method and a server information update algorithm. To evaluate the suggested method in a large-scale network, we leveraged our newly developed CDN simulator which takes into account all the important network parameters in the scope of our problem. The simulation results show that our proposed scheme achieves a better trade-off between the communication cost and load balancing in CDNs, compared to previously proposed schemes.
A Tunable Loss Function for Binary Classification
Venue: arXiv cs.LG 2019
Year: 2019

We present $α$-loss, $α\in [1,\infty]$, a tunable loss function for binary classification that bridges log-loss ($α=1$) and $0$-$1$ loss ($α= \infty$). We prove that $α$-loss has an equivalent margin-based form and is classification-calibrated, two desirable properties for a good surrogate loss function for the ideal yet intractable $0$-$1$ loss. For logistic regression-based classification, we provide an upper bound on the difference between the empirical and expected risk at the empirical risk minimizers for $α$-loss by exploiting its Lipschitzianity along with recent results on the landscape features of empirical risk functions. Finally, we show that $α$-loss with $α= 2$ performs better than log-loss on MNIST for logistic regression.
Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
Venue: arXiv cs.LG 2019
Year: 2019

Many modern neural network architectures are trained in an overparameterized regime where the parameters of the model exceed the size of the training dataset. Sufficiently overparameterized neural network architectures in principle have the capacity to fit any set of labels including random noise. However, given the highly nonconvex nature of the training landscape it is not clear what level and kind of overparameterization is required for first order methods to converge to a global optima that perfectly interpolate any labels. A number of recent theoretical works have shown that for very wide neural networks where the number of hidden units is polynomially large in the size of the training data gradient descent starting from a random initialization does indeed converge to a global optima. However, in practice much more moderate levels of overparameterization seems to be sufficient and in many cases overparameterized models seem to perfectly interpolate the training data as soon as the number of parameters exceed the size of the training data by a constant factor. Thus there is a huge gap between the existing theoretical literature and practical experiments. In this paper we take a step towards closing this gap. Focusing on shallow neural nets and smooth activations, we show that (stochastic) gradient descent when initialized at random converges at a geometric rate to a nearby global optima as soon as the square-root of the number of network parameters exceeds the size of the training data. Our results also benefit from a fast convergence rate and continue to hold for non-differentiable activations such as Rectified Linear Units (ReLUs).
The Complexity of Making the Gradient Small in Stochastic Convex Optimization
Venue: arXiv cs.LG 2019
Year: 2019

We give nearly matching upper and lower bounds on the oracle complexity of finding $ε$-stationary points ($\| \nabla F(x) \| \leqε$) in stochastic convex optimization. We jointly analyze the oracle complexity in both the local stochastic oracle model and the global oracle (or, statistical learning) model. This allows us to decompose the complexity of finding near-stationary points into optimization complexity and sample complexity, and reveals some surprising differences between the complexity of stochastic optimization versus learning. Notably, we show that in the global oracle/statistical learning model, only logarithmic dependence on smoothness is required to find a near-stationary point, whereas polynomial dependence on smoothness is necessary in the local stochastic oracle model. In other words, the separation in complexity between the two models can be exponential, and that the folklore understanding that smoothness is required to find stationary points is only weakly true for statistical learning. Our upper bounds are based on extensions of a recent "recursive regularization" technique proposed by Allen-Zhu (2018). We show how to extend the technique to achieve near-optimal rates, and in particular show how to leverage the extra information available in the global oracle model. Our algorithm for the global model can be implemented efficiently through finite sum methods, and suggests an interesting new computational-statistical tradeoff.
Privacy-Utility Trade-off of Linear Regression under Random Projections and Additive Noise
Venue: arXiv cs.LG 2019
Year: 2019

Data privacy is an important concern in machine learning, and is fundamentally at odds with the task of training useful learning models, which typically require the acquisition of large amounts of private user data. One possible way of fulfilling the machine learning task while preserving user privacy is to train the model on a transformed, noisy version of the data, which does not reveal the data itself directly to the training procedure. In this work, we analyze the privacy-utility trade-off of two such schemes for the problem of linear regression: additive noise, and random projections. In contrast to previous work, we consider a recently proposed notion of differential privacy that is based on conditional mutual information (MI-DP), which is stronger than the conventional $(ε, δ)$-differential privacy, and use relative objective error as the utility metric. We find that projecting the data to a lower-dimensional subspace before adding noise attains a better trade-off in general. We also make a connection between privacy problem and (non-coherent) SIMO, which has been extensively studied in wireless communication, and use tools from there for the analysis. We present numerical results demonstrating the performance of the schemes.
Adapting Quality Assurance to Adaptive Systems: The Scenario Coevolution Paradigm
Venue: arXiv cs.SE 2019
Year: 2019

From formal and practical analysis, we identify new challenges that self-adaptive systems pose to the process of quality assurance. When tackling these, the effort spent on various tasks in the process of software engineering is naturally re-distributed. We claim that all steps related to testing need to become self-adaptive to match the capabilities of the self-adaptive system-under-test. Otherwise, the adaptive system's behavior might elude traditional variants of quality assurance. We thus propose the paradigm of scenario coevolution, which describes a pool of test cases and other constraints on system behavior that evolves in parallel to the (in part autonomous) development of behavior in the system-under-test. Scenario coevolution offers a simple structure for the organization of adaptive testing that allows for both human-controlled and autonomous intervention, supporting software engineering for adaptive systems on a procedural as well as technical level.
Towards a Better Indicator for Cache Timing Channels
Venue: arXiv cs.CR 2019
Year: 2019

Recent studies highlighting the vulnerability of computer architecture to information leakage attacks have been a cause of significant concern. Among the various classes of microarchitectural attacks, cache timing channels are especially worrisome since they have the potential to compromise users' private data at high bit rates. Prior works have demonstrated the use of cache miss patterns to detect these attacks. We find that cache miss traces can be easily spoofed and thus they may not be able to identify smarter adversaries. In this work, we show that \emph{cache occupancy}, which records the number of cache blocks owned by a specific process, can be leveraged as a stronger indicator for the presence of cache timing channels. We observe that the modulation of cache access latency in timing channels can be recognized through analyzing pairwise cache occupancy patterns. Our experimental results show that cache occupancy patterns cannot be easily obfuscated even by advanced adversaries that successfully evade cache miss-based detection.
Mesh: Compacting Memory Management for C/C++ Applications
Venue: arXiv cs.PL 2019
Year: 2019

Programs written in C/C++ can suffer from serious memory fragmentation, leading to low utilization of memory, degraded performance, and application failure due to memory exhaustion. This paper introduces Mesh, a plug-in replacement for malloc that, for the first time, eliminates fragmentation in unmodified C/C++ applications. Mesh combines novel randomized algorithms with widely-supported virtual memory operations to provably reduce fragmentation, breaking the classical Robson bounds with high probability. Mesh generally matches the runtime performance of state-of-the-art memory allocators while reducing memory consumption; in particular, it reduces the memory of consumption of Firefox by 16% and Redis by 39%.