OpenRaiser/Intern-Atlas huggingface dataset:
A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems
Venue: arXiv cs.LG 2020
Year: 2020

Recent researches show that machine learning has the potential to learn better heuristics than the one designed by human for solving combinatorial optimization problems. The deep neural network is used to characterize the input instance for constructing a feasible solution incrementally. Recently, an attention model is proposed to solve routing problems. In this model, the state of an instance is represented by node features that are fixed over time. However, the fact is, the state of an instance is changed according to the decision that the model made at different construction steps, and the node features should be updated correspondingly. Therefore, this paper presents a dynamic attention model with dynamic encoder-decoder architecture, which enables the model to explore node features dynamically and exploit hidden structure information effectively at different construction steps. This paper focuses on a challenging NP-hard problem, vehicle routing problem. The experiments indicate that our model outperforms the previous methods and also shows a good generalization performance.
Unlabeled Data Deployment for Classification of Diabetic Retinopathy Images Using Knowledge Transfer
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional neural networks (CNNs) are extensively beneficial for medical image processing. Medical images are plentiful, but there is a lack of annotated data. Transfer learning is used to solve the problem of lack of labeled data and grants CNNs better training capability. Transfer learning can be used in many different medical applications; however, the model under transfer should have the same size as the original network. Knowledge distillation is recently proposed to transfer the knowledge of a model to another one and can be useful to cover the shortcomings of transfer learning. But some parts of the knowledge may not be distilled by knowledge distillation. In this paper, a novel knowledge distillation using transfer learning is proposed to transfer the whole knowledge of a model to another one. The proposed method can be beneficial and practical for medical image analysis in which a small number of labeled data are available. The proposed process is tested for diabetic retinopathy classification. Simulation results demonstrate that using the proposed method, knowledge of an extensive network can be transferred to a smaller model.
Performance Analysis of SWIPT Relaying Systems in the Presence of Impulsive Noise
Venue: arXiv cs.IT 2020
Year: 2020

We develop an analytical framework to characterize the effect of impulsive noise on the performance of relay-assisted simultaneous wireless information and power transfer (SWIPT) systems. We derive novel closed-form expressions for the pairwise error probability (PEP) considering two variants based on the availability of channel state information (CSI), namely, blind relaying and CSI-assisted relaying. We further consider two energy harvesting (EH) techniques, i.e., instantaneous EH (IEH) and average EH (AEH). Capitalizing on the derived analytical results, we present a detailed numerical investigation of the diversity order for the underlying scenarios under the impulsive noise assumption. For the case when two relays and the availability of a direct link, it is demonstrated that the considered SWIPT system with blind AEH-relaying is able to achieve an asymptotic diversity order of less than 3, which is equal to the diversity order achieved by CSI-assisted IEH-relaying. This result suggests that, by employing the blind AEH relaying, the power consumption of the network can be reduced, due to eliminating the need of CSI estimation. This can be achieved without any performance loss. Our results further show that placing the relays close to the source can significantly mitigate the detrimental effects of impulsive noise. Extensive Monte Carlo simulation results are presented to validate the accuracy of the proposed analytical framework.
Understanding HPC Benchmark Performance on Intel Broadwell and Cascade Lake Processors
Venue: arXiv cs.PF 2020
Year: 2020

Hardware platforms in high performance computing are constantly getting more complex to handle even when considering multicore CPUs alone. Numerous features and configuration options in the hardware and the software environment that are relevant for performance are not even known to most application users or developers. Microbenchmarks, i.e., simple codes that fathom a particular aspect of the hardware, can help to shed light on such issues, but only if they are well understood and if the results can be reconciled with known facts or performance models. The insight gained from microbenchmarks may then be applied to real applications for performance analysis or optimization. In this paper we investigate two modern Intel x86 server CPU architectures in depth: Broadwell EP and Cascade Lake SP. We highlight relevant hardware configuration settings that can have a decisive impact on code performance and show how to properly measure on-chip and off-chip data transfer bandwidths. The new victim L3 cache of Cascade Lake and its advanced replacement policy receive due attention. Finally we use DGEMM, sparse matrix-vector multiplication, and the HPCG benchmark to make a connection to relevant application scenarios.
Abstractive Summarization for Low Resource Data using Domain Transfer and Data Synthesis
Venue: arXiv cs.CL 2020
Year: 2020

Training abstractive summarization models typically requires large amounts of data, which can be a limitation for many domains. In this paper we explore using domain transfer and data synthesis to improve the performance of recent abstractive summarization methods when applied to small corpora of student reflections. First, we explored whether tuning state of the art model trained on newspaper data could boost performance on student reflection data. Evaluations demonstrated that summaries produced by the tuned model achieved higher ROUGE scores compared to model trained on just student reflection data or just newspaper data. The tuned model also achieved higher scores compared to extractive summarization baselines, and additionally was judged to produce more coherent and readable summaries in human evaluations. Second, we explored whether synthesizing summaries of student data could additionally boost performance. We proposed a template-based model to synthesize new data, which when incorporated into training further increased ROUGE scores. Finally, we showed that combining data synthesis with domain transfer achieved higher ROUGE scores compared to only using one of the two approaches.
Optimal polynomial-time compression for Boolean Max CSP
Venue: arXiv cs.CC 2020
Year: 2020

In the Boolean maximum constraint satisfaction problem - Max CSP$(Γ)$ - one is given a collection of weighted applications of constraints from a finite constraint language $Γ$, over a common set of variables, and the goal is to assign Boolean values to the variables so that the total weight of satisfied constraints is maximized. There exists an elegant dichotomy theorem providing a criterion on $Γ$ for the problem to be polynomial-time solvable and stating that otherwise it becomes NP-hard. We study the NP hard cases through the lens of kernelization and provide a complete characterization of Max CSP$(Γ)$ with respect to the optimal compression size. Namely, we prove that Max CSP$(Γ)$ parameterized by the number of variables $n$ is either polynomial-time solvable, or there exists an integer $d \ge 2$ depending on $Γ$, such that 1. An instance of \textsc{Max CSP$(Γ)$} can be compressed into an equivalent instance with $O(n^d\log n)$ bits in polynomial time, 2. Max CSP$(Γ)$ does not admit such a compression to $O(n^{d-ε})$ bits unless $\text{NP} \subseteq \text{co-NP} / \text{poly}$. Our reductions are based on interpreting constraints as multilinear polynomials combined with the framework of constraint implementations. As another application of our reductions, we reveal tight connections between optimal running times for solving Max CSP$(Γ)$. More precisely, we show that obtaining a running time of the form $O(2^{(1-ε)n})$ for particular classes of Max CSPs is as hard as breaching this barrier for Max $d$-SAT for some $d$.
Relation Embedding for Personalised POI Recommendation
Venue: arXiv cs.LG 2020
Year: 2020

Point-of-Interest (POI) recommendation is one of the most important location-based services helping people discover interesting venues or services. However, the extreme user-POI matrix sparsity and the varying spatio-temporal context pose challenges for POI systems, which affects the quality of POI recommendations. To this end, we propose a translation-based relation embedding for POI recommendation. Our approach encodes the temporal and geographic information, as well as semantic contents effectively in a low-dimensional relation space by using Knowledge Graph Embedding techniques. To further alleviate the issue of user-POI matrix sparsity, a combined matrix factorization framework is built on a user-POI graph to enhance the inference of dynamic personal interests by exploiting the side-information. Experiments on two real-world datasets demonstrate the effectiveness of our proposed model.
Robust Online Composition, Routing and NF Placement for NFV-enabled Services
Venue: arXiv cs.NI 2020
Year: 2020

Network function virtualization (NFV) fosters innovation in the networking field and reduces the complexity involved in managing modern-day conventional networks. Via NFV, the provisioning of a network service becomes more agile, whereby virtual network functions can be instantiated on commodity servers and data centers on demand. Network functions can be either mandatory or best-effort. The former type is strictly necessary for the correctness of a network service, whereas the latter is preferrable yet not necessary. In this paper, we study the online provisioning of NFV-enabled network services. We consider both unicast and multicast NFV-enabled services with multiple mandatory and best-effort NF instances. We propose a primal-dual based online approximation algorithm that allocates both processing and transmission resources to maximize a profit function, subject to resource constraints on physical links and NFV nodes. The online algorithm resembles a joint admission mechanism and an online composition, routing and NF placement framework. The online algorithm is derived from an offline formulation through a primal-dual based analysis. Such analysis offers direct insights and a fundamental understanding on the nature of the profit-maximization problem for NFV-enabled services with multiple resource types.
Meet Malexa, Alexa's Malicious Twin: Malware-Induced Misperception Through Intelligent Voice Assistants
Venue: arXiv cs.CR 2020
Year: 2020

This paper reports the findings of a study where users (N=220) interacted with Malexa, Alexa's malicious twin. Malexa is an intelligent voice assistant with a simple and seemingly harmless third-party skill that delivers news briefings to users. The twist, however, is that Malexa covertly rewords these briefings to intentionally introduce misperception about the reported events. This covert rewording is referred to as a Malware-Induced Misperception (MIM) attack. It differs from squatting or invocation hijacking attacks in that it is focused on manipulating the "content" delivered through a third-party skill instead of the skill's "invocation logic." Malexa, in the study, reworded regulatory briefings to make a government response sound more accidental or lenient than the original news delivered by Alexa. The results show that users who interacted with Malexa perceived that the government was less friendly to working people and more in favor of big businesses. The results also show that Malexa is capable of inducing misperceptions regardless of the user's gender, political ideology or frequency of interaction with intelligent voice assistants. We discuss the implications in the context of using Malexa as a covert "influencer" in people's living or working environments.
PBE-CC: Congestion Control via Endpoint-Centric, Physical-Layer Bandwidth Measurements
Venue: arXiv cs.NI 2020
Year: 2020

Wireless networks are becoming ever more sophisticated and overcrowded, imposing the most delay, jitter, and throughput damage to end-to-end network flows in today's internet. We therefore argue for fine-grained mobile endpoint-based wireless measurements to inform a precise congestion control algorithm through a well-defined API to the mobile's wireless physical layer. Our proposed congestion control algorithm is based on Physical-Layer Bandwidth measurements taken at the Endpoint (PBE-CC), and captures the latest 5G New Radio innovations that increase wireless capacity, yet create abrupt rises and falls in available wireless capacity that the PBE-CC sender can react to precisely and very rapidly. We implement a proof-of-concept prototype of the PBE measurement module on software-defined radios and the PBE sender and receiver in C. An extensive performance evaluation compares PBE-CC head to head against the leading cellular-aware and wireless-oblivious congestion control protocols proposed in the research community and in deployment, in mobile and static mobile scenarios, and over busy and quiet networks. Results show 6.3% higher average throughput than BBR, while simultaneously reducing 95th percentile delay by 1.8x.
Massive Access for 5G and Beyond
Venue: arXiv cs.IT 2020
Year: 2020

Massive access, also known as massive connectivity or massive machine-type communication (mMTC), is one of the main use cases of the fifth-generation (5G) and beyond 5G (B5G) wireless networks. A typical application of massive access is the cellular Internet of Things (IoT). Different from conventional human-type communication, massive access aims at realizing efficient and reliable communications for a massive number of IoT devices. Hence, the main characteristics of massive access include low power, massive connectivity, and broad coverage, which require new concepts, theories, and paradigms for the design of next-generation cellular networks. This paper presents a comprehensive survey of aspects of massive access design for B5G wireless networks. Specifically, we provide a detailed review of massive access from the perspectives of theory, protocols, techniques, coverage, energy, and security. Furthermore, several future research directions and challenges are identified.
Fair Correlation Clustering
Venue: arXiv cs.DS 2020
Year: 2020

In this paper we study the problem of correlation clustering under fairness constraints. In the classic correlation clustering problem, we are given a complete graph where each edge is labeled positive or negative. The goal is to obtain a clustering of the vertices that minimizes disagreements -- the number of negative edges trapped inside a cluster plus positive edges between different clusters. We consider two variations of fairness constraint for the problem of correlation clustering where each node has a color, and the goal is to form clusters that do not over-represent vertices of any color. The first variant aims to generate clusters with minimum disagreements, where the distribution of a feature (e.g. gender) in each cluster is same as the global distribution. For the case of two colors when the desired ratio of the number of colors in each cluster is $1:p$, we get $\mathcal{O}(p^2)$-approximation algorithm. Our algorithm could be extended to the case of multiple colors. We prove this problem is NP-hard. The second variant considers relative upper and lower bounds on the number of nodes of any color in a cluster. The goal is to avoid violating upper and lower bounds corresponding to each color in each cluster while minimizing the total number of disagreements. Along with our theoretical results, we show the effectiveness of our algorithm to generate fair clusters by empirical evaluation on real world data sets.
Multi-object Monocular SLAM for Dynamic Environments
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we tackle the problem of multibody SLAM from a monocular camera. The term multibody, implies that we track the motion of the camera, as well as that of other dynamic participants in the scene. The quintessential challenge in dynamic scenes is unobservability: it is not possible to unambiguously triangulate a moving object from a moving monocular camera. Existing approaches solve restricted variants of the problem, but the solutions suffer relative scale ambiguity (i.e., a family of infinitely many solutions exist for each pair of motions in the scene). We solve this rather intractable problem by leveraging single-view metrology, advances in deep learning, and category-level shape estimation. We propose a multi pose-graph optimization formulation, to resolve the relative and absolute scale factor ambiguities involved. This optimization helps us reduce the average error in trajectories of multiple bodies over real-world datasets, such as KITTI. To the best of our knowledge, our method is the first practical monocular multi-body SLAM system to perform dynamic multi-object and ego localization in a unified framework in metric scale.
On the Complexity of Constructive Control under Nearly Single-Peaked Preferences
Venue: arXiv cs.GT 2020
Year: 2020

We investigate the complexity of {\sc{Constructive Control by Adding/Deleting Votes}} (CCAV/CCDV) for $r$-approval, Condorcet, Maximin and Copeland$^α$ in $k$-axes and $k$-candidates partition single-peaked elections. In general, we prove that CCAV and CCDV for most of the voting correspondences mentioned above are NP-hard even when~$k$ is a very small constant. Exceptions are CCAV and CCDV for Condorcet and CCAV for $r$-approval in $k$-axes single-peaked elections, which we show to be fixed-parameter tractable with respect to~$k$. In addition, we give a polynomial-time algorithm for recognizing $2$-axes elections, resolving an open problem. Our work leads to a number of dichotomy results. To establish an NP-hardness result, we also study a property of $3$-regular bipartite graphs which may be of independent interest. In particular, we prove that for every $3$-regular bipartite graph, there are two linear orders of its vertices such that the two endpoints of every edge are consecutive in at least one of the two orders.
Vehicle Driving Assistant
Venue: arXiv cs.CV 2020
Year: 2020

Autonomous vehicles has been a common term in our day to day life with car manufacturers like Tesla shipping cars that are SAE Level 3. While these vehicles include a slew of features such as parking assistance and cruise control,they have mostly been tailored to foreign roads. Potholes, and the abundance of them, is something that is unique to our Indian roads. We believe that successful detection of potholes from visual images can be applied in a variety of scenarios. Moreover, the sheer variety in the color, shape and size of potholes makes this problem an apt candidate to be solved using modern machine learning and image processing techniques.
Optimization of Retrieval Algorithms on Large Scale Knowledge Graphs
Venue: arXiv cs.DB 2020
Year: 2020

Knowledge graphs have been shown to play an important role in recent knowledge mining and discovery, for example in the field of life sciences or bioinformatics. Although a lot of research has been done on the field of query optimization, query transformation and of course in storing and retrieving large scale knowledge graphs the field of algorithmic optimization is still a major challenge and a vital factor in using graph databases. Few researchers have addressed the problem of optimizing algorithms on large scale labeled property graphs. Here, we present two optimization approaches and compare them with a naive approach of directly querying the graph database. The aim of our work is to determine limiting factors of graph databases like Neo4j and we describe a novel solution to tackle these challenges. For this, we suggest a classification schema to differ between the complexity of a problem on a graph database. We evaluate our optimization approaches on a test system containing a knowledge graph derived biomedical publication data enriched with text mining data. This dense graph has more than 71M nodes and 850M relationships. The results are very encouraging and - depending on the problem - we were able to show a speedup of a factor between 44 and 3839.
Sparse Polynomial Interpolation Based on Diversification
Venue: arXiv cs.SC 2020
Year: 2020

We consider the problem of interpolating a sparse multivariate polynomial over a finite field, represented with a black box. Building on the algorithm of Ben-Or and Tiwari for interpolating polynomials over rings with characteristic zero, we develop a new Monte Carlo algorithm over the finite field by doing additional probes. To interpolate a polynomial $f\in F_q[x_1,\dots,x_n]$ with a partial degree bound $D$ and a term bound $T$, our new algorithm costs $O^\thicksim(nT\log ^2q+nT\sqrt{D}\log q)$ bit operations and uses $2(n+1)T$ probes to the black box. If $q\geq O(nT^2D)$, it has constant success rate to return the correct polynomial. Compared with previous algorithms over general finite field, our algorithm has better complexity in the parameters $n,T,D$ and is the first one to achieve the complexity of fractional power about $D$, while keeping linear in $n,T$. A key technique is a randomization which makes all coefficients of the unknown polynomial distinguishable, producing a diverse polynomial. This approach, called diversification, was proposed by Giesbrecht and Roche in 2011. Our algorithm interpolates each variable independently using $O(T)$ probes, and then uses the diversification to correlate terms in different images. At last, we get the exponents by solving the discrete logarithms and obtain coefficients by solving a linear system. We have implemented our algorithm in Maple. Experimental results shows that our algorithm can applied to sparse polynomials with large degree. We also analyze the success rate of the algorithm.
Sparse Polynomial Interpolation Based on Derivative
Venue: arXiv cs.SC 2020
Year: 2020

In this paper, we propose two new interpolation algorithms for sparse multivariate polynomials represented by a straight-line program(SLP). Both of our algorithms work over any finite fields $F_q$ with large characteristic. The first one is a Monte Carlo randomized algorithm. Its arithmetic complexity is linear in the number $T$ of non-zero terms of $f$, in the number $n$ of variables. If $q$ is $O((nTD)^{(1)})$, where $D$ is the partial degree bound, then our algorithm has better complexity than other existing algorithms. The second one is a deterministic algorithm. It has better complexity than existing deterministic algorithms over a field with large characteristic. Its arithmetic complexity is quadratic in $n,T,\log D$, i.e., quadratic in the size of the sparse representation. And we also show that the complexity of our deterministic algorithm is the same as the one of deterministic zero-testing of Bläser et al. for the polynomial given by an SLP over finite field (for large characteristic).
Unsupervised deep clustering for predictive texture pattern discovery in medical images
Venue: arXiv cs.CV 2020
Year: 2020

Predictive marker patterns in imaging data are a means to quantify disease and progression, but their identification is challenging, if the underlying biology is poorly understood. Here, we present a method to identify predictive texture patterns in medical images in an unsupervised way. Based on deep clustering networks, we simultaneously encode and cluster medical image patches in a low-dimensional latent space. The resulting clusters serve as features for disease staging, linking them to the underlying disease. We evaluate the method on 70 T1-weighted magnetic resonance images of patients with different stages of liver steatosis. The deep clustering approach is able to find predictive clusters with a stable ranking, differentiating between low and high steatosis with an F1-Score of 0.78.