OpenRaiser/Intern-Atlas huggingface dataset:
Two at Once: Enhancing Learning and Generalization Capacities via IBN-Net
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional neural networks (CNNs) have achieved great successes in many computer vision problems. Unlike existing works that designed CNN architectures to improve performance on a single task of a single domain and not generalizable, we present IBN-Net, a novel convolutional architecture, which remarkably enhances a CNN's modeling ability on one domain (e.g. Cityscapes) as well as its generalization capacity on another domain (e.g. GTA5) without finetuning. IBN-Net carefully integrates Instance Normalization (IN) and Batch Normalization (BN) as building blocks, and can be wrapped into many advanced deep networks to improve their performances. This work has three key contributions. (1) By delving into IN and BN, we disclose that IN learns features that are invariant to appearance changes, such as colors, styles, and virtuality/reality, while BN is essential for preserving content related information. (2) IBN-Net can be applied to many advanced deep architectures, such as DenseNet, ResNet, ResNeXt, and SENet, and consistently improve their performance without increasing computational cost. (3) When applying the trained networks to new domains, e.g. from GTA5 to Cityscapes, IBN-Net achieves comparable improvements as domain adaptation methods, even without using data from the target domain. With IBN-Net, we won the 1st place on the WAD 2018 Challenge Drivable Area track, with an mIoU of 86.18%.
Raziel: Private and Verifiable Smart Contracts on Blockchains
Venue: arXiv cs.CR 2020
Year: 2020

Raziel combines secure multi-party computation and proof-carrying code to provide privacy, correctness and verifiability guarantees for smart contracts on blockchains. Effectively solving DAO and Gyges attacks, this paper describes an implementation and presents examples to demonstrate its practical viability (e.g., private and verifiable crowdfundings and investment funds). Additionally, we show how to use Zero-Knowledge Proofs of Proofs (i.e., Proof-Carrying Code certificates) to prove the validity of smart contracts to third parties before their execution without revealing anything else. Finally, we show how miners could get rewarded for generating pre-processing data for secure multi-party computation.
KB4Rec: A Dataset for Linking Knowledge Bases with Recommender Systems
Venue: arXiv cs.IR 2020
Year: 2020

To develop a knowledge-aware recommender system, a key data problem is how we can obtain rich and structured knowledge information for recommender system (RS) items. Existing datasets or methods either use side information from original recommender systems (containing very few kinds of useful information) or utilize private knowledge base (KB). In this paper, we present the first public linked KB dataset for recommender systems, named KB4Rec v1.0, which has linked three widely used RS datasets with the popular KB Freebase. Based on our linked dataset, we first preform some interesting qualitative analysis experiments, in which we discuss the effect of two important factors (i.e. popularity and recency) on whether a RS item can be linked to a KB entity. Finally, we present the comparison of several knowledge-aware recommendation algorithms on our linked dataset.
Reward Sharing Schemes for Stake Pools
Venue: arXiv cs.GT 2020
Year: 2020

We introduce and study reward sharing schemes (RSS) that promote the fair formation of {\em stake pools}\ in collaborative projects that involve a large number of stakeholders such as the maintenance of a proof-of-stake (PoS) blockchain. Our mechanisms are parameterized by a target value for the desired number of pools. We show that by properly incentivizing participants, the desired number of stake pools is a Nash equilibrium arising from rational play. Our equilibria also exhibit an efficiency / security tradeoff via a parameter that calibrates between including pools with the smallest cost and providing protection against Sybil attacks, the setting where a single stakeholder creates a large number of pools in the hopes to dominate the collaborative project. We then describe how RSS can be deployed in the PoS setting, mitigating a number of potential deployment attacks and protocol deviations that include censoring transactions, performing Sybil attacks with the objective to control the majority of stake, lying about the actual cost and others. Finally, we experimentally demonstrate fast convergence to equilibria in dynamic environments where players react to each other's strategic moves over an indefinite period of interactive play. We also show how simple reward sharing schemes that are seemingly more "fair", perhaps counterintuitively, converge to centralized equilibria.
Parameterized Orientable Deletion
Venue: arXiv cs.CC 2020
Year: 2020

A graph is $d$-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most $d$. $d$-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-ORIENTABLE DELETION problem: given a graph $G=(V,E)$, delete the minimum number of vertices to make $G$ $d$-orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: - We show that the problem is W[2]-hard and $\log n$-inapproximable with respect to $k$, the number of deleted vertices. This closes the gap in the problem's approximability. - We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by $d+k$, but W-hard for each of the parameters $d,k$ separately. - We show that, under the SETH, for all $d,ε$, the problem does not admit a $(d+2-ε)^{tw}$, algorithm where $tw$ is the graph's treewidth, resolving as a special case an open problem on the complexity of PSEUDOFOREST DELETION. - We show that the problem is W-hard parameterized by the input graph's clique-width. Complementing this, we provide an algorithm running in time $d^{O(d\cdot cw)}$, showing that the problem is FPT by $d+cw$, and improving the previously best known algorithm for this case.
On Triangle Estimation using Tripartite Independent Set Queries
Venue: arXiv cs.DS 2020
Year: 2020

Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an algorithm that approximately counts the number of triangles in a graph using only polylogarithmic queries when \emph{the number of triangles on any edge in the graph is polylogarithmically bounded}. Our query oracle {\em Tripartite Independent Set} (TIS) takes three disjoint sets of vertices $A$, $B$ and $C$ as inputs, and answers whether there exists a triangle having one endpoint in each of these three sets. Our query model generally belongs to the class of \emph{group queries} (Ron and Tsur, ACM ToCT, 2016; Dell and Lapinskas, STOC 2018) and in particular is inspired by the {\em Bipartite Independent Set} (BIS) query oracle of Beame {\em et al.} (ITCS 2018). We extend the algorithmic framework of Beame {\em et al.}, with \tis replacing \bis, for approximately counting triangles in graphs.
Mobile big data analysis with machine learning
Venue: arXiv cs.LG 2020
Year: 2020

This paper investigates to identify the requirement and the development of machine learning-based mobile big data analysis through discussing the insights of challenges in the mobile big data (MBD). Furthermore, it reviews the state-of-the-art applications of data analysis in the area of MBD. Firstly, we introduce the development of MBD. Secondly, the frequently adopted methods of data analysis are reviewed. Three typical applications of MBD analysis, namely wireless channel modeling, human online and offline behavior analysis, and speech recognition in the internet of vehicles, are introduced respectively. Finally, we summarize the main challenges and future development directions of mobile big data analysis.
Classification of EEG Signal based on non-Gaussian Neutral Vector
Venue: arXiv cs.LG 2020
Year: 2020

In the design of brain-computer interface systems, classification of Electroencephalogram (EEG) signals is the essential part and a challenging task. Recently, as the marginalized discrete wavelet transform (mDWT) representations can reveal features related to the transient nature of the EEG signals, the mDWT coefficients have been frequently used in EEG signal classification. In our previous work, we have proposed a super-Dirichlet distribution-based classifier, which utilized the nonnegative and sum-to-one properties of the mDWT coefficients. The proposed classifier performed better than the state-of-the-art support vector machine-based classifier. In this paper, we further study the neutrality of the mDWT coefficients. Assuming the mDWT vector coefficients to be a neutral vector, we transform them non-linearly into a set of independent scalar coefficients. Feature selection strategy is proposed on the transformed feature domain. Experimental results show that the feature selection strategy helps improving the classification accuracy.
Impacts of Weather Conditions on District Heat System
Venue: arXiv cs.LG 2020
Year: 2020

Using artificial neural network for the prediction of heat demand has attracted more and more attention. Weather conditions, such as ambient temperature, wind speed and direct solar irradiance, have been identified as key input parameters. In order to further improve the model accuracy, it is of great importance to understand the influence of different parameters. Based on an Elman neural network (ENN), this paper investigates the impact of direct solar irradiance and wind speed on predicting the heat demand of a district heating network. Results show that including wind speed can generally result in a lower overall mean absolute percentage error (MAPE) (6.43%) than including direct solar irradiance (6.47%); while including direct solar irradiance can achieve a lower maximum absolute deviation (71.8%) than including wind speed (81.53%). In addition, even though including both wind speed and direct solar irradiance shows the best overall performance (MAPE=6.35%).
New Viewpoint and Algorithms for Water-Filling Solutions in Wireless Communications
Venue: arXiv cs.IT 2020
Year: 2020

Water-filling solutions play an important role in the designs for wireless communications, e.g., transmit covariance matrix design. A traditional physical understanding is to use the analogy of pouring water over a pool with fluctuating bottom. Numerous variants of water-filling solutions have been discovered during the evolution of wireless networks. To obtain the solution values, iterative computations are required, even for simple cases with compact mathematical formulations. Thus, algorithm design is a key issue for the practical use of water-filling solutions, which however has been given marginal attention in the literature. Many existing algorithms are designed on a case-by-case basis for the variations of water-filling solutions and/or with complex logics. In this paper, a new viewpoint for water-filling solutions is proposed to understand the problem dynamically by considering changes in the increasing rates on different subchannels. This fresh viewpoint provides useful mechanism and fundamental information in finding the optimization solution values. Based on the new understanding, a novel and comprehensive method for practical water-filling algorithm design is proposed, which can be used for systems with various performance metrics and power constraints, even for systems with imperfect channel state information (CSI).
Quantifying Deployability & Evolvability of Future Internet Architectures via Economic Models
Venue: arXiv cs.NI 2020
Year: 2020

Emerging new applications demand the current Internet to provide new functionalities. Although many future Internet architectures and protocols have been proposed to fulfill such needs, ISPs have been reluctant to deploy many of these architectures. We believe technical issues are not the main reasons as many of these new proposals are technically sound. In this paper, we take an economic perspective and seek to answer: Why most new Internet architectures failed to be deployed? How to enhance the deployability of a new architecture? We develop a game-theoretic model to characterize the outcome of an architecture's deployment through the equilibrium of ISPs' decisions. This model enables us to: (1) analyze several key factors of the deployability of a new architecture such as the number of critical ISPs and the change of routing path; (2) explain the deploying outcomes of some previously proposed architectures/protocols such as IPv6, DiffServ, CDN, etc., and shed light on the "Internet flattening phenomenon"; (3) predict the deployability of a new architecture such as NDN, and compare its deployability with competing architectures. Our study suggests that the difficulty to deploy a new Internet architecture comes from the "coordination" of distributed ISPs. Finally, we design a coordination mechanism to enhance the deployability of new architectures.
Contention resolution on a restrained channel
Venue: arXiv cs.DC 2020
Year: 2020

We examine deterministic broadcasting on multiple-access channels for a scenario when packets are injected continuously by an adversary to the buffers of the devices at rate $ρ$ packages per round. The aim is to maintain system stability, that is, bounded queues. In contrast to previous work we assume that there is a strict limit of available power, defined as the total number of stations allowed to transmit or listen to the channel at a given time, that can never be exceeded. We study how this constraint influences the quality of services with particular focus on stability. We show that in the regime of deterministic algorithms, the significance of energy restriction depends strongly on communication capabilities of broadcasting protocols. For the adaptive and full-sensing protocols, wherein stations may substantially adopt their behavior to the injection pattern, one can construct efficient algorithms using very small amounts of power without sacrificing throughput or stability of the system. In particular, we construct constant-energy adaptive and full sensing protocols stable for $ρ=1$ and any $ρ<1$, respectively, even for worst case (adversarial) injection patterns. Surprisingly, for the case of acknowledgment based algorithms that cannot adopt to the situation on the channel (i.e., their transmitting pattern is fixed in advance), limiting power leads to reducing the throughput. That is, for this class of protocols in order to preserve stability we need to reduce injection rate significantly. We support our theoretical analysis by simulation results of algorithms constructed in the paper. We depict how they work for systems of moderate, realistic sizes. We also provide a comprehensive simulation to compare our algorithms with backoff algorithms, which are common in real-world implementations, in terms of queue sizes and energy consumption.
The Capacity of Associated Subsequence Retrieval
Venue: arXiv cs.IT 2020
Year: 2020

The objective of a genome-wide association study (GWAS) is to associate subsequences of individuals' genomes to the observable characteristics called phenotypes (e.g., high blood pressure). Motivated by the GWAS problem, in this paper we introduce the information-theoretic problem of \emph{associated subsequence retrieval}, where a dataset of $N$ (possibly high-dimensional) sequences of length $G$, and their corresponding observable (binary) characteristics is given. The sequences are chosen independently and uniformly at random from $\mathcal{X}^G$, where $\mathcal{X}$ is a finite alphabet. The observable (binary) characteristic is only related to a specific unknown subsequence of length $L$ of the sequences, called \textit{associated subsequence}. For each sequence, if the associated subsequence of it belongs to a universal finite set, then it is more likely to display the observable characteristic (i.e., it is more likely that the observable characteristic is one). The goal is to retrieve the associated subsequence using a dataset of $N$ sequences and their observable characteristics. We demonstrate that as the parameters $N$, $G$, and $L$ grow, a threshold effect appears in the curve of probability of error versus the rate which is defined as ${Gh(L/G)}/{N}$, where $h(\cdot)$ is the binary entropy function. This effect allows us to define the capacity of associated subsequence retrieval. We develop an achievable scheme and a matching converse for this problem, and thus characterize its capacity in two scenarios: the zero-error-rate and the $ε$-error-rate.
Unsupervised Keyphrase Extraction from Scientific Publications
Venue: arXiv cs.CL 2020
Year: 2020

We propose a novel unsupervised keyphrase extraction approach that filters candidate keywords using outlier detection. It starts by training word embeddings on the target document to capture semantic regularities among the words. It then uses the minimum covariance determinant estimator to model the distribution of non-keyphrase word vectors, under the assumption that these vectors come from the same distribution, indicative of their irrelevance to the semantics expressed by the dimensions of the learned vector representation. Candidate keyphrases only consist of words that are detected as outliers of this dominant distribution. Empirical results show that our approach outperforms state-of-the-art and recent unsupervised keyphrase extraction methods.
A new coinductive confluence proof for infinitary lambda calculus
Venue: arXiv cs.LO 2020
Year: 2020

We present a new and formal coinductive proof of confluence and normalisation of Böhm reduction in infinitary lambda calculus. The proof is simpler than previous proofs of this result. The technique of the proof is new, i.e., it is not merely a coinductive reformulation of any earlier proofs. We formalised the proof in the Coq proof assistant.
Faster Support Vector Machines
Venue: arXiv cs.LG 2020
Year: 2020

The time complexity of support vector machines (SVMs) prohibits training on huge data sets with millions of data points. Recently, multilevel approaches to train SVMs have been developed to allow for time-efficient training on huge data sets. While regular SVMs perform the entire training in one -- time consuming -- optimization step, multilevel SVMs first build a hierarchy of problems decreasing in size that resemble the original problem and then train an SVM model for each hierarchy level, benefiting from the solved models of previous levels. We present a faster multilevel support vector machine that uses a label propagation algorithm to construct the problem hierarchy. Extensive experiments indicate that our approach is up to orders of magnitude faster than the previous fastest algorithm while having comparable classification quality. For example, already one of our sequential solvers is on average a factor 15 faster than the parallel ThunderSVM algorithm, while having similar classification quality.
New Bounds for Energy Complexity of Boolean Functions
Venue: arXiv cs.CC 2020
Year: 2020

$\newcommand{\EC}{\mathsf{EC}}\newcommand{\KW}{\mathsf{KW}}\newcommand{\DT}{\mathsf{DT}}\newcommand{\psens}{\mathsf{psens}} \newcommand{\calB}{\cal B} $ For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\mathcal{B}$, the energy complexity of $C$ (denoted by $\EC_{\calB}(C)$) is the maximum over all inputs $\{0,1\}^n$ the numbers of gates of the circuit $C$ (excluding the inputs) that output a one. Energy Complexity of a Boolean function over a finite basis $\calB$ denoted by $\EC_\calB(f):= \min_C \EC_{\calB}(C)$ where $C$ is a circuit over $\calB$ computing $f$. We study the case when $\calB = \{\land_2, \lor_2, \lnot\}$, the standard Boolean basis. It is known that any Boolean function can be computed by a circuit (with potentially large size) with an energy of at most $3n(1+ε(n))$ for a small $ ε(n)$(which we observe is improvable to $3n-1$). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions. * For all Boolean functions $f$, $\EC(f) \le O(\DT(f)^3)$ where $\DT(f)$ is the optimal decision tree depth of $f$. * We define a parameter \textit{positive sensitivity} (denoted by $\psens$), a quantity that is smaller than sensitivity and defined in a similar way, and show that for any Boolean circuit $C$ computing a Boolean function $f$, $ \EC(C) \ge \psens(f)/3$. * For a monotone function $f$, we show that $\EC(f) = Ω(\KW^+(f))$ where $\KW^+(f)$ is the cost of monotone Karchmer-Wigderson game of $f$. * Restricting the above notion of energy complexity to Boolean formulas, we show $\EC(F) = Ω\left (\sqrt{L(F)}-depth(F)\right )$ where $L(F)$ is the size and $depth(F)$ is the depth of a formula $F$.
Don't Use Large Mini-Batches, Use Local SGD
Venue: arXiv cs.LG 2020
Year: 2020

Mini-batch stochastic gradient methods (SGD) are state of the art for distributed training of deep neural networks. Drastic increases in the mini-batch sizes have lead to key efficiency and scalability gains in recent years. However, progress faces a major roadblock, as models trained with large batches often do not generalize well, i.e. they do not show good accuracy on new data. As a remedy, we propose a \emph{post-local} SGD and show that it significantly improves the generalization performance compared to large-batch training on standard benchmarks while enjoying the same efficiency (time-to-accuracy) and scalability. We further provide an extensive study of the communication efficiency vs. performance trade-offs associated with a host of \emph{local SGD} variants.
Identification of Deep Network Generated Images Using Disparities in Color Components
Venue: arXiv cs.MM 2020
Year: 2020

With the powerful deep network architectures, such as generative adversarial networks, one can easily generate photorealistic images. Although the generated images are not dedicated for fooling human or deceiving biometric authentication systems, research communities and public media have shown great concerns on the security issues caused by these images. This paper addresses the problem of identifying deep network generated (DNG) images. Taking the differences between camera imaging and DNG image generation into considerations, we analyze the disparities between DNG images and real images in different color components. We observe that the DNG images are more distinguishable from real ones in the chrominance components, especially in the residual domain. Based on these observations, we propose a feature set to capture color image statistics for identifying DNG images. Additionally, we evaluate several detection situations, including the training-testing data are matched or mismatched in image sources or generative models and detection with only real images. Extensive experimental results show that the proposed method can accurately identify DNG images and outperforms existing methods when the training and testing data are mismatched. Moreover, when the GAN model is unknown, our methods also achieves good performance with one-class classification by using only real images for training.