OpenRaiser/Intern-Atlas huggingface dataset:
Local Distance Constrained Bribery in Voting
Venue: arXiv cs.GT 2020
Year: 2020

Studying complexity of various bribery problems has been one of the main research focus in computational social choice. In all the models of bribery studied so far, the briber has to pay every voter some amount of money depending on what the briber wants the voter to report and the briber has some budget at her disposal. Although these models successfully capture many real world applications, in many other scenarios, the voters may be unwilling to deviate too much from their true preferences. In this paper, we study the computational complexity of the problem of finding a preference profile which is as close to the true preference profile as possible and still achieves the briber's goal subject to budget constraints. We call this problem Optimal Bribery. We consider three important measures of distances, namely, swap distance, footrule distance, and maximum displacement distance, and resolve the complexity of the optimal bribery problem for many common voting rules. We show that the problem is polynomial time solvable for the plurality and veto voting rules for all the three measures of distance. On the other hand, we prove that the problem is NP-complete for a class of scoring rules which includes the Borda voting rule, maximin, Copeland$^α$ for any $α\in[0,1]$, and Bucklin voting rules for all the three measures of distance even when the distance allowed per voter is $1$ for the swap and maximum displacement distances and $2$ for the footrule distance even without the budget constraints (which corresponds to having an infinite budget). For the $k$-approval voting rule for any constant $k>1$ and the simplified Bucklin voting rule, we show that the problem is NP-complete for the swap distance even when the distance allowed is $2$ and for the footrule distance even when the distance allowed is $4$ even without the budget constraints.
3D Contouring for Breast Tumor in Sonography
Venue: arXiv cs.CV 2020
Year: 2020

Malignant and benign breast tumors present differently in their shape and size on sonography. Morphological information provided by tumor contours are important in clinical diagnosis. However, ultrasound images contain noises and tissue texture; clinical diagnosis thus highly depends on the experience of physicians. The manual way to sketch three-dimensional (3D) contours of breast tumor is a time-consuming and complicate task. If automatic contouring could provide a precise breast tumor contour that might assist physicians in making an accurate diagnosis. This study presents an efficient method for automatically contouring breast tumors in 3D sonography. The proposed method utilizes an efficient segmentation procedure, i.e. level-set method (LSM), to automatic detect contours of breast tumors. This study evaluates 20 cases comprising ten benign and ten malignant tumors. The results of computer simulation reveal that the proposed 3D segmentation method provides robust contouring for breast tumor on ultrasound images. This approach consistently obtains contours similar to those obtained by manual contouring of the breast tumor and can save much of the time required to sketch precise contours.
Stiffness: A New Perspective on Generalization in Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

In this paper we develop a new perspective on generalization of neural networks by proposing and investigating the concept of a neural network stiffness. We measure how stiff a network is by looking at how a small gradient step in the network's parameters on one example affects the loss on another example. Higher stiffness suggests that a network is learning features that generalize. In particular, we study how stiffness depends on 1) class membership, 2) distance between data points in the input space, 3) training iteration, and 4) learning rate. We present experiments on MNIST, FASHION MNIST, and CIFAR-10/100 using fully-connected and convolutional neural networks, as well as on a transformer-based NLP model. We demonstrate the connection between stiffness and generalization, and observe its dependence on learning rate. When training on CIFAR-100, the stiffness matrix exhibits a coarse-grained behavior indicative of the model's awareness of super-class membership. In addition, we measure how stiffness between two data points depends on their mutual input-space distance, and establish the concept of a dynamical critical length -- a distance below which a parameter update based on a data point influences its neighbors.
CoCoNet: A Collaborative Convolutional Network
Venue: arXiv cs.CV 2020
Year: 2020

We present an end-to-end deep network for fine-grained visual categorization called Collaborative Convolutional Network (CoCoNet). The network uses a collaborative layer after the convolutional layers to represent an image as an optimal weighted collaboration of features learned from training samples as a whole rather than one at a time. This gives CoCoNet more power to encode the fine-grained nature of the data with limited samples. We perform a detailed study of the performance with 1-stage and 2-stage transfer learning. The ablation study shows that the proposed method outperforms its constituent parts consistently. CoCoNet also outperforms few state-of-the-art competing methods. Experiments have been performed on the fine-grained bird species classification problem as a representative example, but the method may be applied to other similar tasks. We also introduce a new public dataset for fine-grained species recognition, that of Indian endemic birds and have reported initial results on it.
On the Units of GANs (Extended Abstract)
Venue: arXiv cs.LG 2020
Year: 2020

Generative Adversarial Networks (GANs) have achieved impressive results for many real-world applications. As an active research topic, many GAN variants have emerged with improvements in sample quality and training stability. However, visualization and understanding of GANs is largely missing. How does a GAN represent our visual world internally? What causes the artifacts in GAN results? How do architectural choices affect GAN learning? Answering such questions could enable us to develop new insights and better models. In this work, we present an analytic framework to visualize and understand GANs at the unit-, object-, and scene-level. We first identify a group of interpretable units that are closely related to concepts with a segmentation-based network dissection method. We quantify the causal effect of interpretable units by measuring the ability of interventions to control objects in the output. Finally, we examine the contextual relationship between these units and their surrounding by inserting the discovered concepts into new images. We show several practical applications enabled by our framework, from comparing internal representations across different layers, models, and datasets, to improving GANs by locating and removing artifact-causing units, to interactively manipulating objects in the scene. We will open source our interactive tools to help researchers and practitioners better understand their models.
Compressed Domain Image Classification Using a Dynamic-Rate Neural Network
Venue: arXiv cs.CV 2020
Year: 2020

Compressed domain image classification performs classification directly on compressive measurements acquired from the single-pixel camera, bypassing the image reconstruction step. It is of great importance for extending high-speed object detection and classification beyond the visible spectrum in a cost-effective manner especially for resource-limited platforms. Previous neural network methods require training a dedicated neural network for each different measurement rate (MR), which is costly in computation and storage. In this work, we develop an efficient training scheme that provides a neural network with dynamic-rate property, where a single neural network is capable of classifying over any MR within the range of interest with a given sensing matrix. This training scheme uses only a few selected MRs for training and the trained neural network is valid over the full range of MRs of interest. We demonstrate the performance of the dynamic-rate neural network on datasets of MNIST, CIFAR-10, Fashion-MNIST, COIL-100, and show that it generates approximately equal performance at each MR as that of a single-rate neural network valid only for one MR. Robustness to noise of the dynamic-rate model is also demonstrated. The dynamic-rate training scheme can be regarded as a general approach compatible with different types of sensing matrices, various neural network architectures, and is a valuable step towards wider adoption of compressive inference techniques and other compressive sensing related tasks via neural networks.
Unique perfect matchings, forbidden transitions and proof nets for linear logic with Mix
Venue: arXiv cs.LO 2020
Year: 2020

This paper establishes a bridge between linear logic and mainstream graph theory, building on previous work by Retoré (2003). We show that the problem of correctness for MLL+Mix proof nets is equivalent to the problem of uniqueness of a perfect matching. By applying matching theory, we obtain new results for MLL+Mix proof nets: a linear-time correctness criterion, a quasi-linear sequentialization algorithm, and a characterization of the sub-polynomial complexity of the correctness problem. We also use graph algorithms to compute the dependency relation of Bagnol et al. (2015) and the kingdom ordering of Bellin (1997), and relate them to the notion of blossom which is central to combinatorial maximum matching algorithms. In this journal version, we have added an explanation of Retoré's "RB-graphs" in terms of a general construction on graphs with forbidden transitions. In fact, it is by analyzing RB-graphs that we arrived at this construction, and thus obtained a polynomial-time algorithm for finding trails avoiding forbidden transitions; the latter is among the material covered in another paper by the author focusing on graph theory (arXiv:1901.07028).
Tensorized Embedding Layers for Efficient Model Compression
Venue: arXiv cs.CL 2020
Year: 2020

The embedding layers transforming input words into real vectors are the key components of deep neural networks used in natural language processing. However, when the vocabulary is large, the corresponding weight matrices can be enormous, which precludes their deployment in a limited resource setting. We introduce a novel way of parametrizing embedding layers based on the Tensor Train (TT) decomposition, which allows compressing the model significantly at the cost of a negligible drop or even a slight gain in performance. We evaluate our method on a wide range of benchmarks in natural language processing and analyze the trade-off between performance and compression ratios for a wide range of architectures, from MLPs to LSTMs and Transformers.
Zipper Stack: Shadow Stacks Without Shadow
Venue: arXiv cs.CR 2020
Year: 2020

Return-Oriented Programming (ROP) is a typical attack technique that exploits return addresses to abuse existing code repeatedly. Most of the current return address protecting mechanisms (also known as the Backward-Edge Control-Flow Integrity) work only in limited threat models. For example, the attacker cannot break memory isolation, or the attacker has no knowledge of a secret key or random values. This paper presents a novel, lightweight mechanism protecting return addresses, Zipper Stack, which authenticates all return addresses by a chain structure using cryptographic message authentication codes (MACs). This innovative design can defend against the most powerful attackers who have full control over the program's memory and even know the secret key of the MAC function. This threat model is stronger than the one used in related work. At the same time, it produces low-performance overhead. We implemented Zipper Stack by extending the RISC-V instruction set architecture, and the evaluation on FPGA shows that the performance overhead of Zipper Stack is only 1.86%. Thus, we think Zipper Stack is suitable for actual deployment.
Universal Lemmatizer: A Sequence to Sequence Model for Lemmatizing Universal Dependencies Treebanks
Venue: arXiv cs.CL 2020
Year: 2020

In this paper we present a novel lemmatization method based on a sequence-to-sequence neural network architecture and morphosyntactic context representation. In the proposed method, our context-sensitive lemmatizer generates the lemma one character at a time based on the surface form characters and its morphosyntactic features obtained from a morphological tagger. We argue that a sliding window context representation suffers from sparseness, while in majority of cases the morphosyntactic features of a word bring enough information to resolve lemma ambiguities while keeping the context representation dense and more practical for machine learning systems. Additionally, we study two different data augmentation methods utilizing autoencoder training and morphological transducers especially beneficial for low resource languages. We evaluate our lemmatizer on 52 different languages and 76 different treebanks, showing that our system outperforms all latest baseline systems. Compared to the best overall baseline, UDPipe Future, our system outperforms it on 62 out of 76 treebanks reducing errors on average by 19% relative. The lemmatizer together with all trained models is made available as a part of the Turku-neural-parsing-pipeline under the Apache 2.0 license.
A Moving Target Defense for Securing Cyber-Physical Systems
Venue: arXiv cs.SY 2020
Year: 2020

This article considers the design and analysis of multiple moving target defenses for recognizing and isolating attacks on cyber-physical systems. We consider attackers who perform integrity attacks on a set of sensors and actuators in a control system. In such cases, a model aware adversary can carefully design attack vectors to bypass bad data detection and identification filters while causing damage to the control system. To counter such an attacker, we propose the moving target defense which introduces stochastic, time-varying parameters in the control system. The underlying random dynamics of the system limit an attacker's model knowledge and inhibits his/her ability to construct stealthy attack sequences. Moreover, the time-varying nature of the dynamics thwarts adaptive adversaries. We explore three main designs. First, we consider a hybrid system where parameters within the existing plant are switched among multiple modes. We demonstrate how such an approach can enable both the detection and identification of malicious nodes. Next, we investigate the addition of an extended system with dynamics that are coupled to the original plant but do not affect system performance. An attack on the original system will affect the authenticating subsystem and in turn be revealed by a set of sensors measuring the extended plant. Lastly, we propose the use of sensor nonlinearities to enhance the effectiveness of the moving target defense. The nonlinear dynamics act to conceal normal operational behavior from an attacker who has tampered with the system state, further hindering an attacker's ability to glean information about the time-varying dynamics. In all cases mechanisms for analysis and design are proposed. Finally, we analyze attack detectability for each moving target defense by investigating expected lower bounds on the detection statistic. Our contributions are tested via simulation.
A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints
Venue: arXiv cs.CV 2020
Year: 2020

A popular paradigm for 3D point cloud registration is by extracting 3D keypoint correspondences, then estimating the registration function from the correspondences using a robust algorithm. However, many existing 3D keypoint techniques tend to produce large proportions of erroneous correspondences or outliers, which significantly increases the cost of robust estimation. An alternative approach is to directly search for the subset of correspondences that are pairwise consistent, without optimising the registration function. This gives rise to the combinatorial problem of matching with pairwise constraints. In this paper, we propose a very efficient maximum clique algorithm to solve matching with pairwise constraints. Our technique combines tree searching with efficient bounding and pruning based on graph colouring. We demonstrate that, despite the theoretical intractability, many real problem instances can be solved exactly and quickly (seconds to minutes) with our algorithm, which makes our approach an excellent alternative to standard robust techniques for 3D registration.
Restructuring Conversations using Discourse Relations for Zero-shot Abstractive Dialogue Summarization
Venue: arXiv cs.CL 2020
Year: 2020

Dialogue summarization is a challenging problem due to the informal and unstructured nature of conversational data. Recent advances in abstractive summarization have been focused on data-hungry neural models and adapting these models to a new domain requires the availability of domain-specific manually annotated corpus created by linguistic experts. We propose a zero-shot abstractive dialogue summarization method that uses discourse relations to provide structure to conversations, and then uses an out-of-the-box document summarization model to create final summaries. Experiments on the AMI and ICSI meeting corpus, with document summarization models like PGN and BART, shows that our method improves the ROGUE score by up to 3 points, and even performs competitively against other state-of-the-art methods.
Partisanship, Propaganda and Post-Truth Politics: Quantifying Impact in Online Debate
Venue: arXiv cs.CY 2020
Year: 2020

The recent past has highlighted the influential role of social networks and online media in shaping public debate on current affairs and political issues. This paper is focused on studying the role of politically-motivated actors and their strategies for influencing and manipulating public opinion online: partisan media, state-backed propaganda, and post-truth politics. In particular, we present quantitative research on the presence and impact of these three `Ps' in online Twitter debates in two contexts: (i) the run up to the UK EU membership referendum (`Brexit'); and (ii) the information operations of Russia-backed online troll accounts. We first compare the impact of highly partisan versus mainstream media during the Brexit referendum, specifically comparing tweets by half a million `leave' and `remain' supporters. Next, online propaganda strategies are examined, specifically left- and right-wing troll accounts. Lastly, we study the impact of misleading claims made by the political leaders of the leave and remain campaigns. This is then compared to the impact of the Russia-backed partisan media and propaganda accounts during the referendum. In particular, just two of the many misleading claims made by politicians during the referendum were found to be cited in 4.6 times more tweets than the 7,103 tweets related to Russia Today and Sputnik and in 10.2 times more tweets than the 3,200 Brexit-related tweets by the Russian troll accounts.
Information-theoretic and algorithmic thresholds for group testing
Venue: arXiv cs.DM 2020
Year: 2020

In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [Aldridge et al.\ 2016] the individuals are assigned to test groups randomly, with every individual joining an equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [Aldridge et al.\ 2014, Johnson et al.\ 2019].
Information Flow in Computational Systems
Venue: arXiv cs.IT 2020
Year: 2020

We develop a theoretical framework for defining and identifying flows of information in computational systems. Here, a computational system is assumed to be a directed graph, with "clocked" nodes that send transmissions to each other along the edges of the graph at discrete points in time. We are interested in a definition that captures the dynamic flow of information about a specific message, and which guarantees an unbroken "information path" between appropriately defined inputs and outputs in the directed graph. Prior measures, including those based on Granger Causality and Directed Information, fail to provide clear assumptions and guarantees about when they correctly reflect information flow about a message. We take a systematic approach---iterating through candidate definitions and counterexamples---to arrive at a definition for information flow that is based on conditional mutual information, and which satisfies desirable properties, including the existence of information paths. Finally, we describe how information flow might be detected in a noiseless setting, and provide an algorithm to identify information paths on the time-unrolled graph of a computational system.
Are Mobility Management Solutions Ready for 5G and Beyond?
Venue: arXiv cs.NI 2020
Year: 2020

Enabling users to move to different geographical locations within a network and still be able to maintain their connectivity and most essentially, continuity of service, is what makes any wireless network ubiquitous. Whilst challenging, modern day wireless networks, such as 3GPP-LTE, provision satisfactory mobility management (MM) performance. However, it is estimated that the number of mobile subscriptions will approximately touch 9 billion and the amount of data traffic will expand by 5 times in 2024 as compared to 2018. Further, it is expected that this trend of exponential growth will be maintained well into the future. To cope with such an exponential increase in cellular traffic and users alongside a burgeoning demand for higher Quality of Service (QoS), the future networks are expected to be highly dense and heterogeneous. This will severely challenge the existing MM solutions and ultimately render them ineffective as they will not be able to provide the required reliability, flexibility, and scalability. Consequently, to serve the 5G and beyond 5G networks, a new perspective to MM is required. Hence, in this article we present a novel discussion of the functional requirements from MM strategies for these networks. We present a novel qualitative assessment of the state-of-the-art mechanisms based on their ability to satisfy the reliability, flexibility and scalability criteria for future MM strategies. We then present a study detailing the research challenges that exist in the design and implementation of MM strategies for 5G and beyond networks. Further, we chart out the potential MM solutions and the associated capabilities they offer to tackle the persistent challenges. We conclude this paper with a vision for the 5G and beyond MM mechanisms.