OpenRaiser/Intern-Atlas huggingface dataset:
Deep Prediction of Investor Interest: a Supervised Clustering Approach
Venue: arXiv cs.LG 2021
Year: 2021

We propose a novel deep learning architecture suitable for the prediction of investor interest for a given asset in a given time frame. This architecture performs both investor clustering and modelling at the same time. We first verify its superior performance on a synthetic scenario inspired by real data and then apply it to two real-world databases, a publicly available dataset about the position of investors in Spanish stock market and proprietary data from BNP Paribas Corporate and Institutional Banking.
In Defense of LSTMs for Addressing Multiple Instance Learning Problems
Venue: arXiv cs.CV 2021
Year: 2021

LSTMs have a proven track record in analyzing sequential data. But what about unordered instance bags, as found under a Multiple Instance Learning (MIL) setting? While not often used for this, we show LSTMs excell under this setting too. In addition, we show thatLSTMs are capable of indirectly capturing instance-level information us-ing only bag-level annotations. Thus, they can be used to learn instance-level models in a weakly supervised manner. Our empirical evaluation on both simplified (MNIST) and realistic (Lookbook and Histopathology) datasets shows that LSTMs are competitive with or even surpass state-of-the-art methods specially designed for handling specific MIL problems. Moreover, we show that their performance on instance-level prediction is close to that of fully-supervised methods.
Temporal FiLM: Capturing Long-Range Sequence Dependencies with Feature-Wise Modulations
Venue: arXiv cs.LG 2021
Year: 2021

Learning representations that accurately capture long-range dependencies in sequential inputs -- including text, audio, and genomic data -- is a key problem in deep learning. Feed-forward convolutional models capture only feature interactions within finite receptive fields while recurrent architectures can be slow and difficult to train due to vanishing gradients. Here, we propose Temporal Feature-Wise Linear Modulation (TFiLM) -- a novel architectural component inspired by adaptive batch normalization and its extensions -- that uses a recurrent neural network to alter the activations of a convolutional model. This approach expands the receptive field of convolutional sequence models with minimal computational overhead. Empirically, we find that TFiLM significantly improves the learning speed and accuracy of feed-forward neural networks on a range of generative and discriminative learning tasks, including text classification and audio super-resolution
A Vector Space Approach to Generate Dynamic Keys for Hill Cipher
Venue: arXiv cs.CR 2021
Year: 2021

In this paper, a variant of the Hill cipher is proposed. In the classical Hill cipher, an invertible matrix is used for encryption but the scheme is vulnerable to the known-plaintext attack which can reveal the matrix. In our proposed cryptosystem, each plaintext block is encrypted by a new invertible key matrix that thwarts the known-plaintext attack. To generate the invertible matrices which serve as the dynamic keys we make use of the vector spaces, randomly generated basis and non-singular linear transformation. Resulting cipher is secure against the known-plaintext attack.
I-MAD: Interpretable Malware Detector Using Galaxy Transformer
Venue: arXiv cs.LG 2021
Year: 2021

Malware currently presents a number of serious threats to computer users. Signature-based malware detection methods are limited in detecting new malware samples that are significantly different from known ones. Therefore, machine learning-based methods have been proposed, but there are two challenges these methods face. The first is to model the full semantics behind the assembly code of malware. The second challenge is to provide interpretable results while keeping excellent detection performance. In this paper, we propose an Interpretable MAlware Detector (I-MAD) that outperforms state-of-the-art static malware detection models regarding accuracy with excellent interpretability. To improve the detection performance, I-MAD incorporates a novel network component called the Galaxy Transformer network that can understand assembly code at the basic block, function, and executable levels. It also incorporates our proposed interpretable feed-forward neural network to provide interpretations for its detection results by quantifying the impact of each feature with respect to the prediction. Experiment results show that our model significantly outperforms existing state-of-the-art static malware detection models and presents meaningful interpretations.
6DLS: Modeling Nonplanar Frictional Surface Contacts for Grasping using 6D Limit Surfaces
Venue: arXiv cs.RO 2021
Year: 2021

Robot grasping with deformable gripper jaws results in nonplanar surface contacts if the jaws deform to the nonplanar local geometry of an object. The frictional force and torque that can be transmitted through a nonplanar surface contact are both three-dimensional, resulting in a six-dimensional frictional wrench (6DFW). Applying traditional planar contact models to such contacts leads to over-conservative results as the models do not consider the nonplanar surface geometry and only compute a three-dimensional subset of the 6DFW. To address this issue, we derive the 6DFW for nonplanar surfaces by combining concepts of differential geometry and Coulomb friction. We also propose two 6D limit surface (6DLS) models, generalized from well-known three-dimensional LS (3DLS) models, which describe the friction-motion constraints for a contact. We evaluate the 6DLS models by fitting them to the 6DFW samples obtained from six parametric surfaces and 2,932 meshed contacts from finite element method simulations of 24 rigid objects. We further present an algorithm to predict multicontact grasp success by building a grasp wrench space with the 6DLS model of each contact. To evaluate the algorithm, we collected 1,035 physical grasps of ten 3D-printed objects with a KUKA robot and a deformable parallel-jaw gripper. In our experiments, the algorithm achieves 66.8% precision, a metric inversely related to false positive predictions, and 76.9% recall, a metric inversely related to false negative predictions. The 6DLS models increase recall by up to 26.1% over 3DLS models with similar precision.
Span-based Joint Entity and Relation Extraction with Transformer Pre-training
Venue: arXiv cs.CL 2021
Year: 2021

We introduce SpERT, an attention model for span-based joint entity and relation extraction. Our key contribution is a light-weight reasoning on BERT embeddings, which features entity recognition and filtering, as well as relation classification with a localized, marker-free context representation. The model is trained using strong within-sentence negative samples, which are efficiently extracted in a single BERT pass. These aspects facilitate a search over all spans in the sentence. In ablation studies, we demonstrate the benefits of pre-training, strong negative sampling and localized context. Our model outperforms prior work by up to 2.6% F1 score on several datasets for joint entity and relation extraction.
Preprocessing and Cutting Planes with Conflict Graphs
Venue: arXiv cs.DS 2021
Year: 2021

This paper addresses the development of conflict graph-based algorithms and data structures into the COIN-OR Branch-and-Cut (CBC) solver, including: $(i)$ an efficient infrastructure for the construction and manipulation of conflict graphs; $(ii)$ a preprocessing routine based on a clique strengthening scheme that can both reduce the number of constraints and produce stronger formulations; $(iii)$ a clique cut separator capable of obtaining dual bounds at the root node LP relaxation that are $19.65\%$ stronger than those provided by the equivalent cut generator of a state-of-the-art commercial solver, $3.62$ times better than those attained by the clique cut separator of the GLPK solver and $4.22$ times stronger than the dual bounds obtained by the clique separation routine of the COIN-OR Cut Generation Library; and $(iv)$ an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities. The average gap closed by this new version of CBC was up to four times better than its previous version. Moreover, the number of mixed-integer programs solved by CBC in a time limit of three hours was increased by $23.53\%$.
Weighted Envy-Freeness in Indivisible Item Allocation
Venue: arXiv cs.AI 2021
Year: 2021

We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1): strong, where envy can be eliminated by removing an item from the envied agent's bundle, and weak, where envy can be eliminated either by removing an item (as in the strong version) or by replicating an item from the envied agent's bundle in the envying agent's bundle. We show that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists and can be computed in pseudo-polynomial time; moreover, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1, but always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence algorithm produces in polynomial time a strongly WEF1 allocation for an arbitrary number of agents; for two agents, we can efficiently achieve both strong WEF1 and Pareto optimality by adapting the adjusted winner procedure. Our work highlights several aspects in which weighted fair division is richer and more challenging than its unweighted counterpart.
Device-to-Device Private Caching with Trusted Server
Venue: arXiv cs.IT 2021
Year: 2021

In order to preserve the privacy of the users demands from other users, in this paper we formulate a novel information theoretic Device-to-Device (D2D) private caching model by adding a trusted server. In the delivery phase, the trusted server collects the users demands and sends a query to each user, who then broadcasts packets according to this query. Two D2D private caching schemes (uncoded and coded) are proposed in this paper, which are shown to be order optimal.
Geomorphological Analysis Using Unpiloted Aircraft Systems, Structure from Motion, and Deep Learning
Venue: arXiv cs.RO 2021
Year: 2021

We present a pipeline for geomorphological analysis that uses structure from motion (SfM) and deep learning on close-range aerial imagery to estimate spatial distributions of rock traits (size, roundness, and orientation) along a tectonic fault scarp. The properties of the rocks on the fault scarp derive from the combination of initial volcanic fracturing and subsequent tectonic and geomorphic fracturing, and our pipeline allows scientists to leverage UAS-based imagery to gain a better understanding of such surface processes. We start by using SfM on aerial imagery to produce georeferenced orthomosaics and digital elevation models (DEM). A human expert then annotates rocks on a set of image tiles sampled from the orthomosaics, and these annotations are used to train a deep neural network to detect and segment individual rocks in the entire site. The extracted semantic information (rock masks) on large volumes of unlabeled, high-resolution SfM products allows subsequent structural analysis and shape descriptors to estimate rock size, roundness, and orientation. We present results of two experiments conducted along a fault scarp in the Volcanic Tablelands near Bishop, California. We conducted the first, proof-of-concept experiment with a DJI Phantom 4 Pro equipped with an RGB camera and inspected if elevation information assisted instance segmentation from RGB channels. Rock-trait histograms along and across the fault scarp were obtained with the neural network inference. In the second experiment, we deployed a hexrotor and a multispectral camera to produce a DEM and five spectral orthomosaics in red, green, blue, red edge, and near infrared. We focused on examining the effectiveness of different combinations of input channels in instance segmentation.
Learning transport cost from subset correspondence
Venue: arXiv cs.LG 2021
Year: 2021

Learning to align multiple datasets is an important problem with many applications, and it is especially useful when we need to integrate multiple experiments or correct for confounding. Optimal transport (OT) is a principled approach to align datasets, but a key challenge in applying OT is that we need to specify a transport cost function that accurately captures how the two datasets are related. Reliable cost functions are typically not available and practitioners often resort to using hand-crafted or Euclidean cost even if it may not be appropriate. In this work, we investigate how to learn the cost function using a small amount of side information which is often available. The side information we consider captures subset correspondence -- i.e. certain subsets of points in the two data sets are known to be related. For example, we may have some images labeled as cars in both datasets; or we may have a common annotated cell type in single-cell data from two batches. We develop an end-to-end optimizer (OT-SI) that differentiates through the Sinkhorn algorithm and effectively learns the suitable cost function from side information. On systematic experiments in images, marriage-matching and single-cell RNA-seq, our method substantially outperform state-of-the-art benchmarks.
Likelihood-based approach to discriminate mixtures of network models that vary in time
Venue: arXiv cs.SI 2021
Year: 2021

Discriminating between competing explanatory models as to which is more likely responsible for the growth of a network is a problem of fundamental importance for network science. The rules governing this growth are attributed to mechanisms such as preferential attachment and triangle closure, with a wealth of explanatory models based on these. These models are deliberately simple, commonly with the network growing according to a constant mechanism for its lifetime, to allow for analytical results. We use a likelihood-based framework on artificial data where the network model changes at a known point in time and demonstrate that we can recover the change point from analysis of the network. We then use real datasets and demonstrate how our framework can show the changing importance of network growth mechanisms over time.
Controllable Data Synthesis Method for Grammatical Error Correction
Venue: arXiv cs.CL 2021
Year: 2021

Due to the lack of parallel data in current Grammatical Error Correction (GEC) task, models based on Sequence to Sequence framework cannot be adequately trained to obtain higher performance. We propose two data synthesis methods which can control the error rate and the ratio of error types on synthetic data. The first approach is to corrupt each word in the monolingual corpus with a fixed probability, including replacement, insertion and deletion. Another approach is to train error generation models and further filtering the decoding results of the models. The experiments on different synthetic data show that the error rate is 40% and the ratio of error types is the same can improve the model performance better. Finally, we synthesize about 100 million data and achieve comparable performance as the state of the art, which uses twice as much data as we use.
Noisy Simon Period Finding
Venue: arXiv cs.CR 2021
Year: 2021

Let $f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ be a Boolean function with period $\vec s$. It is well-known that Simon's algorithm finds $\vec s$ in time polynomial in $n$ on quantum devices that are capable of performing error-correction. However, today's quantum devices are inherently noisy, too limited for error correction, and Simon's algorithm is not error-tolerant. We show that even noisy quantum period finding computations may lead to speedups in comparison to purely classical computations. To this end, we implemented Simon's quantum period finding circuit on the $15$-qubit quantum device IBM Q 16 Melbourne. Our experiments show that with a certain probability $τ(n)$ we measure erroneous vectors that are not orthogonal to $\vec s$. We propose new, simple, but very effective smoothing techniques to classically mitigate physical noise effects such as e.g. IBM Q's bias towards the $0$-qubit. After smoothing, our noisy quantum device provides us a statistical distribution that we can easily transform into an LPN instance with parameters $n$ and $τ(n)$. Hence, in the noisy case we may not hope to find periods in time polynomial in $n$. However, we may still obtain a quantum advantage if the error $τ(n)$ does not grow too large. This demonstrates that quantum devices may be useful for period finding, even before achieving the level of full error correction capability.
A Henkin-style completeness proof for the modal logic S5
Venue: arXiv cs.LO 2021
Year: 2021

This paper presents a recent formalization of a Henkin-style completeness proof for the propositional modal logic S5 using the Lean theorem prover. The proof formalized is close to that of Hughes and Cresswell, but the system, based on a different choice of axioms, is better described as a Mendelson system augmented with axiom schemes for K, T, S4, and B, and the necessitation rule as a rule of inference. The language has the false and implication as the only primitive logical connectives and necessity as the only primitive modal operator. The full source code is available online at https://github.com/bbentzen/mpl/ and has been typechecked with Lean 3.4.2.
Template-based Minor Embedding for Adiabatic Quantum Optimization
Venue: arXiv cs.DS 2021
Year: 2021

Quantum Annealing (QA) can be used to quickly obtain near-optimal solutions for Quadratic Unconstrained Binary Optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to some pair of adjacent qubits. However, qubits have limited connectivity in existing QA hardware. This has spurred work on preprocessing algorithms for embedding the graph representing problem variables with quadratic terms into the hardware graph representing qubits adjacencies, such as the Chimera graph in hardware produced by D-Wave Systems. In this paper, we use integer linear programming to search for an embedding of the problem graph into certain classes of minors of the Chimera graph, which we call template embeddings. One of these classes corresponds to complete bipartite graphs, for which we show the limitation of the existing approach based on minimum Odd Cycle Transversals (OCTs). One of the formulations presented is exact, and thus can be used to certify the absence of a minor embedding using that template. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed more graphs than a state-of-the-art OCT-based approach, our approach scales better with the hardware size, and the runtime is generally orders of magnitude smaller.
Evaluation of Error Probability of Classification Based on the Analysis of the Bayes Code: Extension and Example
Venue: arXiv cs.IT 2021
Year: 2021

Suppose that we have two training sequences generated by parametrized distributions $P_{θ^*}$ and $P_{ξ^*}$, where $θ^*$ and $ξ^*$ are unknown true parameters. Given training sequences, we study the problem of classifying whether a test sequence was generated according to $P_{θ^*}$ or $P_{ξ^*}$. This problem can be thought of as a hypothesis testing problem and our aim is to analyze the weighted sum of type-I and type-II error probabilities. Utilizing the analysis of the codeword lengths of the Bayes code, our previous study derived more refined bounds on the error probability than known previously. However, our previous study had the following deficiencies: i) the prior distributions of $θ$ and $ξ$ are the same; ii) the prior distributions of two hypotheses are uniform; iii) no numerical calculation at finite blocklength. This study solves these problems. We remove the restrictions i) and ii) and derive more general results than obtained previously. To deal with problem iii), we perform a numerical calculation for a concrete model.
Upper and Lower Bounds for Fully Retroactive Graph Problems
Venue: arXiv cs.DS 2021
Year: 2021

Classic dynamic data structure problems maintain a data structure subject to a sequence S of updates and they answer queries using the latest version of the data structure, i.e., the data structure after processing the whole sequence. To handle operations that change the sequence S of updates, Demaine et al. (TALG 2007) introduced retroactive data structures. A retroactive operation modifies the update sequence S in a given position t, called time, and either creates or cancels an update in S at time t. A partially retroactive data structure restricts queries to be executed exclusively in the latest version of the data structure. A fully retroactive data structure supports queries at any time t: a query at time t is answered using only the updates of S up to time t. If the sequence S only consists of insertions, the resulting data structure is an incremental retroactive data structure. While efficient retroactive data structures have been proposed for classic data structures, e.g., stack, priority queue and binary search tree, the retroactive version of graph problems are rarely studied. In this paper we study retroactive graph problems including connectivity, minimum spanning forest (MSF), maximum degree, etc. We provide fully retroactive data structures for maintaining the maximum degree, connectivity and MSF in $\tilde{O}(n)$ time per operation. We also give an algorithm for the incremental fully retroactive connectivity with $\tilde{O}(1)$ time per operation. We compliment our algorithms with almost tight hardness results. We show that under the OMv conjecture (proposed by Henzinger et al. (STOC 2015)), there does not exist fully retroactive data structures maintaining connectivity or MSF, or incremental fully retroactive data structure maintaining the maximum degree with $O(n^{1-ε})$ time per operation, for any constant $ε> 0$.
Who's responsible? Jointly quantifying the contribution of the learning algorithm and training data
Venue: arXiv cs.LG 2021
Year: 2021

A learning algorithm $A$ trained on a dataset $D$ is revealed to have poor performance on some subpopulation at test time. Where should the responsibility for this lay? It can be argued that the data is responsible, if for example training $A$ on a more representative dataset $D'$ would have improved the performance. But it can similarly be argued that $A$ itself is at fault, if training a different variant $A'$ on the same dataset $D$ would have improved performance. As ML becomes widespread and such failure cases more common, these types of questions are proving to be far from hypothetical. With this motivation in mind, in this work we provide a rigorous formulation of the joint credit assignment problem between a learning algorithm $A$ and a dataset $D$. We propose Extended Shapley as a principled framework for this problem, and experiment empirically with how it can be used to address questions of ML accountability.
Estimating Transfer Entropy via Copula Entropy
Venue: arXiv cs.LG 2021
Year: 2021

Causal discovery is a fundamental problem in statistics and has wide applications in different fields. Transfer Entropy (TE) is a important notion defined for measuring causality, which is essentially conditional Mutual Information (MI). Copula Entropy (CE) is a theory on measurement of statistical independence and is equivalent to MI. In this paper, we prove that TE can be represented with only CE and then propose a non-parametric method for estimating TE via CE. The proposed method was applied to analyze the Beijing PM2.5 data in the experiments. Experimental results show that the proposed method can infer causality relationships from data effectively and hence help to understand the data better.