OpenRaiser/Intern-Atlas huggingface dataset:
AutoQ: Automated Kernel-Wise Neural Network Quantization
Venue: arXiv cs.LG 2020
Year: 2020

Network quantization is one of the most hardware friendly techniques to enable the deployment of convolutional neural networks (CNNs) on low-power mobile devices. Recent network quantization techniques quantize each weight kernel in a convolutional layer independently for higher inference accuracy, since the weight kernels in a layer exhibit different variances and hence have different amounts of redundancy. The quantization bitwidth or bit number (QBN) directly decides the inference accuracy, latency, energy and hardware overhead. To effectively reduce the redundancy and accelerate CNN inferences, various weight kernels should be quantized with different QBNs. However, prior works use only one QBN to quantize each convolutional layer or the entire CNN, because the design space of searching a QBN for each weight kernel is too large. The hand-crafted heuristic of the kernel-wise QBN search is so sophisticated that domain experts can obtain only sub-optimal results. It is difficult for even deep reinforcement learning (DRL) Deep Deterministic Policy Gradient (DDPG)-based agents to find a kernel-wise QBN configuration that can achieve reasonable inference accuracy. In this paper, we propose a hierarchical-DRL-based kernel-wise network quantization technique, AutoQ, to automatically search a QBN for each weight kernel, and choose another QBN for each activation layer. Compared to the models quantized by the state-of-the-art DRL-based schemes, on average, the same models quantized by AutoQ reduce the inference latency by 54.06\%, and decrease the inference energy consumption by 50.69\%, while achieving the same inference accuracy.
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership
Venue: arXiv cs.LO 2020
Year: 2020

We study two extensions of FO2[<], first-order logic interpreted in finite words, in which formulas are restricted to use only two variables. We adjoin to this language two-variable atomic formulas that say, "the letter $a$ appears between positions $x$ and $y$" and "the factor $u$ appears between positions $x$ and $y$". These are, in a sense, the simplest properties that are not expressible using only two variables. We present several logics, both first-order and temporal, that have the same expressive power, and find matching lower and upper bounds for the complexity of satisfiability for each of these formulations. We give effective conditions, in terms of the syntactic monoid of a regular language, for a property to be expressible in these logics. This algebraic analysis allows us to prove, among other things, that our new logics have strictly less expressive power than full first-order logic FO[<]. Our proofs required the development of novel techniques concerning factorizations of words.
Electing a committee with dominance constraints
Venue: arXiv cs.GT 2020
Year: 2020

We consider the problem of electing a committee of $k$ candidates, subject to some constraints as to what this committee is supposed to look like. In our framework, the candidates are given labels as an abstraction of a politician's religion, a film's genre, a song's language, or other attribute, and the election outcome is constrained by interval constraints -- of the form "Between 3 and 5 candidates with label X" -- and dominance constraints -- "At least as many candidates with label X as with label Y". The problem is, what shall we do if the committee selected by a given voting rule fails these constraints? In this paper we argue how the logic underlying weakly-separable and best-$k$ rules can be extended into an ordering of committees, and study the question of how to select the best valid committee with respect to this order. The problem is NP-hard, but we show the existence of a polynomial time solution in the case of tree-like constraints, and a fixed-parameter tractable algorithm for the general case.
Limited Lookahead in Imperfect-Information Games
Venue: arXiv cs.GT 2020
Year: 2020

Limited lookahead has been studied for decades in perfect-information games. We initiate a new direction via two simultaneous deviation points: generalization to imperfect-information games and a game-theoretic approach. We study how one should act when facing an opponent whose lookahead is limited. We study this for opponents that differ based on their lookahead depth, based on whether they, too, have imperfect information, and based on how they break ties. We characterize the hardness of finding a Nash equilibrium or an optimal commitment strategy for either player, showing that in some of these variations the problem can be solved in polynomial time while in others it is PPAD-hard, NP-hard, or inapproximable. We proceed to design algorithms for computing optimal commitment strategies---for when the opponent breaks ties favorably, according to a fixed rule, or adversarially. We then experimentally investigate the impact of limited lookahead. The limited-lookahead player often obtains the value of the game if she knows the expected values of nodes in the game tree for some equilibrium---but we prove this is not sufficient in general. Finally, we study the impact of noise in those estimates and different lookahead depths.
Modeling and Analysis of Data Harvesting Architecture based on Unmanned Aerial Vehicles
Venue: arXiv cs.IT 2020
Year: 2020

This paper explores an emerging wireless Internet-of-things (IoT) architecture based on unmanned aerial vehicles (UAVs). We consider a network where a fleet of UAVs at a fixed altitude flies on planned trajectories and IoT devices on the ground are scheduled to transmit their data to the UAVs when the latter are nearby. In such a system, the UAVs' motion triggers the uplink transmissions of the IoT devices. As a result, network performance is determined by the geometric and dynamic characteristics of the system. We propose a joint stationary model for UAVs and IoT devices and then evaluate the interference, the coverage probability, and the data rate of the typical UAV. To assess the harvesting capability of the proposed architecture, we derive a formula for the amount of data uploaded from each IoT device to a UAV. We also establish a linear relationship between the UAV coverage and the harvesting capability of the network, which provides insights into the design of the proposed harvesting scheme. In addition, we use our analytical results to numerically show that there exists a trade-off between the uploaded data and the size of the IoT scheduling window. Specifically, for a given UAV and IoT geometry, there exists an optimal scheduling window that maximizes the harvesting capability of the proposed network.
Beating Treewidth for Average-Case Subgraph Isomorphism
Venue: arXiv cs.CC 2020
Year: 2020

For any fixed graph $G$, the subgraph isomorphism problem asks whether an $n$-vertex input graph has a subgraph isomorphic to $G$. A well-known algorithm of Alon, Yuster and Zwick (1995) efficiently reduces this to the "colored" version of the problem, denoted $G$-$\mathsf{SUB}$, and then solves $G$-$\mathsf{SUB}$ in time $O(n^{tw(G)+1})$ where $tw(G)$ is the treewidth of $G$. Marx (2010) conjectured that $G$-$\mathsf{SUB}$ requires time $Ω(n^{\mathrm{const}\cdot tw(G)})$ and, assuming the Exponential Time Hypothesis, proved a lower bound of $Ω(n^{\mathrm{const}\cdot emb(G)})$ for a certain graph parameter $emb(G) \ge Ω(tw(G)/\log tw(G))$. With respect to the size of $\mathrm{AC}^0$ circuits solving $G$-$\mathsf{SUB}$ in the average case, Li, Razborov and Rossman (2017) proved (unconditional) upper and lower bounds of $O(n^{2κ(G)+\mathrm{const}})$ and $Ω(n^{κ(G)})$ for a different graph parameter $κ(G) \ge Ω(tw(G)/\log tw(G))$. Our contributions are as follows. First, we prove that $emb(G)$ is $O(κ(G))$ for all graphs $G$. Next, we show that $κ(G)$ can be asymptotically less than $tw(G)$; for example, if $G$ is a hypercube then $κ(G)$ is $Θ\big(tw(G)\big/\sqrt{\log tw(G)}\big)$. This implies that the average-case complexity of $G$-$\mathsf{SUB}$ is $n^{o(tw(G))}$ when $G$ is a hypercube. Finally, we construct $\mathrm{AC}^0$ circuits of size $O(n^{κ(G)+\mathrm{const}})$ that solve $G$-$\mathsf{SUB}$ in the average case, closing the gap between the upper and lower bounds of Li et al.
Tik-Tok: The Utility of Packet Timing in Website Fingerprinting Attacks
Venue: arXiv cs.CR 2020
Year: 2020

A passive local eavesdropper can leverage Website Fingerprinting (WF) to deanonymize the web browsing activity of Tor users. The value of timing information to WF has often been discounted in recent works due to the volatility of low-level timing information. In this paper, we more carefully examine the extent to which packet timing can be used to facilitate WF attacks. We first propose a new set of timing-related features based on burst-level characteristics to further identify more ways that timing patterns could be used by classifiers to identify sites. Then we evaluate the effectiveness of both raw timing and directional timing which is a combination of raw timing and direction in a deep-learning-based WF attack. Our closed-world evaluation shows that directional timing performs best in most of the settings we explored, achieving: (i) 98.4% in undefended Tor traffic; (ii) 93.5% on WTF-PAD traffic, several points higher than when only directional information is used; and (iii) 64.7% against onion sites, 12% higher than using only direction. Further evaluations in the open-world setting show small increases in both precision (+2%) and recall (+6%) with directional-timing on WTF-PAD traffic. To further investigate the value of timing information, we perform an information leakage analysis on our proposed handcrafted features. Our results show that while timing features leak less information than directional features, the information contained in each feature is mutually exclusive to one another and can thus improve the robustness of a classifier.
Improved efficiency for covering codes matching the sphere-covering bound
Venue: arXiv cs.IT 2020
Year: 2020

A covering code is a subset $\mathcal{C} \subseteq \{0,1\}^n$ with the property that any $z \in \{0,1\}^n$ is close to some $c \in \mathcal{C}$ in Hamming distance. For every $ε,δ>0$, we show a construction of a family of codes with relative covering radius $δ+ ε$ and rate $1 - \mathrm{H}(δ) $ with block length at most $\exp(O((1/ε) \log (1/ε)))$ for every $ε> 0$. This improves upon a folklore construction which only guaranteed codes of block length $\exp(1/ε^2)$. The main idea behind this proof is to find a distribution on codes with relatively small support such that most of these codes have good covering properties.
Learning efficient haptic shape exploration with a rigid tactile sensor array
Venue: arXiv cs.RO 2020
Year: 2020

Haptic exploration is a key skill for both robots and humans to discriminate and handle unknown objects or to recognize familiar objects. Its active nature is evident in humans who from early on reliably acquire sophisticated sensory-motor capabilities for active exploratory touch and directed manual exploration that associates surfaces and object properties with their spatial locations. This is in stark contrast to robotics. In this field, the relative lack of good real-world interaction models - along with very restricted sensors and a scarcity of suitable training data to leverage machine learning methods - has so far rendered haptic exploration a largely underdeveloped skill. In the present work, we connect recent advances in recurrent models of visual attention with previous insights about the organisation of human haptic search behavior, exploratory procedures and haptic glances for a novel architecture that learns a generative model of haptic exploration in a simulated three-dimensional environment. The proposed algorithm simultaneously optimizes main perception-action loop components: feature extraction, integration of features over time, and the control strategy, while continuously acquiring data online. We perform a multi-module neural network training, including a feature extractor and a recurrent neural network module aiding pose control for storing and combining sequential sensory data. The resulting haptic meta-controller for the rigid $16 \times 16$ tactile sensor array moving in a physics-driven simulation environment, called the Haptic Attention Model, performs a sequence of haptic glances, and outputs corresponding force measurements. The resulting method has been successfully tested with four different objects. It achieved results close to $100 \%$ while performing object contour exploration that has been optimized for its own sensor morphology.
Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model
Venue: arXiv cs.CR 2020
Year: 2020

The famous Fiat-Shamir transformation turns any public-coin three-round interactive proof, i.e., any so-called sigma-protocol, into a non-interactive proof in the random-oracle model. We study this transformation in the setting of a quantum adversary that in particular may query the random oracle in quantum superposition. Our main result is a generic reduction that transforms any quantum dishonest prover attacking the Fiat-Shamir transformation in the quantum random-oracle model into a similarly successful quantum dishonest prover attacking the underlying sigma-protocol (in the standard model). Applied to the standard soundness and proof-of-knowledge definitions, our reduction implies that both these security properties, in both the computational and the statistical variant, are preserved under the Fiat-Shamir transformation even when allowing quantum attacks. Our result improves and completes the partial results that have been known so far, but it also proves wrong certain claims made in the literature. In the context of post-quantum secure signature schemes, our results imply that for any sigma-protocol that is a proof-of-knowledge against quantum dishonest provers (and that satisfies some additional natural properties), the corresponding Fiat-Shamir signature scheme is secure in the quantum random-oracle model. For example, we can conclude that the non-optimized version of Fish, which is the bare Fiat-Shamir variant of the NIST candidate Picnic, is secure in the quantum random-oracle model.
Federated Heavy Hitters Discovery with Differential Privacy
Venue: arXiv cs.CR 2020
Year: 2020

The discovery of heavy hitters (most frequent items) in user-generated data streams drives improvements in the app and web ecosystems, but can incur substantial privacy risks if not done with care. To address these risks, we propose a distributed and privacy-preserving algorithm for discovering the heavy hitters in a population of user-generated data streams. We leverage the sampling and thresholding properties of our distributed algorithm to prove that it is inherently differentially private, without requiring additional noise. We also examine the trade-off between privacy and utility, and show that our algorithm provides excellent utility while also achieving strong privacy guarantees. A significant advantage of this approach is that it eliminates the need to centralize raw data while also avoiding the significant loss in utility incurred by local differential privacy. We validate our findings both theoretically, using worst-case analyses, and practically, using a Twitter dataset with 1.6M tweets and over 650k users. Finally, we carefully compare our approach to Apple's local differential privacy method for discovering heavy hitters.
Are Few-Shot Learning Benchmarks too Simple ? Solving them without Task Supervision at Test-Time
Venue: arXiv cs.LG 2020
Year: 2020

We show that several popular few-shot learning benchmarks can be solved with varying degrees of success without using support set Labels at Test-time (LT). To this end, we introduce a new baseline called Centroid Networks, a modification of Prototypical Networks in which the support set labels are hidden from the method at test-time and have to be recovered through clustering. A benchmark that can be solved perfectly without LT does not require proper task adaptation and is therefore inadequate for evaluating few-shot methods. In practice, most benchmarks cannot be solved perfectly without LT, but running our baseline on any new combinations of architectures and datasets gives insights on the baseline performance to be expected from leveraging a good representation, before any adaptation to the test-time labels.
Discriminative Pattern Mining for Breast Cancer Histopathology Image Classification via Fully Convolutional Autoencoder
Venue: arXiv cs.CV 2020
Year: 2020

Accurate diagnosis of breast cancer in histopathology images is challenging due to the heterogeneity of cancer cell growth as well as of a variety of benign breast tissue proliferative lesions. In this paper, we propose a practical and self-interpretable invasive cancer diagnosis solution. With minimum annotation information, the proposed method mines contrast patterns between normal and malignant images in unsupervised manner and generates a probability map of abnormalities to verify its reasoning. Particularly, a fully convolutional autoencoder is used to learn the dominant structural patterns among normal image patches. Patches that do not share the characteristics of this normal population are detected and analyzed by one-class support vector machine and 1-layer neural network. We apply the proposed method to a public breast cancer image set. Our results, in consultation with a senior pathologist, demonstrate that the proposed method outperforms existing methods. The obtained probability map could benefit the pathology practice by providing visualized verification data and potentially leads to a better understanding of data-driven diagnosis solutions.
Edge Federation: Towards an Integrated Service Provisioning Model
Venue: arXiv cs.NI 2020
Year: 2020

Edge computing is a promising computing paradigm for pushing the cloud service to the network edge. To this end, edge infrastructure providers (EIPs) need to bring computation and storage resources to the network edge and allow edge service providers (ESPs) to provision latency-critical services to users. Currently, EIPs prefer to establish a series of private edge-computing environments to serve specific requirements of users. This kind of resource provisioning mechanism severely limits the development and spread of edge computing for serving diverse user requirements. To this end, we propose an integrated resource provisioning model, named edge federation, to seamlessly realize the resource cooperation and service provisioning across standalone edge computing providers and clouds. To efficiently schedule and utilize the resources across multiple EIPs, we systematically characterize the provisioning process as a large-scale linear programming (LP) problem and transform it into an easily solved form. Accordingly, we design a dynamic algorithm to tackle the varying service demands from users. We conduct extensive experiments over the base station networks in Toronto city. Compared with the existing fixed contract model and multihoming model, edge federation can reduce the overall cost of EIPs by 23.3% to 24.5%, and 15.5% to 16.3%, respectively.
The Role of Cloud-MANET Framework in the Internet of Things (IoT)
Venue: arXiv cs.NI 2020
Year: 2020

In the next generation of computing, Mobile ad-hoc network (MANET) will play a very important role in the Internet of Things (IoT). The MANET is a kind of wireless networks that are self-organizing and auto connected in a decentralized system. Every device in MANET can be moved freely from one location to another in any direction. They can create a network with their neighbors smart devices and forward data to another device. The IoT-Cloud-MANET framework of smart devices is composed of IoT, cloud computing, and MANET. This framework can access and deliver cloud services to the MANET users through their smart devices in the IoT framework where all computations, data handling, and resource management are performed. The smart devices can move from one location to another within the range of the MANET network. Various MANETs can connect to the same cloud, they can use cloud service in a real time. For connecting the smart device of MANET to cloud needs integration with mobile apps. My main contribution in this research links a new methodology for providing secure communication on the internet of smart devices using MANET Concept in 5G. The research methodology uses the correct and efficient simulation of the desired study and can be implemented in a framework of the Internet of Things in 5G.
Embedded Agency
Venue: arXiv cs.AI 2020
Year: 2020

Traditional models of rational action treat the agent as though it is cleanly separated from its environment, and can act on that environment from the outside. Such agents have a known functional relationship with their environment, can model their environment in every detail, and do not need to reason about themselves or their internal parts. We provide an informal survey of obstacles to formalizing good reasoning for agents embedded in their environment. Such agents must optimize an environment that is not of type "function"; they must rely on models that fit within the modeled environment; and they must reason about themselves as just another physical system, made of parts that can be modified and that can work at cross purposes.
Online Learning with Continuous Ranked Probability Score
Venue: arXiv cs.LG 2020
Year: 2020

Probabilistic forecasts in the form of probability distributions over future events have become popular in several fields of statistical science. The dissimilarity between a probability forecast and an outcome is measured by a loss function (scoring rule). Popular example of scoring rule for continuous outcomes is the continuous ranked probability score (CRPS). We consider the case where several competing methods produce online predictions in the form of probability distribution functions. In this paper, the problem of combining probabilistic forecasts is considered in the prediction with expert advice framework. We show that CRPS is a mixable loss function and then the time independent upper bound for the regret of the Vovk's aggregating algorithm using CRPS as a loss function can be obtained. We present the results of numerical experiments illustrating the proposed methods.
Prediction of the disease controllability in a complex network using machine learning algorithms
Venue: arXiv cs.SI 2020
Year: 2020

The application of machine learning (ML) techniques span a vast spectrum ranging from speech, face and character recognition, medical diagnosis, anomaly detection in data to the general classification, prediction, and regression problems. In the present work, we solve the problem of predicting R_0 for disease spreading on complex networks using the regression-based state-of-art ML techniques. R_0 is a metric that determines whether the disease-free epidemic or an endemic state is asymptotically stable and hence indicates the controllability of the disease spread. We predict R_0 , based on training the ML models with structural properties of complex networks, irrespective of the network type. The prediction is possible because: (a) The structure of complex networks plays an essential role in the spreading processes on networks (b) The regression techniques such as Support Vector Regression and Artificial Neural Network Model can be very efficiently used for prediction problems, even for non-linear data. We obtained good accuracy in the prediction of R_0 for the simulated networks as well as real-world networks using these techniques. Moreover, the ML model training is a one-time investment cost in terms of training time and memory, and the trained model can be used for predicting R_0 on unseen/new examples of networks.