pwc-archive/papers-with-abstracts huggingface dataset:
JCOL: A Java package for solving the graph coloring problem
Authors: Shalin Shah
Date: 2020-04-03 00:00:00
Proceeding: Journal of Open Source Software 2020 4

The graph coloring problem aims at assigning colors to the nodes of a graph such that no two connected nodes have the same color. The graph coloring problem is NP-complete and one of the harder problems to solve. Here we present a randomized heuristic to solve this problem using three cascaded algorithms. The graph coloring problem was one of Karp’s 21 NP-complete problems, and is also know as the problem of finding the chromatic number of a graph. Several other problems reduce to graph coloring including solving generalized Sudoku puzzles.
Simulated Annealing Algorithm for the Multiple Choice Multidimensional Knapsack Problem
Authors: Shalin Shah
Date: 2020-05-01 00:00:00
Proceeding: ResearchGate 2020 5
Tasks: All, C++ code, Multiple-choice

The multiple choice multidimensional knapsack problem (MCMK) is a harder version of the 0/1 knapsack problem, and is ever more complex than the 0/1 multidimensional knapsack problem. In MCMK, there are several groups of items. The objective is to maximize the value (profit) by choosing exactly 1 item from each group such that all the constraints are satisfied. It is difficult and NP-hard even to find a solution that does not violate all constraints. In this work, we present a simulated annealing based algorithm with open source C++ code to find good solutions to the multidimensional multiple choice knapsack problem. In all of the benchmark instances we used, the algorithm is able to find optimum (or close) solutions, thereby proving that the algorithm is suitable for solving larger instances for which optimal solutions are unknown.
Implementation of iterative local search (ILS) for the quadratic assignment problem
Authors: Shalin Shah
Date: 2014-05-01 00:00:00
Proceeding: ResearchGate 2014 5

The quadratic assignment problem (QAP) is one of the hardest NP-hard problems and problems with a dimension of 20 or more can be difficult to solve using exact methods. The QAP has a set of facilities and a set of locations. The goal is to assign each facility to a location such that the product of the flow between pairs of facilities and the distance between them are minimized. Sometimes there is also a cost associated with assigning a facility to a location. In this work, I solve the QAP using a population based iterative local search with open source code in C++. Results show that the code is able to solve all nug instances to optimality, thereby proving that the algorithm is capable of solving larger problems for which optimum solutions are not known.
Randomized heuristic for the maximum clique problem
Authors: Shalin Shah
Date: 2016-05-01 00:00:00
Proceeding: ResearchGate 2016 5

A clique in a graph is a set of vertices that are all directly connected to each other i.e. a complete sub-graph. A clique of the largest size is called a maximum clique. Finding the maximum clique in a graph is an NP-hard problem and it cannot be solved by an approximation algorithm that returns a solution within a constant factor of the optimum. In this work, we present a simple and very fast randomized algorithm for the maximum clique problem. We also provide Java code of the algorithm in our git repository. Results show that the algorithm is able to find reasonably good solutions to some randomly chosen DIMACS benchmark graphs. Rather than aiming for optimality, we aim to find good solutions very fast.
Tuning Multilingual Transformers for Named Entity Recognition on Slavic Languages
Authors: Mikhail Arkhipov, Maria Trofimova, Yuri Kuratov, Alexey Sorokin
Date: 2019-01-30 00:00:00
Proceeding: Conference: Proceedings of the 7th Workshop on Balto-Slavic Natural Language Processing 2019 1
Tasks: Multilingual Named Entity Recognition, named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), NER, Unsupervised Pre-training

Our paper addresses the problem of multilingual named entity recognition on the material of 4 languages: Russian, Bulgarian, Czech and Polish. We solve this task using the BERT model. We use a hundred languages multilingual model as base for transfer to the mentioned Slavic languages. Unsupervised pre-training of the BERT model on these 4 languages allows to significantly outperform baseline neural approaches and multilingual BERT. Additional improvement is achieved by extending BERT with a word-level CRF layer. Our system was submitted to BSNLP 2019 Shared Task on Multilingual Named Entity Recognition and took the 1st place in 3 competition metrics out of 4 we participated in. We open-sourced NER models and BERT model pre-trained on the four Slavic languages.
LANGUAGE MODEL EMBEDDINGS IMPROVE SENTIMENT ANALYSIS IN RUSSIAN
Authors: Baymurzina D. R., Kuznetsov D. P., Burtsev M. S.
Date: 2019-05-29 00:00:00
Proceeding: Computational Linguistics and Intellectual Technologies: Proceedings of the International Conference “Dialogue 2019” 2019 5
Tasks: Articles, Language Modeling, Language Modelling, model, Sentiment Analysis, Text Classification

Sentiment analysis is one of the most popular natural language processing tasks. In this paper we introduce pre-trained Russian language models which are used to extract embeddings (ELMo) to improve accuracy for classification of short conversational texts. The first language model was trained on Russian Twitter dataset containing 102 million sentences, while two others were trained on 57.5 million sentences of Russian News and 23.9 million sentences of Russian Wikipedia articles. Although classifiers trained on top of language models perform better than in the case of utilizing of fastText embeddings of the same language style, we show that domain of language model also has a significant impact on accuracy. This paper establishes state-of-the-art results for RuSentiment dataset improving weighted F1-score from 72.8 to 78.5. All our models are available online as well as the source code which allows everyone to apply them or fine-tune on domain-specific data.
Sentence Level Representation And Language Models In The Task Of Coreference Resolution For Russian
Authors: Le T. A., Petrov M. A., Kuratov Y. M., Burtsev M. S.
Date: 2019-05-29 00:00:00
Proceeding: Computational Linguistics and Intellectual Technologies: Proceedings of the International Conference “Dialogue 2019” 2019 5
Tasks: coreference-resolution, Coreference Resolution, Sentence

Coreference Resolution (CR) is one of the most difficult tasks in the field of Natural Language Processing due to the lack of deeply and comprehensively understanding the semantic meaning of the mention in not only the sentence-level context but also the entire document-level context. To the best of our knowledge, the previous proposed models often address the coreference resolution task in two steps: 1) detect all possible mention candidates, 2) score and cluster them into chains. We instead propose a new approach which reforms the coreference resolution task to the task of learning sentence-level coreferential relations. Additionally, by leveraging the power of state-of-the-art language representation models such as BERT, ELMo, it was possible to achieve cutting edge results on Russian datasets.
Comparative Study of Machine Learning Models and BERT on SQuAD
Authors: Devshree Patel, Param Raval, Ratnam Parikh, Yesha Shastri
Date: 2020-05-22 00:00:00
Tasks: BIG-bench Machine Learning, Question Answering

This study aims to provide a comparative analysis of performance of certain models popular in machine learning and the BERT model on the Stanford Question Answering Dataset (SQuAD). The analysis shows that the BERT model, which was once state-of-the-art on SQuAD, gives higher accuracy in comparison to other models. However, BERT requires a greater execution time even when only 100 samples are used. This shows that with increasing accuracy more amount of time is invested in training the data. Whereas in case of preliminary machine learning models, execution time for full data is lower but accuracy is compromised.
Neural Bipartite Matching
Authors: Dobrik Georgiev, Pietro Liò
Date: 2020-05-22 00:00:00

Graph neural networks (GNNs) have found application for learning in the space of algorithms. However, the algorithms chosen by existing research (sorting, Breadth-First search, shortest path finding, etc.) usually align perfectly with a standard GNN architecture. This report describes how neural execution is applied to a complex algorithm, such as finding maximum bipartite matching by reducing it to a flow problem and using Ford-Fulkerson to find the maximum flow. This is achieved via neural execution based only on features generated from a single GNN. The evaluation shows strongly generalising results with the network achieving optimal matching almost 100% of the time.
Nonparametric inverse probability weighted estimators based on the highly adaptive lasso
Authors: Ashkan Ertefaie, Nima S. Hejazi, Mark J. Van Der Laan
Date: 2020-05-22 00:00:00

Inverse probability weighted estimators are the oldest and potentially most commonly used class of procedures for the estimation of causal effects. By adjusting for selection biases via a weighting mechanism, these procedures estimate an effect of interest by constructing a pseudo-population in which selection biases are eliminated. Despite their ease of use, these estimators require the correct specification of a model for the weighting mechanism, are known to be inefficient, and suffer from the curse of dimensionality. We propose a class of nonparametric inverse probability weighted estimators in which the weighting mechanism is estimated via undersmoothing of the highly adaptive lasso, a nonparametric regression function proven to converge at $n^{-1/3}$-rate to the true weighting mechanism. We demonstrate that our estimators are asymptotically linear with variance converging to the nonparametric efficiency bound. Unlike doubly robust estimators, our procedures require neither derivation of the efficient influence function nor specification of the conditional outcome model. Our theoretical developments have broad implications for the construction of efficient inverse probability weighted estimators in large statistical models and a variety of problem settings. We assess the practical performance of our estimators in simulation studies and demonstrate use of our proposed methodology with data from a large-scale epidemiologic study.
Model Evidence with Fast Tree Based Quadrature
Authors: Thomas Foster, Chon Lok Lei, Martin Robinson, David Gavaghan, Ben Lambert
Date: 2020-05-22 00:00:00
Tasks: Bayesian Inference, model

High dimensional integration is essential to many areas of science, ranging from particle physics to Bayesian inference. Approximating these integrals is hard, due in part to the difficulty of locating and sampling from regions of the integration domain that make significant contributions to the overall integral. Here, we present a new algorithm called Tree Quadrature (TQ) that separates this sampling problem from the problem of using those samples to produce an approximation of the integral. TQ places no qualifications on how the samples provided to it are obtained, allowing it to use state-of-the-art sampling algorithms that are largely ignored by existing integration algorithms. Given a set of samples, TQ constructs a surrogate model of the integrand in the form of a regression tree, with a structure optimised to maximise integral precision. The tree divides the integration domain into smaller containers, which are individually integrated and aggregated to estimate the overall integral. Any method can be used to integrate each individual container, so existing integration methods, like Bayesian Monte Carlo, can be combined with TQ to boost their performance. On a set of benchmark problems, we show that TQ provides accurate approximations to integrals in up to 15 dimensions; and in dimensions 4 and above, it outperforms simple Monte Carlo and the popular Vegas method.
From ImageNet to Image Classification: Contextualizing Progress on Benchmarks
Authors: Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Andrew Ilyas, Aleksander Madry
Date: 2020-05-22 00:00:00
Proceeding: ICML 2020 1
Tasks: Classification, General Classification, image-classification, Image Classification

Building rich machine learning datasets in a scalable manner often necessitates a crowd-sourced data collection pipeline. In this work, we use human studies to investigate the consequences of employing such a pipeline, focusing on the popular ImageNet dataset. We study how specific design choices in the ImageNet creation process impact the fidelity of the resulting dataset---including the introduction of biases that state-of-the-art models exploit. Our analysis pinpoints how a noisy data collection pipeline can lead to a systematic misalignment between the resulting benchmark and the real-world task it serves as a proxy for. Finally, our findings emphasize the need to augment our current model training and evaluation toolkit to take such misalignments into account. To facilitate further research, we release our refined ImageNet annotations at https://github.com/MadryLab/ImageNetMultiLabel.
PruneNet: Channel Pruning via Global Importance
Authors: Ashish Khetan, Zohar Karnin
Date: 2020-05-22 00:00:00

Channel pruning is one of the predominant approaches for accelerating deep neural networks. Most existing pruning methods either train from scratch with a sparsity inducing term such as group lasso, or prune redundant channels in a pretrained network and then fine tune the network. Both strategies suffer from some limitations: the use of group lasso is computationally expensive, difficult to converge and often suffers from worse behavior due to the regularization bias. The methods that start with a pretrained network either prune channels uniformly across the layers or prune channels based on the basic statistics of the network parameters. These approaches either ignore the fact that some CNN layers are more redundant than others or fail to adequately identify the level of redundancy in different layers. In this work, we investigate a simple-yet-effective method for pruning channels based on a computationally light-weight yet effective data driven optimization step that discovers the necessary width per layer. Experiments conducted on ILSVRC-$12$ confirm effectiveness of our approach. With non-uniform pruning across the layers on ResNet-$50$, we are able to match the FLOP reduction of state-of-the-art channel pruning results while achieving a $0.98\%$ higher accuracy. Further, we show that our pruned ResNet-$50$ network outperforms ResNet-$34$ and ResNet-$18$ networks, and that our pruned ResNet-$101$ outperforms ResNet-$50$.
Fast differentiable DNA and protein sequence optimization for molecular design
Authors: Johannes Linder, Georg Seelig
Date: 2020-05-22 00:00:00

Designing DNA and protein sequences with improved function has the potential to greatly accelerate synthetic biology. Machine learning models that accurately predict biological fitness from sequence are becoming a powerful tool for molecular design. Activation maximization offers a simple design strategy for differentiable models: one-hot coded sequences are first approximated by a continuous representation which is then iteratively optimized with respect to the predictor oracle by gradient ascent. While elegant, this method suffers from vanishing gradients and may cause predictor pathologies leading to poor convergence. Here, we build on a previously proposed straight-through approximation method to optimize through discrete sequence samples. By normalizing nucleotide logits across positions and introducing an adaptive entropy variable, we remove bottlenecks arising from overly large or skewed sampling parameters. The resulting algorithm, which we call Fast SeqProp, achieves up to 100-fold faster convergence compared to previous versions of activation maximization and finds improved fitness optima for many applications. We demonstrate Fast SeqProp by designing DNA and protein sequences for six deep learning predictors, including a protein structure predictor.
Information-Theoretic Limits for the Matrix Tensor Product
Authors: Galen Reeves
Date: 2020-05-22 00:00:00
Tasks: Stochastic Block Model

This paper studies a high-dimensional inference problem involving the matrix tensor product of random matrices. This problem generalizes a number of contemporary data science problems including the spiked matrix models used in sparse principal component analysis and covariance estimation and the stochastic block model used in network analysis. The main results are single-letter formulas (i.e., analytical expressions that can be approximated numerically) for the mutual information and the minimum mean-squared error (MMSE) in the Bayes optimal setting where the distributions of all random quantities are known. We provide non-asymptotic bounds and show that our formulas describe exactly the leading order terms in the mutual information and MMSE in the high-dimensional regime where the number of rows $n$ and number of columns $d$ scale with $d = O(n^\alpha)$ for some $\alpha < 1/20$. On the technical side, this paper introduces some new techniques for the analysis of high-dimensional matrix-valued signals. Specific contributions include a novel extension of the adaptive interpolation method that uses order-preserving positive semidefinite interpolation paths, and a variance inequality between the overlap and the free energy that is based on continuous-time I-MMSE relations.
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
Authors: Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
Date: 2020-05-22 00:00:00
Tasks: compressed sensing

In compressed sensing, the restricted isometry property (RIP) on $M \times N$ sensing matrices (where $M < N$) guarantees efficient reconstruction of sparse vectors. A matrix has the $(s,\delta)$-$\mathsf{RIP}$ property if behaves as a $\delta$-approximate isometry on $s$-sparse vectors. It is well known that an $M\times N$ matrix with i.i.d. $\mathcal{N}(0,1/M)$ entries is $(s,\delta)$-$\mathsf{RIP}$ with high probability as long as $s\lesssim \delta^2 M/\log N$. On the other hand, most prior works aiming to deterministically construct $(s,\delta)$-$\mathsf{RIP}$ matrices have failed when $s \gg \sqrt{M}$. An alternative way to find an RIP matrix could be to draw a random gaussian matrix and certify that it is indeed RIP. However, there is evidence that this certification task is computationally hard when $s \gg \sqrt{M}$, both in the worst case and the average case. In this paper, we investigate the exact average-case time complexity of certifying the RIP property for $M\times N$ matrices with i.i.d. $\mathcal{N}(0,1/M)$ entries, in the "possible but hard" regime $\sqrt{M} \ll s\lesssim M/\log N$. Based on analysis of the low-degree likelihood ratio, we give rigorous evidence that subexponential runtime $N^{\tilde\Omega(s^2/M)}$ is required, demonstrating a smooth tradeoff between the maximum tolerated sparsity and the required computational power. This lower bound is essentially tight, matching the runtime of an existing algorithm due to Koiran and Zouzias. Our hardness result allows $\delta$ to take any constant value in $(0,1)$, which captures the relevant regime for compressed sensing. This improves upon the existing average-case hardness result of Wang, Berthet, and Plan, which is limited to $\delta = o(1)$.
Givenness Hierarchy Theoretic Cognitive Status Filtering
Authors: Poulomi Pal, Lixiao Zhu, Andrea Golden-Lasher, Akshay Swaminathan, Tom Williams
Date: 2020-05-22 00:00:00
Tasks: Text Generation

For language-capable interactive robots to be effectively introduced into human society, they must be able to naturally and efficiently communicate about the objects, locations, and people found in human environments. An important aspect of natural language communication is the use of pronouns. Ac-cording to the linguistic theory of the Givenness Hierarchy(GH), humans use pronouns due to implicit assumptions about the cognitive statuses their referents have in the minds of their conversational partners. In previous work, Williams et al. presented the first computational implementation of the full GH for the purpose of robot language understanding, leveraging a set of rules informed by the GH literature. However, that approach was designed specifically for language understanding,oriented around GH-inspired memory structures used to assess what entities are candidate referents given a particular cognitive status. In contrast, language generation requires a model in which cognitive status can be assessed for a given entity. We present and compare two such models of cognitive status: a rule-based Finite State Machine model directly informed by the GH literature and a Cognitive Status Filter designed to more flexibly handle uncertainty. The models are demonstrated and evaluated using a silver-standard English subset of the OFAI Multimodal Task Description Corpus.
Epidemiologically and Socio-economically Optimal Policies via Bayesian Optimization
Authors: Amit Chandak, Debojyoti Dey, Bhaskar Mukhoty, Purushottam Kar
Date: 2020-05-22 00:00:00
Tasks: Bayesian Optimization

Mass public quarantining, colloquially known as a lock-down, is a non-pharmaceutical intervention to check spread of disease. This paper presents ESOP (Epidemiologically and Socio-economically Optimal Policies), a novel application of active machine learning techniques using Bayesian optimization, that interacts with an epidemiological model to arrive at lock-down schedules that optimally balance public health benefits and socio-economic downsides of reduced economic activity during lock-down periods. The utility of ESOP is demonstrated using case studies with VIPER (Virus-Individual-Policy-EnviRonment), a stochastic agent-based simulator that this paper also proposes. However, ESOP is flexible enough to interact with arbitrary epidemiological simulators in a black-box manner, and produce schedules that involve multiple phases of lock-downs.
A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs
Authors: Dorian Florescu, Matthew England
Date: 2020-05-22 00:00:00
Tasks: BIG-bench Machine Learning

We are interested in the application of Machine Learning (ML) technology to improve mathematical software. It may seem that the probabilistic nature of ML tools would invalidate the exact results prized by such software, however, the algorithms which underpin the software often come with a range of choices which are good candidates for ML application. We refer to choices which have no effect on the mathematical correctness of the software, but do impact its performance. In the past we experimented with one such choice: the variable ordering to use when building a Cylindrical Algebraic Decomposition (CAD). We used the Python library Scikit-Learn (sklearn) to experiment with different ML models, and developed new techniques for feature generation and hyper-parameter selection. These techniques could easily be adapted for making decisions other than our immediate application of CAD variable ordering. Hence in this paper we present a software pipeline to use sklearn to pick the variable ordering for an algorithm that acts on a polynomial system. The code described is freely available online.