OpenRaiser/Intern-Atlas huggingface dataset:
Targeted display advertising: the case of preferential attachment
Venue: arXiv cs.LG 2020
Year: 2020

An average adult is exposed to hundreds of digital advertisements daily (https://www.mediadynamicsinc.com/uploads/files/PR092214-Note-only-150-Ads-2mk.pdf), making the digital advertisement industry a classic example of a big-data-driven platform. As such, the ad-tech industry relies on historical engagement logs (clicks or purchases) to identify potentially interested users for the advertisement campaign of a partner (a seller who wants to target users for its products). The number of advertisements that are shown for a partner, and hence the historical campaign data available for a partner depends upon the budget constraints of the partner. Thus, enough data can be collected for the high-budget partners to make accurate predictions, while this is not the case with the low-budget partners. This skewed distribution of the data leads to "preferential attachment" of the targeted display advertising platforms towards the high-budget partners. In this paper, we develop "domain-adaptation" approaches to address the challenge of predicting interested users for the partners with insufficient data, i.e., the tail partners. Specifically, we develop simple yet effective approaches that leverage the similarity among the partners to transfer information from the partners with sufficient data to cold-start partners, i.e., partners without any campaign data. Our approaches readily adapt to the new campaign data by incremental fine-tuning, and hence work at varying points of a campaign, and not just the cold-start. We present an experimental analysis on the historical logs of a major display advertising platform (https://www.criteo.com/). Specifically, we evaluate our approaches across 149 partners, at varying points of their campaigns. Experimental results show that the proposed approaches outperform the other "domain-adaptation" approaches at different time points of the campaigns.
Data augmentation with Mobius transformations
Venue: arXiv cs.CV 2020
Year: 2020

Data augmentation has led to substantial improvements in the performance and generalization of deep models, and remain a highly adaptable method to evolving model architectures and varying amounts of data---in particular, extremely scarce amounts of available training data. In this paper, we present a novel method of applying Mobius transformations to augment input images during training. Mobius transformations are bijective conformal maps that generalize image translation to operate over complex inversion in pixel space. As a result, Mobius transformations can operate on the sample level and preserve data labels. We show that the inclusion of Mobius transformations during training enables improved generalization over prior sample-level data augmentation techniques such as cutout and standard crop-and-flip transformations, most notably in low data regimes.
Multilevel Acyclic Hypergraph Partitioning
Venue: arXiv cs.DS 2020
Year: 2020

A directed acyclic hypergraph is a generalized concept of a directed acyclic graph, where each hyperedge can contain an arbitrary number of tails and heads. Directed hypergraphs can be used to model data flow and execution dependencies in streaming applications. Thus, hypergraph partitioning algorithms can be used to obtain efficient parallelizations for multiprocessor architectures. However, an acyclicity constraint on the partition is necessary when mapping streaming applications to embedded multiprocessors due to resource restrictions on this type of hardware. The acyclic hypergraph partitioning problem is to partition the hypernodes of a directed acyclic hypergraph into a given number of blocks of roughly equal size such that the corresponding quotient graph is acyclic while minimizing an objective function on the partition. Here, we contribute the first n-level algorithm for the acyclic hypergraph partitioning problem. Our focus is on acyclic hypergraphs where hyperedges can have one head and arbitrary many tails. Based on this, we engineer a memetic algorithm to further reduce communication cost, as well as to improve scheduling makespan on embedded multiprocessor architectures. Experiments indicate that our algorithm outperforms previous algorithms that focus on the directed acyclic graph case which have previously been employed in the application domain. Moreover, our experiments indicate that using the directed hypergraph model for this type of application yields a significantly smaller makespan.
Learning Whole-body Motor Skills for Humanoids
Venue: arXiv cs.RO 2020
Year: 2020

This paper presents a hierarchical framework for Deep Reinforcement Learning that acquires motor skills for a variety of push recovery and balancing behaviors, i.e., ankle, hip, foot tilting, and stepping strategies. The policy is trained in a physics simulator with realistic setting of robot model and low-level impedance control that are easy to transfer the learned skills to real robots. The advantage over traditional methods is the integration of high-level planner and feedback control all in one single coherent policy network, which is generic for learning versatile balancing and recovery motions against unknown perturbations at arbitrary locations (e.g., legs, torso). Furthermore, the proposed framework allows the policy to be learned quickly by many state-of-the-art learning algorithms. By comparing our learned results to studies of preprogrammed, special-purpose controllers in the literature, self-learned skills are comparable in terms of disturbance rejection but with additional advantages of producing a wide range of adaptive, versatile and robust behaviors.
autoNLP: NLP Feature Recommendations for Text Analytics Applications
Venue: arXiv cs.CL 2020
Year: 2020

While designing machine learning based text analytics applications, often, NLP data scientists manually determine which NLP features to use based upon their knowledge and experience with related problems. This results in increased efforts during feature engineering process and renders automated reuse of features across semantically related applications inherently difficult. In this paper, we argue for standardization in feature specification by outlining structure of a language for specifying NLP features and present an approach for their reuse across applications to increase likelihood of identifying optimal features.
The Bloom Tree
Venue: arXiv cs.DS 2020
Year: 2020

We introduce a data structure that allows for efficient (probabilistic) presence proofs and non-probabilistic absence proofs in a bandwidth efficient and secure way. The Bloom tree combines the idea of Bloom filters with that of Merkle trees. Bloom filters are used to verify the presence, or absence of elements in a set. In the case of the Bloom tree, we are interested to verify and transmit the presence, or absence of an element in a secure and bandwidth efficient way to another party. Instead of sending the whole Bloom filter to check for the presence, or absence of an element, the Bloom tree achieves efficient verification by using a compact Merkle multiproof.
Storyboard: Optimizing Precomputed Summaries for Aggregation
Venue: arXiv cs.DB 2020
Year: 2020

An emerging class of data systems partition their data and precompute approximate summaries (i.e., sketches and samples) for each segment to reduce query costs. They can then aggregate and combine the segment summaries to estimate results without scanning the raw data. However, given limited storage space each summary introduces approximation errors that affect query accuracy. For instance, systems that use existing mergeable summaries cannot reduce query error below the error of an individual precomputed summary. We introduce Storyboard, a query system that optimizes item frequency and quantile summaries for accuracy when aggregating over multiple segments. Compared to conventional mergeable summaries, Storyboard leverages additional memory available for summary construction and aggregation to derive a more precise combined result. This reduces error by up to 25x over interval aggregations and 4.4x over data cube aggregations on industrial datasets compared to standard summarization methods, with provable worst-case error guarantees.
Attacking Optical Character Recognition (OCR) Systems with Adversarial Watermarks
Venue: arXiv cs.CV 2020
Year: 2020

Optical character recognition (OCR) is widely applied in real applications serving as a key preprocessing tool. The adoption of deep neural network (DNN) in OCR results in the vulnerability against adversarial examples which are crafted to mislead the output of the threat model. Different from vanilla colorful images, images of printed text have clear backgrounds usually. However, adversarial examples generated by most of the existing adversarial attacks are unnatural and pollute the background severely. To address this issue, we propose a watermark attack method to produce natural distortion that is in the disguise of watermarks and evade human eyes' detection. Experimental results show that watermark attacks can yield a set of natural adversarial examples attached with watermarks and attain similar attack performance to the state-of-the-art methods in different attack scenarios.
A Constraint Driven Solution Model for Discrete Domains with a Case Study of Exam Timetabling Problems
Venue: arXiv cs.NE 2020
Year: 2020

Many science and engineering applications require finding solutions to planning and optimization problems by satisfying a set of constraints. These constraint problems (CPs) are typically NP-complete and can be formalized as constraint satisfaction problems (CSPs) or constraint optimization problems (COPs). Evolutionary algorithms (EAs) are good solvers for optimization problems ubiquitous in various problem domains, however traditional operators for EAs are 'blind' to constraints or generally use problem dependent objective functions; as they do not exploit information from the constraints in search for solutions. A variation of EA, Intelligent constraint handling evolutionary algorithm (ICHEA), has been demonstrated to be a versatile constraints-guided EA for continuous constrained problems in our earlier works in (Sharma and Sharma, 2012) where it extracts information from constraints and exploits it in the evolutionary search to make the search more efficient. In this paper ICHEA has been demonstrated to solve benchmark exam timetabling problems, a classic COP. The presented approach demonstrates competitive results with other state-of-the-art approaches in EAs in terms of quality of solutions. ICHEA first uses its inter-marriage crossover operator to satisfy all the given constraints incrementally and then uses combination of traditional and enhanced operators to optimize the solution. Generally CPs solved by EAs are problem dependent penalty based fitness functions. We also proposed a generic preference based solution model that does not require a problem dependent fitness function, however currently it only works for mutually exclusive constraints.
OoDAnalyzer: Interactive Analysis of Out-of-Distribution Samples
Venue: arXiv cs.HC 2020
Year: 2020

One major cause of performance degradation in predictive models is that the test samples are not well covered by the training data. Such not well-represented samples are called OoD samples. In this paper, we propose OoDAnalyzer, a visual analysis approach for interactively identifying OoD samples and explaining them in context. Our approach integrates an ensemble OoD detection method and a grid-based visualization. The detection method is improved from deep ensembles by combining more features with algorithms in the same family. To better analyze and understand the OoD samples in context, we have developed a novel kNN-based grid layout algorithm motivated by Hall's theorem. The algorithm approximates the optimal layout and has $O(kN^2)$ time complexity, faster than the grid layout algorithm with overall best performance but $O(N^3)$ time complexity. Quantitative evaluation and case studies were performed on several datasets to demonstrate the effectiveness and usefulness of OoDAnalyzer.
A Time-Frequency Perspective on Audio Watermarking
Venue: arXiv cs.MM 2020
Year: 2020

Existing audio watermarking methods usually treat the host audio signals of a function of time or frequency individually, while considering them in the joint time-frequency (TF) domain has received less attention. This paper proposes an audio watermarking framework from the perspective of TF analysis. The proposed framework treats the host audio signal in the 2-dimensional (2D) TF plane, and selects a series of patches within the 2D TF image. These patches correspond to the TF clusters with minimum averaged energy, and are used to form the feature vectors for watermark embedding. Classical spread spectrum embedding schemes are incorporated in the framework. The feature patches that carry the watermarks only occupy a few TF regions of the host audio signal, thus leading to improved imperceptibility property. In addition, since the feature patches contain a neighborhood area of TF representation of audio samples, the correlations among the samples within a single patch could be exploited for improved robustness against a series of processing attacks. Extensive experiments are carried out to illustrate the effectiveness of the proposed system, as compared to its counterpart systems. The aim of this work is to shed some light on the notion of audio watermarking in TF feature domain, which may potentially lead us to more robust watermarking solutions against malicious attacks.
A General Coreset-Based Approach to Diversity Maximization under Matroid Constraints
Venue: arXiv cs.DC 2020
Year: 2020

Diversity maximization is a fundamental problem in web search and data mining. For a given dataset $S$ of $n$ elements, the problem requires to determine a subset of $S$ containing $k\ll n$ "representatives" which minimize some diversity function expressed in terms of pairwise distances, where distance models dissimilarity. An important variant of the problem prescribes that the solution satisfy an additional orthogonal requirement, which can be specified as a matroid constraint (i.e., a feasible solution must be an independent set of size $k$ of a given matroid). While unconstrained diversity maximization admits efficient coreset-based strategies for several diversity functions, known approaches dealing with the additional matroid constraint apply only to one diversity function (sum of distances), and are based on an expensive, inherently sequential, local search over the entire input dataset. We devise the first coreset-based algorithms for diversity maximization under matroid constraints for various diversity functions, together with efficient sequential, MapReduce and Streaming implementations. Technically, our algorithms rely on the construction of a small coreset, that is, a subset of $S$ containing a feasible solution which is no more than a factor $1-ε$ away from the optimal solution for $S$. While our algorithms are fully general, for the partition and transversal matroids, if $ε$ is a constant in $(0,1)$ and $S$ has bounded doubling dimension, the coreset size is independent of $n$ and it is small enough to afford the execution of a slow sequential algorithm to extract a final, accurate, solution in reasonable time. Extensive experiments show that our algorithms are accurate, fast and scalable, and therefore they are capable of dealing with the large input instances typical of the big data scenario.
On a scalable entropic breaching of the overfitting barrier in machine learning
Venue: arXiv cs.LG 2020
Year: 2020

Overfitting and treatment of "small data" are among the most challenging problems in the machine learning (ML), when a relatively small data statistics size $T$ is not enough to provide a robust ML fit for a relatively large data feature dimension $D$. Deploying a massively-parallel ML analysis of generic classification problems for different $D$ and $T$, existence of statistically-significant linear overfitting barriers for common ML methods is demonstrated. For example, these results reveal that for a robust classification of bioinformatics-motivated generic problems with the Long Short-Term Memory deep learning classifier (LSTM) one needs in a best case a statistics $T$ that is at least 13.8 times larger then the feature dimension $D$. It is shown that this overfitting barrier can be breached at a $10^{-12}$ fraction of the computational cost by means of the entropy-optimal Scalable Probabilistic Approximations algorithm (eSPA), performing a joint solution of the entropy-optimal Bayesian network inference and feature space segmentation problems. Application of eSPA to experimental single cell RNA sequencing data exhibits a 30-fold classification performance boost when compared to standard bioinformatics tools - and a 7-fold boost when compared to the deep learning LSTM classifier.
Correction of Chromatic Aberration from a Single Image Using Keypoints
Venue: arXiv cs.GR 2020
Year: 2020

In this paper, we propose a method to correct for chromatic aberration in a single photograph. Our method replicates what a user would do in a photo editing program to account for this defect. We find matching keypoints in each colour channel then align them as a user would.
Eliminating Search Intent Bias in Learning to Rank
Venue: arXiv cs.LG 2020
Year: 2020

Click-through data has proven to be a valuable resource for improving search-ranking quality. Search engines can easily collect click data, but biases introduced in the data can make it difficult to use the data effectively. In order to measure the effects of biases, many click models have been proposed in the literature. However, none of the models can explain the observation that users with different search intent (e.g., informational, navigational, etc.) have different click behaviors. In this paper, we study how differences in user search intent can influence click activities and determined that there exists a bias between user search intent and the relevance of the document relevance. Based on this observation, we propose a search intent bias hypothesis that can be applied to most existing click models to improve their ability to learn unbiased relevance. Experimental results demonstrate that after adopting the search intent hypothesis, click models can better interpret user clicks and substantially improve retrieval performance.
Invariant Hopping Attacks on Block Ciphers
Venue: arXiv cs.CR 2020
Year: 2020

Block ciphers are in widespread use since the 1970s. Their iterated structure is prone to numerous round invariant attacks for example in Linear Cryptanalysis (LC). The next step is to look at non-linear polynomial invariants cf. Eurocrypt'95. Until recently, researchers have found extremely few such attacks, with some impossibility results. Eventually recent papers show how to construct polynomial invariant attacks for block ciphers, however many such results were of degree 2. In this paper we propose a new incremental methodology for constructing high degree polynomial invariant attacks on block ciphers. A trivial attack on one cipher setup will be transposed to show the existence of a more advanced attack on a stronger cipher in several steps. The key tool is the manipulation of the roots of the so called Fundamental Equation. Examples are constructed with an old historical block cipher T-310.
Conservative Exploration in Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

While learning in an unknown Markov Decision Process (MDP), an agent should trade off exploration to discover new information about the MDP, and exploitation of the current knowledge to maximize the reward. Although the agent will eventually learn a good or optimal policy, there is no guarantee on the quality of the intermediate policies. This lack of control is undesired in real-world applications where a minimum requirement is that the executed policies are guaranteed to perform at least as well as an existing baseline. In this paper, we introduce the notion of conservative exploration for average reward and finite horizon problems. We present two optimistic algorithms that guarantee (w.h.p.) that the conservative constraint is never violated during learning. We derive regret bounds showing that being conservative does not hinder the learning ability of these algorithms.
Privacy-Preserving Image Classification in the Local Setting
Venue: arXiv cs.LG 2020
Year: 2020

Image data has been greatly produced by individuals and commercial vendors in the daily life, and it has been used across various domains, like advertising, medical and traffic analysis. Recently, image data also appears to be greatly important in social utility, like emergency response. However, the privacy concern becomes the biggest obstacle that prevents further exploration of image data, due to that the image could reveal sensitive information, like the personal identity and locations. The recent developed Local Differential Privacy (LDP) brings us a promising solution, which allows the data owners to randomly perturb their input to provide the plausible deniability of the data before releasing. In this paper, we consider a two-party image classification problem, in which data owners hold the image and the untrustworthy data user would like to fit a machine learning model with these images as input. To protect the image privacy, we propose to locally perturb the image representation before revealing to the data user. Subsequently, we analyze how the perturbation satisfies ε-LDP and affect the data utility regarding count-based and distance-based machine learning algorithm, and propose a supervised image feature extractor, DCAConv, which produces an image representation with scalable domain size. Our experiments show that DCAConv could maintain a high data utility while preserving the privacy regarding multiple image benchmark datasets.
Robust URLLC Packet Scheduling of OFDM Systems
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we consider the power minimization problem of joint physical resource block (PRB) assignment and transmit power allocation under specified delay and reliability requirements for ultra-reliable and low-latency communication (URLLC) in downlink cellular orthogonal frequency-division multiple-access (OFDMA) system. To be more practical, only the imperfect channel state information (CSI) is assumed to be available at the base station (BS). The formulated problem is a combinatorial and mixed-integer nonconvex problem and is difficult to tackle. Through techniques of slack variables introduction, the first-order Taylor approximation and reweighted $\ell_1$-norm, we approximate it by a convex problem and the successive convex approximation (SCA) based iterative algorithm is proposed to yield sub-optimal solutions. Numerical results provide some insights into the impact of channel estimation error, user number, the allowable maximum delay and packet error probability on the required system sum power.