OpenRaiser/Intern-Atlas huggingface dataset:
Ultra Reliable Communication via Optimum Power Allocation for HARQ Retransmission Schemes
Venue: arXiv cs.IT 2020
Year: 2020

In this work, we develop low complexity, optimal power allocation algorithms that would allow ultra reliable operation at any outage probability target with minimum power consumption in the finite blocklength regime by utilizing Karush-Kuhn-Tucker (KKT) conditions. In our setup, we assume that the transmitter does not know the channel state information (CSI). First, we show that achieving a very low packet outage probability by using an open loop setup requires extremely high power consumption. Thus, we resort to retransmission schemes as a solution, namely Automatic Repeat Request (ARQ), Chase Combining Hybrid ARQ (CC-HARQ) and Incremental Redundancy (IR) HARQ. Countrary to classical approaches, where it is optimal to allocate equal power with each transmission, we show that for operation in the ultra reliable regime (URR), the optimal strategy suggests transmission with incremental power in each round. Numerically, we evaluate the power gains of the proposed protocol. We show that the best power saving is given by IR-HARQ protocol. Further, we show that when compared to the one shot transmission, these protocols enable large average and maximum power gains. Finally, we show that the larger the number of transmissions is, the larger power gains will be attained.
PointTrackNet: An End-to-End Network For 3-D Object Detection and Tracking From Point Clouds
Venue: arXiv cs.CV 2020
Year: 2020

Recent machine learning-based multi-object tracking (MOT) frameworks are becoming popular for 3-D point clouds. Most traditional tracking approaches use filters (e.g., Kalman filter or particle filter) to predict object locations in a time sequence, however, they are vulnerable to extreme motion conditions, such as sudden braking and turning. In this letter, we propose PointTrackNet, an end-to-end 3-D object detection and tracking network, to generate foreground masks, 3-D bounding boxes, and point-wise tracking association displacements for each detected object. The network merely takes as input two adjacent point-cloud frames. Experimental results on the KITTI tracking dataset show competitive results over the state-of-the-arts, especially in the irregularly and rapidly changing scenarios.
Election in India: Polling in National Financial Switch
Venue: arXiv cs.CY 2020
Year: 2020

Indian voters from Kashmir to Kanyakumari select their representatives to form their parliament by going to polls. India's election is one of the largest democratic exercise in the world history. About 850 million eligible voters determine which political party or alliance will form the government and in turn, will serve as prime minister. Given the electoral rules of placing a polling place within 2 kilometers of every habitation, it comes as no surprise that is indeed a humongous task for the Election Commission of India (ECI). It sends around 11 million election workers through tough terrains to reach the last mile. This exercise also comes as ever growing expenditure for the ECI. This paper proposes the use of Automated Teller Machines (ATM) and Point Of Sale (POS) machines to be used to cover as much as urban, rural and semi-urban places possible given the wide network of National Financial Switch (NFS) and increase in connectivity through Digital India initiative. This would add to the use of the existing infrastructure to accommodate a free, fair and transparent election.
Algorithms for Fair Team Formation in Online Labour Marketplaces
Venue: arXiv cs.CY 2020
Year: 2020

As freelancing work keeps on growing almost everywhere due to a sharp decrease in communication costs and to the widespread of Internet-based labour marketplaces (e.g., guru.com, feelancer.com, mturk.com, upwork.com), many researchers and practitioners have started exploring the benefits of outsourcing and crowdsourcing. Since employers often use these platforms to find a group of workers to complete a specific task, researchers have focused their efforts on the study of team formation and matching algorithms and on the design of effective incentive schemes. Nevertheless, just recently, several concerns have been raised on possibly unfair biases introduced through the algorithms used to carry out these selection and matching procedures. For this reason, researchers have started studying the fairness of algorithms related to these online marketplaces, looking for intelligent ways to overcome the algorithmic bias that frequently arises. Broadly speaking, the aim is to guarantee that, for example, the process of hiring workers through the use of machine learning and algorithmic data analysis tools does not discriminate, even unintentionally, on grounds of nationality or gender. In this short paper, we define the Fair Team Formation problem in the following way: given an online labour marketplace where each worker possesses one or more skills, and where all workers are divided into two or more not overlapping classes (for examples, men and women), we want to design an algorithm that is able to find a team with all the skills needed to complete a given task, and that has the same number of people from all classes. We provide inapproximability results for the Fair Team Formation problem together with four algorithms for the problem itself. We also tested the effectiveness of our algorithmic solutions by performing experiments using real data from an online labor marketplace.
When showing your hand pays off: Announcing strategic intentions in Colonel Blotto games
Venue: arXiv cs.GT 2020
Year: 2020

In competitive adversarial environments, it is often advantageous to obfuscate one's strategies or capabilities. However, revealing one's strategic intentions may shift the dynamics of the competition in complex ways. Can it ever be advantageous to reveal strategic intentions to an opponent? In this paper, we consider three-stage Colonel Blotto games in which one player can choose whether or not to pre-commit resources to a single battlefield before play begins. This pre-commitment is public knowledge. In response, the opponent can either secure the battlefield by matching the pre-commitment with its own forces, or withdraw. In a two-player setting, we show that a weaker player never has an incentive to pre-commit any amount of resources to a battlefield regardless of how valuable it is. We then consider a three-player setting in which two players fight against a common adversary on separate fronts. Only one of the two players facing the adversary has the option of pre-committing. We find there are instances where this player benefits from pre-committing. The analysis indicates that under non-cooperative team settings and no possibility of forming alliances, there can be incentives to publicly announce one's strategic intentions to an adversary.
Workload Prediction of Business Processes -- An Approach Based on Process Mining and Recurrent Neural Networks
Venue: arXiv cs.DB 2020
Year: 2020

Recent advances in the interconnectedness and digitization of industrial machines, known as Industry 4.0, pave the way for new analytical techniques. Indeed, the availability and the richness of production-related data enables new data-driven methods. In this paper, we propose a process mining approach augmented with artificial intelligence that (1) reconstructs the historical workload of a company and (2) predicts the workload using neural networks. Our method relies on logs, representing the history of business processes related to manufacturing. These logs are used to quantify the supply and demand and are fed into a recurrent neural network model to predict customer orders. The corresponding activities to fulfill these orders are then sampled from history with a replay mechanism, based on criteria such as trace frequency and activities similarity. An evaluation and illustration of the method is performed on the administrative processes of Heraeus Materials SA. The workload prediction on a one-year test set achieves an MAPE score of 19% for a one-week forecast. The case study suggests a reasonable accuracy and confirms that a good understanding of the historical workload combined to articulated predictions are of great help for supporting management decisions and can decrease costs with better resources planning on a medium-term level.
Limitations of Greed: Influence Maximization in Undirected Networks Re-visited
Venue: arXiv cs.DS 2020
Year: 2020

We consider the influence maximization problem (selecting $k$ seeds in a network maximizing the expected total influence) on undirected graphs under the linear threshold model. On the one hand, we prove that the greedy algorithm always achieves a $(1 - (1 - 1/k)^k + Ω(1/k^3))$-approximation, showing that the greedy algorithm does slightly better on undirected graphs than the generic $(1- (1 - 1/k)^k)$ bound which also applies to directed graphs. On the other hand, we show that substantial improvement on this bound is impossible by presenting an example where the greedy algorithm can obtain at most a $(1- (1 - 1/k)^k + O(1/k^{0.2}))$ approximation. This result stands in contrast to the previous work on the independent cascade model. Like the linear threshold model, the greedy algorithm obtains a $(1-(1-1/k)^k)$-approximation on directed graphs in the independent cascade model. However, Khanna and Lucier showed that, in undirected graphs, the greedy algorithm performs substantially better: a $(1-(1-1/k)^k + c)$ approximation for constant $c > 0$. Our results show that, surprisingly, no such improvement occurs in the linear threshold model. Finally, we show that, under the linear threshold model, the approximation ratio $(1 - (1 - 1/k)^k)$ is tight if 1) the graph is directed or 2) the vertices are weighted. In other words, under either of these two settings, the greedy algorithm cannot achieve a $(1 - (1 - 1/k)^k + f(k))$-approximation for any positive function $f(k)$. The result in setting 2) is again in a sharp contrast to Khanna and Lucier's $(1 - (1 - 1/k)^k + c)$-approximation result for the independent cascade model, where the $(1 - (1 - 1/k)^k + c)$ approximation guarantee can be extended to the setting where vertices are weighted. We also discuss extensions to more generalized settings including those with edge-weighted graphs.
Algorithms for Optimizing Fleet Scheduling of Air Ambulances
Venue: arXiv cs.AI 2020
Year: 2020

Proper scheduling of air assets can be the difference between life and death for a patient. While poor scheduling can be incredibly problematic during hospital transfers, it can be potentially catastrophic in the case of a disaster. These issues are amplified in the case of an air emergency medical service (EMS) system where populations are dispersed, and resources are limited. There are exact methodologies existing for scheduling missions, although actual calculation times can be quite significant given a large enough problem space. For this research, known coordinates of air and health facilities were used in conjunction with a formulated integer linear programming model. This was the programmed through Gurobi so that performance could be compared against custom algorithmic solutions. Two methods were developed, one based on neighbourhood search and the other on Tabu search. While both were able to achieve results quite close to the Gurobi solution, the Tabu search outperformed the former algorithm. Additionally, it was able to do so in a greatly decreased time, with Gurobi actually being unable to resolve to optimal in larger examples. Parallel variations were also developed with the compute unified device architecture (CUDA), though did not improve the timing given the smaller sample size.
Trapping problem on star-type graphs with applications
Venue: arXiv cs.DM 2020
Year: 2020

The trapping problem on graph (or network) as a typical focus of great interest has attracted more attention from various science fields, including applied mathematics and theoretical computer science, in the past. Here, we first study this problem on an arbitrary graph and obtain the closed-form formula for calculating the theoretical lower bound of average trapping time ($ATT$), a quantity that evaluates trapping efficiency of graph in question, using methods from spectral graph theory. The results show that the choice of the trap's location has a significant influence on determining parameter $ATT$. As a result, we consider the problem on star-type graphs, a special graph family which will be introduced shortly, with a single trap $θ$ and then derive using probability generating functions the exact solution to quantity $ATT$. Our results suggest that all star-type graphs have most optimal trapping efficiency by achieving the corresponding theoretical lower bounds of $ATT$. More importantly, we further find that a given graph is most optimal only if its underlying structure is star-type when considering the trapping problem. At meantime, we also provide the upper bounds for $ATT$ of several graphs in terms of well-known Holder inequality, some of which are sharp. By using all the consequences obtained, one may be able to design better control scheme for complex networks from respect of trapping efficiency, to some extent, which are in well agreement with many other previous thoughts.
Type-2 Fuzzy Set based Hesitant Fuzzy Linguistic Term Sets for Linguistic Decision Making
Venue: arXiv cs.AI 2020
Year: 2020

Approaches based on computing with words find good applicability in decision making systems. Predominantly finding their basis in type-1 fuzzy sets, computing with words approaches employ type-1 fuzzy sets as semantics of the linguistic terms. However, type-2 fuzzy sets have been proven to be scientifically more appropriate to represent linguistic information in practical systems. They take into account both the intra-uncertainty as well as the inter-uncertainty in cases where the linguistic information comes from a group of experts. Hence in this paper, we propose to introduce linguistic terms whose semantics are denoted by interval type-2 fuzzy sets within the hesitant fuzzy linguistic term set framework, resulting in type-2 fuzzy sets based hesitant fuzzy linguistic term sets. We also introduce a novel method of computing type-2 fuzzy envelopes out of multiple interval type-2 fuzzy sets with trapezoidal membership functions. Furthermore, the proposed framework with interval type-2 fuzzy sets is applied on a supplier performance evaluation scenario. Since humans are predominantly involved in the entire process of supply chain, their feedback is crucial while deciding many factors. Towards the end of the paper, we compare our presented model with various existing models and demonstrate the advantages of the former.
On Certifying Robustness against Backdoor Attacks via Randomized Smoothing
Venue: arXiv cs.CR 2020
Year: 2020

Backdoor attack is a severe security threat to deep neural networks (DNNs). We envision that, like adversarial examples, there will be a cat-and-mouse game for backdoor attacks, i.e., new empirical defenses are developed to defend against backdoor attacks but they are soon broken by strong adaptive backdoor attacks. To prevent such cat-and-mouse game, we take the first step towards certified defenses against backdoor attacks. Specifically, in this work, we study the feasibility and effectiveness of certifying robustness against backdoor attacks using a recent technique called randomized smoothing. Randomized smoothing was originally developed to certify robustness against adversarial examples. We generalize randomized smoothing to defend against backdoor attacks. Our results show the theoretical feasibility of using randomized smoothing to certify robustness against backdoor attacks. However, we also find that existing randomized smoothing methods have limited effectiveness at defending against backdoor attacks, which highlight the needs of new theory and methods to certify robustness against backdoor attacks.
GLAS: Global-to-Local Safe Autonomy Synthesis for Multi-Robot Motion Planning with End-to-End Learning
Venue: arXiv cs.RO 2020
Year: 2020

We present GLAS: Global-to-Local Autonomy Synthesis, a provably-safe, automated distributed policy generation for multi-robot motion planning. Our approach combines the advantage of centralized planning of avoiding local minima with the advantage of decentralized controllers of scalability and distributed computation. In particular, our synthesized policies only require relative state information of nearby neighbors and obstacles, and compute a provably-safe action. Our approach has three major components: i) we generate demonstration trajectories using a global planner and extract local observations from them, ii) we use deep imitation learning to learn a decentralized policy that can run efficiently online, and iii) we introduce a novel differentiable safety module to ensure collision-free operation, thereby allowing for end-to-end policy training. Our numerical experiments demonstrate that our policies have a 20% higher success rate than optimal reciprocal collision avoidance, ORCA, across a wide range of robot and obstacle densities. We demonstrate our method on an aerial swarm, executing the policy on low-end microcontrollers in real-time.
Toward Predicting Success and Failure in CS2: A Mixed-Method Analysis
Venue: arXiv cs.OH 2020
Year: 2020

Factors driving success and failure in CS1 are the subject of much study but less so for CS2. This paper investigates the transition from CS1 to CS2 in search of leading indicators of success in CS2. Both CS1 and CS2 at the University of North Carolina Wilmington (UNCW) are taught in Python with annual enrollments of 300 and 150 respectively. In this paper, we report on the following research questions: 1) Are CS1 grades indicators of CS2 grades? 2) Does a quantitative relationship exist between CS2 course grade and a modified version of the SCS1 concept inventory? 3) What are the most challenging aspects of CS2, and how well does CS1 prepare students for CS2 from the student's perspective? We provide a quantitative analysis of 2300 CS1 and CS2 course grades from 2013--2019. In Spring 2019, we administered a modified version of the SCS1 concept inventory to 44 students in the first week of CS2. Further, 69 students completed an exit questionnaire at the conclusion of CS2 to gain qualitative student feedback on their challenges in CS2 and on how well CS1 prepared them for CS2. We find that 56% of students' grades were lower in CS2 than CS1, 18% improved their grades, and 26% earned the same grade. Of the changes, 62% were within one grade point. We find a statistically significant correlation between the modified SCS1 score and CS2 grade points. Students identify linked lists and class/object concepts among the most challenging. Student feedback on CS2 challenges and the adequacy of their CS1 preparations identify possible avenues for improving the CS1-CS2 transition.
Finding large matchings in 1-planar graphs of minimum degree 3
Venue: arXiv cs.CG 2020
Year: 2020

A matching is a set of edges without common endpoint. It was recently shown that every 1-planar graph (i.e., a graph that can be drawn in the plane with at most one crossing per edge) that has minimum degree 3 has a matching of size at least $\frac{n+12}{7}$, and this is tight for some graphs. The proof did not come with an algorithm to find the matching more efficiently than a general-purpose maximum-matching algorithm. In this paper, we give such an algorithm. More generally, we show that any matching that has no augmenting paths of length 9 or less has size at least $\frac{n+12}{7}$ in a 1-planar graph with minimum degree 3.
No computation without representation: Avoiding data and algorithm biases through diversity
Venue: arXiv cs.CY 2020
Year: 2020

The emergence and growth of research on issues of ethics in AI, and in particular algorithmic fairness, has roots in an essential observation that structural inequalities in society are reflected in the data used to train predictive models and in the design of objective functions. While research aiming to mitigate these issues is inherently interdisciplinary, the design of unbiased algorithms and fair socio-technical systems are key desired outcomes which depend on practitioners from the fields of data science and computing. However, these computing fields broadly also suffer from the same under-representation issues that are found in the datasets we analyze. This disconnect affects the design of both the desired outcomes and metrics by which we measure success. If the ethical AI research community accepts this, we tacitly endorse the status quo and contradict the goals of non-discrimination and equity which work on algorithmic fairness, accountability, and transparency seeks to address. Therefore, we advocate in this work for diversifying computing as a core priority of the field and our efforts to achieve ethical AI practices. We draw connections between the lack of diversity within academic and professional computing fields and the type and breadth of the biases encountered in datasets, machine learning models, problem formulations, and interpretation of results. Examining the current fairness/ethics in AI literature, we highlight cases where this lack of diverse perspectives has been foundational to the inequity in treatment of underrepresented and protected group data. We also look to other professional communities, such as in law and health, where disparities have been reduced both in the educational diversity of trainees and among professional practices. We use these lessons to develop recommendations that provide concrete steps for the computing community to increase diversity.
CrossWOZ: A Large-Scale Chinese Cross-Domain Task-Oriented Dialogue Dataset
Venue: arXiv cs.CL 2020
Year: 2020

To advance multi-domain (cross-domain) dialogue modeling as well as alleviate the shortage of Chinese task-oriented datasets, we propose CrossWOZ, the first large-scale Chinese Cross-Domain Wizard-of-Oz task-oriented dataset. It contains 6K dialogue sessions and 102K utterances for 5 domains, including hotel, restaurant, attraction, metro, and taxi. Moreover, the corpus contains rich annotation of dialogue states and dialogue acts at both user and system sides. About 60% of the dialogues have cross-domain user goals that favor inter-domain dependency and encourage natural transition across domains in conversation. We also provide a user simulator and several benchmark models for pipelined task-oriented dialogue systems, which will facilitate researchers to compare and evaluate their models on this corpus. The large size and rich annotation of CrossWOZ make it suitable to investigate a variety of tasks in cross-domain dialogue modeling, such as dialogue state tracking, policy learning, user simulation, etc.