OpenRaiser/Intern-Atlas huggingface dataset:
Destroying Bicolored $P_3$s by Deleting Few Edges
Venue: arXiv cs.DS 2021
Year: 2021

We introduce and study the Bicolored $P_3$ Deletion problem defined as follows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitioned into a set $E_r$ of red edges and a set $E_b$ of blue edges. The question is whether we can delete at most $k$ edges such that $G$ does not contain a bicolored $P_3$ as an induced subgraph. Here, a bicolored $P_3$ is a path on three vertices with one blue and one red edge. We show that Bicolored $P_3$ Deletion is NP-hard and cannot be solved in $2^{o(|V|+|E|)}$ time on bounded-degree graphs if the ETH is true. Then, we show that Bicolored $P_3$ Deletion is polynomial-time solvable when $G$ does not contain a bicolored $K_3$, that is, a triangle with edges of both colors. Moreover, we provide a polynomial-time algorithm for the case that $G$ contains no blue $P_3$, red $P_3$, blue $K_3$, and red $K_3$. Finally, we show that Bicolored $P_3$ Deletion can be solved in $ O(1.84^k\cdot |V| \cdot |E|)$ time and that it admits a kernel with $ O(kΔ\min(k,Δ))$ vertices, where $Δ$ is the maximum degree of $G$.
On the Optimality of D2D Coded Caching with Uncoded Cache Placement and One-shot Delivery
Venue: arXiv cs.IT 2021
Year: 2021

We consider a cache-aided wireless device-to-device (D2D) network of the type introduced by Ji, Caire, and Molisch [1], where the placement phase is orchestrated by a central server. We assume that the devices' caches are filled with uncoded data, and the whole content database is contained in the collection of caches. After the cache placement phase, the files requested by the users are serviced by inter-device multicast communication. For such a system setting, we provide the exact characterization of the optimal load-memory trade-off under the assumptions of uncoded placement and one-shot delivery. In particular, we derive both the minimum average (under uniformly distributed demands) and the minimum worst-case sum-load of the D2D transmissions, for given individual cache memory size at disposal of each user. Furthermore, we show that the performance of the proposed scheme is within factor $4$ of the information-theoretic optimum. Capitalizing on the one-shot delivery property, we also propose an extension of the presented scheme that provides robustness against random user inactivity.
Unifying the Brascamp-Lieb Inequality and the Entropy Power Inequality
Venue: arXiv cs.IT 2021
Year: 2021

The entropy power inequality (EPI) and the Brascamp-Lieb inequality (BLI) are fundamental inequalities concerning the differential entropies of linear transformations of random vectors. The EPI provides lower bounds for the differential entropy of linear transformations of random vectors with independent components. The BLI, on the other hand, provides upper bounds on the differential entropy of a random vector in terms of the differential entropies of some of its linear transformations. In this paper, we define a family of entropy functionals, which we show are subadditive. We then establish that Gaussians are extremal for these functionals by mimicking the idea in Geng and Nair (2014). As a consequence, we obtain a new entropy inequality that generalizes both the BLI and EPI. By considering a variety of independence relations among the components of the random vectors appearing in these functionals, we also obtain families of inequalities that lie between the EPI and the BLI.
Fast algorithms at low temperatures via Markov chains
Venue: arXiv cs.DS 2021
Year: 2021

We define a discrete-time Markov chain for abstract polymer models and show that under sufficient decay of the polymer weights, this chain mixes rapidly. We apply this Markov chain to polymer models derived from the hard-core and ferromagnetic Potts models on bounded-degree (bipartite) expander graphs. In this setting, Jenssen, Keevash and Perkins (2019) recently gave an FPTAS and an efficient sampling algorithm at sufficiently high fugacity and low temperature respectively. Their method is based on using the cluster expansion to obtain a complex zero-free region for the partition function of a polymer model, and then approximating this partition function using the polynomial interpolation method of Barvinok. Our approach via the polymer model Markov chain circumvents the zero-free analysis and the generalization to complex parameters, and leads to a sampling algorithm with a fast running time of $O(n \log n)$ for the Potts model and $O(n^2 \log n)$ for the hard-core model, in contrast to typical running times of $n^{O(\log Δ)}$ for algorithms based on Barvinok's polynomial interpolation method on graphs of maximum degree $Δ$. We finally combine our results for the hard-core and ferromagnetic Potts models with standard Markov chain comparison tools to obtain polynomial mixing time for the usual spin Glauber dynamics restricted to even and odd or `red' dominant portions of the respective state spaces.
Mixed integer formulations using natural variables for single machine scheduling around a common due date
Venue: arXiv cs.DS 2021
Year: 2021

While almost all existing works which optimally solve just-in-time scheduling problems propose dedicated algorithmic approaches, we propose in this work mixed integer formulations. We consider a single machine scheduling problem that aims at minimizing the weighted sum of earliness tardiness penalties around a common due-date. Using natural variables, we provide one compact formulation for the unrestrictive case and, for the general case, a non-compact formulation based on non-overlapping inequalities. We show that the separation problem related to the latter formulation is solved polynomially. In this formulation, solutions are only encoded by extreme points. We establish a theoretical framework to show the validity of such a formulation using non-overlapping inequalities, which could be used for other scheduling problems. A Branch-and-Cut algorithm together with an experimental analysis are proposed to assess the practical relevance of this mixed integer programming based methods.
Face morphing detection in the presence of printing/scanning and heterogeneous image sources
Venue: arXiv cs.CV 2021
Year: 2021

Face morphing represents nowadays a big security threat in the context of electronic identity documents as well as an interesting challenge for researchers in the field of face recognition. Despite of the good performance obtained by state-of-the-art approaches on digital images, no satisfactory solutions have been identified so far to deal with cross-database testing and printed-scanned images (typically used in many countries for document issuing). In this work, novel approaches are proposed to train Deep Neural Networks for morphing detection: in particular generation of simulated printed-scanned images together with other data augmentation strategies and pre-training on large face recognition datasets, allowed to reach state-of-the-art accuracy on challenging datasets from heterogeneous image sources.
Provably efficient RL with Rich Observations via Latent State Decoding
Venue: arXiv cs.LG 2021
Year: 2021

We study the exploration problem in episodic MDPs with rich observations generated from a small number of latent states. Under certain identifiability assumptions, we demonstrate how to estimate a mapping from the observations to latent states inductively through a sequence of regression and clustering steps -- where previously decoded latent states provide labels for later regression problems -- and use it to construct good exploration policies. We provide finite-sample guarantees on the quality of the learned state decoding function and exploration policies, and complement our theory with an empirical evaluation on a class of hard exploration problems. Our method exponentially improves over $Q$-learning with naïve exploration, even when $Q$-learning has cheating access to latent states.
Sparse evolutionary Deep Learning with over one million artificial neurons on commodity hardware
Venue: arXiv cs.NE 2021
Year: 2021

Artificial Neural Networks (ANNs) have emerged as hot topics in the research community. Despite the success of ANNs, it is challenging to train and deploy modern ANNs on commodity hardware due to the ever-increasing model size and the unprecedented growth in the data volumes. Particularly for microarray data, the very-high dimensionality and the small number of samples make it difficult for machine learning techniques to handle. Furthermore, specialized hardware such as Graphics Processing Unit (GPU) is expensive. Sparse neural networks are the leading approaches to address these challenges. However, off-the-shelf sparsity inducing techniques either operate from a pre-trained model or enforce the sparse structure via binary masks. The training efficiency of sparse neural networks cannot be obtained practically. In this paper, we introduce a technique allowing us to train truly sparse neural networks with fixed parameter count throughout training. Our experimental results demonstrate that our method can be applied directly to handle high dimensional data, while achieving higher accuracy than the traditional two phases approaches. Moreover, we have been able to create truly sparse MultiLayer Perceptrons (MLPs) models with over one million neurons and to train them on a typical laptop without GPU, this being way beyond what is possible with any state-of-the-art techniques.
Edge, Ridge, and Blob Detection with Symmetric Molecules
Venue: arXiv cs.CV 2021
Year: 2021

We present a novel approach to the detection and characterization of edges, ridges, and blobs in two-dimensional images which exploits the symmetry properties of directionally sensitive analyzing functions in multiscale systems that are constructed in the framework of alpha-molecules. The proposed feature detectors are inspired by the notion of phase congruency, stable in the presence of noise, and by definition invariant to changes in contrast. We also show how the behavior of coefficients corresponding to differently scaled and oriented analyzing functions can be used to obtain a comprehensive characterization of the geometry of features in terms of local tangent directions, widths, and heights. The accuracy and robustness of the proposed measures are validated and compared to various state-of-the-art algorithms in extensive numerical experiments in which we consider sets of clean and distorted synthetic images that are associated with reliable ground truths. To further demonstrate the applicability, we show how the proposed ridge measure can be used to detect and characterize blood vessels in digital retinal images and how the proposed blob measure can be applied to automatically count the number of cell colonies in a Petri dish.
Learning Context-Dependent Choice Functions
Venue: arXiv cs.LG 2021
Year: 2021

Choice functions accept a set of alternatives as input and produce a preferred subset of these alternatives as output. We study the problem of learning such functions under conditions of context-dependence of preferences, which means that the preference in favor of a certain choice alternative may depend on what other options are also available. In spite of its practical relevance, this kind of context-dependence has received little attention in preference learning so far. We propose a suitable model based on context-dependent (latent) utility functions, thereby reducing the problem to the task of learning such utility functions. Practically, this comes with a number of challenges. For example, the set of alternatives provided as input to a choice function can be of any size, and the output of the function should not depend on the order in which the alternatives are presented. To meet these requirements, we propose two general approaches based on two representations of context-dependent utility functions, as well as instantiations in the form of appropriate end-to-end trainable neural network architectures. Moreover, to demonstrate the performance of both networks, we present extensive empirical evaluations on both synthetic and real-world datasets.
Labelling Vertebrae with 2D Reformations of Multidetector CT Images: An Adversarial Approach for Incorporating Prior Knowledge of Spine Anatomy
Venue: arXiv cs.CV 2021
Year: 2021

Purpose: To use and test a labelling algorithm that operates on two-dimensional (2D) reformations, rather than three-dimensional (3D) data to locate and identify vertebrae. Methods: We improved the Btrfly Net (described by Sekuboyina et al) that works on sagittal and coronal maximum intensity projections (MIP) and augmented it with two additional components: spine-localization and adversarial a priori-learning. Furthermore, we explored two variants of adversarial training schemes that incorporated the anatomical a priori knowledge into the Btrfly Net. We investigated the superiority of the proposed approach for labelling vertebrae on three datasets: a public benchmarking dataset of 302 CT scans and two in-house datasets with a total of 238 CT scans. We employed Wilcoxon signed-rank test to compute the statistical significance of the improvement in performance observed due to various architectural components in our approach. Results: On the public dataset, our approach using the described Btrfly(pe-eb) network performed on par with current state-of-the-art methods achieving a statistically significant (p < .001) vertebrae identification rate of 88.5+/-0.2 % and localization distances of less than 7-mm. On the in-house datasets that had a higher inter-scan data variability, we obtained an identification rate of 85.1+/-1.2%. Conclusion: An identification performance comparable to existing 3D approaches was achieved when labelling vertebrae on 2D MIPs. The performance was further improved using the proposed adversarial training regime that effectively enforced local spine a priori knowledge during training. Lastly, spine-localization increased the generalizability of our approach by homogenizing the content in the MIPs.
Thompson Sampling with Information Relaxation Penalties
Venue: arXiv cs.LG 2021
Year: 2021

We consider a finite-horizon multi-armed bandit (MAB) problem in a Bayesian setting, for which we propose an information relaxation sampling framework. With this framework, we define an intuitive family of control policies that include Thompson sampling (TS) and the Bayesian optimal policy as endpoints. Analogous to TS, which, at each decision epoch pulls an arm that is best with respect to the randomly sampled parameters, our algorithms sample entire future reward realizations and take the corresponding best action. However, this is done in the presence of "penalties" that seek to compensate for the availability of future information. We develop several novel policies and performance bounds for MAB problems that vary in terms of improving performance and increasing computational complexity between the two endpoints. Our policies can be viewed as natural generalizations of TS that simultaneously incorporate knowledge of the time horizon and explicitly consider the exploration-exploitation trade-off. We prove associated structural results on performance bounds and suboptimality gaps. Numerical experiments suggest that this new class of policies perform well, in particular in settings where the finite time horizon introduces significant exploration-exploitation tension into the problem. Finally, inspired by the finite-horizon Gittins index, we propose an index policy that builds on our framework that particularly outperforms the state-of-the-art algorithms in our numerical experiments.
Differentials and distances in probabilistic coherence spaces
Venue: arXiv cs.LO 2021
Year: 2021

In probabilistic coherence spaces, a denotational model of probabilistic functional languages, mor-phisms are analytic and therefore smooth. We explore two related applications of the corresponding derivatives. First we show how derivatives allow to compute the expectation of execution time in the weak head reduction of probabilistic PCF (pPCF). Next we apply a general notion of "local" differential of morphisms to the proof of a Lipschitz property of these morphisms allowing in turn to relate the observational distance on pPCF terms to a distance the model is naturally equipped with. This suggests that extending probabilistic programming languages with derivatives, in the spirit of the differential lambda-calculus, could be quite meaningful.
A Survey on Session-based Recommender Systems
Venue: arXiv cs.IR 2021
Year: 2021

Recommender systems (RSs) have been playing an increasingly important role for informed consumption, services, and decision-making in the overloaded information era and digitized economy. In recent years, session-based recommender systems (SBRSs) have emerged as a new paradigm of RSs. Different from other RSs such as content-based RSs and collaborative filtering-based RSs which usually model long-term yet static user preferences, SBRSs aim to capture short-term but dynamic user preferences to provide more timely and accurate recommendations sensitive to the evolution of their session contexts. Although SBRSs have been intensively studied, neither unified problem statements for SBRSs nor in-depth elaboration of SBRS characteristics and challenges are available. It is also unclear to what extent SBRS challenges have been addressed and what the overall research landscape of SBRSs is. This comprehensive review of SBRSs addresses the above aspects by exploring in depth the SBRS entities (e.g., sessions), behaviours (e.g., users' clicks on items) and their properties (e.g., session length). We propose a general problem statement of SBRSs, summarize the diversified data characteristics and challenges of SBRSs, and define a taxonomy to categorize the representative SBRS research. Finally, we discuss new research opportunities in this exciting and vibrant area.
Timeline-based planning: Expressiveness and Complexity
Venue: arXiv cs.AI 2021
Year: 2021

Timeline-based planning is an approach originally developed in the context of space mission planning and scheduling, where problem domains are modelled as systems made of a number of independent but interacting components, whose behaviour over time, the timelines, is governed by a set of temporal constraints. This approach is different from the action-based perspective of common PDDL-like planning languages. Timeline-based systems have been successfully deployed in a number of space missions and other domains. However, despite this practical success, a thorough theoretical understanding of the paradigm was missing. This thesis fills this gap, providing the first detailed account of formal and computational properties of the timeline-based approach to planning. In particular, we show that a particularly restricted variant of the formalism is already expressive enough to compactly capture action-based temporal planning problems. Then, finding a solution plan for a timeline-based planning problem is proved to be EXPSPACE-complete. Then, we study the problem of timeline-based planning with uncertainty, that include external components whose behaviour is not under the control of the planned system. We identify a few issues in the state-of-the-art approach based on flexible plans, proposing timeline-based games, a more general game-theoretic formulation of the problem, that addresses those issues. We show that winning strategies for such games can be found in doubly-exponential time. Then, we study the expressiveness of the formalism from a logic point of view, showing that (most of) timeline-based planning problems can be captured by Bounded TPTL with Past, a fragment of TPTL+P that, unlike the latter, keeps an EXPSPACE satisfiability problem. The logic is introduced and its satisfiabilty problem is solved by extending a recent one-pass tree-shaped tableau method for LTL.
EAT: a simple and versatile semantic representation format for multi-purpose NLP
Venue: arXiv cs.CL 2021
Year: 2021

Semantic representations are central in many NLP tasks that require human-interpretable data. The conjunctivist framework - primarily developed by Pietroski (2005, 2018) - obtains expressive representations with only a few basic semantic types and relations systematically linked to syntactic positions. While representational simplicity is crucial for computational applications, such findings have not yet had major influence on NLP. We present the first generic semantic representation format for NLP directly based on these insights. We name the format EAT due to its basis in the Event-, Agent-, and Theme arguments in Neo-Davidsonian logical forms. It builds on the idea that similar tripartite argument relations are ubiquitous across categories, and can be constructed from grammatical structure without additional lexical information. We present a detailed exposition of EAT and how it relates to other prevalent formats used in prior work, such as Abstract Meaning Representation (AMR) and Minimal Recursion Semantics (MRS). EAT stands out in two respects: simplicity and versatility. Uniquely, EAT discards semantic metapredicates, and instead represents semantic roles entirely via positional encoding. This is made possible by limiting the number of roles to only three; a major decrease from the many dozens recognized in e.g. AMR and MRS. EAT's simplicity makes it exceptionally versatile in application. First, we show that drastically reducing semantic roles based on EAT benefits text generation from MRS in the test settings of Hajdik et al. (2019). Second, we implement the derivation of EAT from a syntactic parse, and apply this for parallel corpus generation between grammatical classes. Third, we train an encoder-decoder LSTM network to map EAT to English. Finally, we use both the encoder-decoder network and a rule-based alternative to conduct grammatical transformation from EAT-input.
Correct and Efficient Antichain Algorithms for Refinement Checking
Venue: arXiv cs.LO 2021
Year: 2021

The notion of refinement plays an important role in software engineering. It is the basis of a stepwise development methodology in which the correctness of a system can be established by proving, or computing, that a system refines its specification. Wang et al. describe algorithms based on antichains for efficiently deciding trace refinement, stable failures refinement and failures-divergences refinement. We identify several issues pertaining to the soundness and performance in these algorithms and propose new, correct, antichain-based algorithms. Using a number of experiments we show that our algorithms outperform the original ones in terms of running time and memory usage. Furthermore, we show that additional run time improvements can be obtained by applying divergence-preserving branching bisimulation minimisation.
Reconciliation k-median: Clustering with Non-Polarized Representatives
Venue: arXiv cs.DS 2021
Year: 2021

We propose a new variant of the k-median problem, where the objective function models not only the cost of assigning data points to cluster representatives, but also a penalty term for disagreement among the representatives. We motivate this novel problem by applications where we are interested in clustering data while avoiding selecting representatives that are too far from each other. For example, we may want to summarize a set of news sources, but avoid selecting ideologically-extreme articles in order to reduce polarization. To solve the proposed k-median formulation we adopt the local-search algorithm of Arya et al. We show that the algorithm provides a provable approximation guarantee, which becomes constant under an assumption on the minimum number of points for each cluster. We experimentally evaluate our problem formulation and proposed algorithm on datasets inspired by the motivating applications. In particular, we experiment with data extracted from Twitter, the US Congress voting records, and popular news sources. The results show that our objective can lead to choosing less polarized groups of representatives without significant loss in representation fidelity.