OpenRaiser/Intern-Atlas huggingface dataset:
An Early Benchmark of Quality of Experience Between HTTP/2 and HTTP/3 using Lighthouse
Venue: arXiv cs.NI 2020
Year: 2020

Google's QUIC (GQUIC) is an emerging transport protocol designed to reduce HTTP latency. Deployed across its platforms and positioned as an alternative to TCP+TLS, GQUIC is feature rich: offering reliable data transmission and secure communication. It addresses TCP+TLS's (i) Head of Line Blocking (HoLB), (ii) excessive round-trip times on connection establishment, and (iii) entrenchment. Efforts by the IETF are in progress to standardize the next generation of HTTP's (HTTP/3, or H3) delivery, with their own variant of QUIC. While performance benchmarks have been conducted between GQUIC and HTTP/2-over-TCP (H2), no such analysis to our knowledge has taken place between H2 and H3. In addition, past studies rely on Page Load Time as their main, if not only, metric. The purpose of this work is to benchmark the latest draft specification of H3 and dig further into a user's Quality of Experience (QoE) using Lighthouse: an open source (and metric diverse) auditing tool. Our findings show that, for one of H3's early implementations, H3 is mostly worse but achieves a higher average throughput
Average Age of Information of Irregular Repetition Slotted ALOHA
Venue: arXiv cs.NI 2020
Year: 2020

Flanking traditional metrics such as throughput and reliability, age of information (AoI) is emerging as a fundamental tool to capture the performance of IoT systems. In this context, we focus on a setup in which a large number of nodes attempt delivery of time-stamped updates to a common destination over a shared channel, and investigate the ability of different grant-free access strategies to maintain fresh information at the receiver. Specifically, we derive for the first time an exact closed-form expression of the average AoI achieved by irregular repetition slotted ALOHA (IRSA), and compare its performance to that of a slotted ALOHA approach. Our analysis reveals the potential of modern random access schemes, and pinpoints some fundamental trade-offs, providing useful hints for proper system design.
Privacy Shadow: Measuring Node Predictability and Privacy Over Time
Venue: arXiv cs.SI 2020
Year: 2020

The structure of network data enables simple predictive models to leverage local correlations between nodes to high accuracy on tasks such as attribute and link prediction. While this is useful for building better user models, it introduces the privacy concern that a user's data may be re-inferred from the network structure, after they leave the application. We propose the privacy shadow for measuring how long a user remains predictive from an arbitrary time within the network. Furthermore, we demonstrate that the length of the privacy shadow can be predicted for individual users in three real-world datasets.
Machine Translation Pre-training for Data-to-Text Generation -- A Case Study in Czech
Venue: arXiv cs.CL 2020
Year: 2020

While there is a large body of research studying deep learning methods for text generation from structured data, almost all of it focuses purely on English. In this paper, we study the effectiveness of machine translation based pre-training for data-to-text generation in non-English languages. Since the structured data is generally expressed in English, text generation into other languages involves elements of translation, transliteration and copying - elements already encoded in neural machine translation systems. Moreover, since data-to-text corpora are typically small, this task can benefit greatly from pre-training. Based on our experiments on Czech, a morphologically complex language, we find that pre-training lets us train end-to-end models with significantly improved performance, as judged by automatic metrics and human evaluation. We also show that this approach enjoys several desirable properties, including improved performance in low data scenarios and robustness to unseen slot values.
On Tractable Representations of Binary Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

We consider the compilation of a binary neural network's decision function into tractable representations such as Ordered Binary Decision Diagrams (OBDDs) and Sentential Decision Diagrams (SDDs). Obtaining this function as an OBDD/SDD facilitates the explanation and formal verification of a neural network's behavior. First, we consider the task of verifying the robustness of a neural network, and show how we can compute the expected robustness of a neural network, given an OBDD/SDD representation of it. Next, we consider a more efficient approach for compiling neural networks, based on a pseudo-polynomial time algorithm for compiling a neuron. We then provide a case study in a handwritten digits dataset, highlighting how two neural networks trained from the same dataset can have very high accuracies, yet have very different levels of robustness. Finally, in experiments, we show that it is feasible to obtain compact representations of neural networks as SDDs.
A Resource for Studying Chatino Verbal Morphology
Venue: arXiv cs.CL 2020
Year: 2020

We present the first resource focusing on the verbal inflectional morphology of San Juan Quiahije Chatino, a tonal mesoamerican language spoken in Mexico. We provide a collection of complete inflection tables of 198 lemmata, with morphological tags based on the UniMorph schema. We also provide baseline results on three core NLP tasks: morphological analysis, lemmatization, and morphological inflection.
Deeply Aligned Adaptation for Cross-domain Object Detection
Venue: arXiv cs.CV 2020
Year: 2020

Cross-domain object detection has recently attracted more and more attention for real-world applications, since it helps build robust detectors adapting well to new environments. In this work, we propose an end-to-end solution based on Faster R-CNN, where ground-truth annotations are available for source images (e.g., cartoon) but not for target ones (e.g., watercolor) during training. Motivated by the observation that the transferabilities of different neural network layers differ from each other, we propose to apply a number of domain alignment strategies to different layers of Faster R-CNN, where the alignment strength is gradually reduced from low to higher layers. Moreover, after obtaining region proposals in our network, we develop a foreground-background aware alignment module to further reduce the domain mismatch by separately aligning features of the foreground and background regions from the source and target domains. Extensive experiments on benchmark datasets demonstrate the effectiveness of our proposed approach.
Attentive One-Dimensional Heatmap Regression for Facial Landmark Detection and Tracking
Venue: arXiv cs.CV 2020
Year: 2020

Although heatmap regression is considered a state-of-the-art method to locate facial landmarks, it suffers from huge spatial complexity and is prone to quantization error. To address this, we propose a novel attentive one-dimensional heatmap regression method for facial landmark localization. First, we predict two groups of 1D heatmaps to represent the marginal distributions of the x and y coordinates. These 1D heatmaps reduce spatial complexity significantly compared to current heatmap regression methods, which use 2D heatmaps to represent the joint distributions of x and y coordinates. With much lower spatial complexity, the proposed method can output high-resolution 1D heatmaps despite limited GPU memory, significantly alleviating the quantization error. Second, a co-attention mechanism is adopted to model the inherent spatial patterns existing in x and y coordinates, and therefore the joint distributions on the x and y axes are also captured. Third, based on the 1D heatmap structures, we propose a facial landmark detector capturing spatial patterns for landmark detection on an image; and a tracker further capturing temporal patterns with a temporal refinement mechanism for landmark tracking. Experimental results on four benchmark databases demonstrate the superiority of our method.
Simpler completeness proofs for modal logics with intersection
Venue: arXiv cs.LO 2020
Year: 2020

There has been a significant interest in extending various modal logics with intersection, the most prominent examples being epistemic and doxastic logics with distributed knowledge. Completeness proofs for such logics tend to be complicated, in particular on model classes such as S5 like in standard epistemic logic, mainly due to the undefinability of intersection of modalities in standard modal logics. A standard proof method for the S5 case was outlined in [8] and later explicated in more detail in [13], using an "unraveling-folding method" case to achieve a treelike model to deal with the problem of undefinability. This method, however, is not easily adapted to other logics, due to the level of detail and reliance on S5. In this paper we propose a simpler proof technique by building a treelike canonical model directly, which avoids the complications in the processes of unraveling and folding. We demonstrate the technique by showing completeness of the normal modal logics K, D, T, B, S4 and S5 extended with intersection modalities. Furthermore, these treelike canonical models are compatible with Fischer-Ladner-style closures, and we combine the methods to show the completeness of the mentioned logics further extended with transitive closure of union modalities known from PDL or epistemic logic. Some of these completeness results are new.
#P-completeness of counting update digraphs, cacti, and a series-parallel decomposition method
Venue: arXiv cs.DM 2020
Year: 2020

Automata networks are a very general model of interacting entities, with applications to biological phenomena such as gene regulation. In many contexts, the order in which entities update their state is unknown, and the dynamics may be very sensitive to changes in this schedule of updates. Since the works of Aracena et. al, it is known that update digraphs are pertinent objects to study non-equivalent block-sequential update schedules. We prove that counting the number of equivalence classes, that is a tight upper bound on the synchronism sensitivity of a given network, is #P-complete. The problem is nevertheless computable in quasi-quadratic time for oriented cacti, and for oriented series-parallel graphs thanks to a decomposition method.
Anomaly Detection and Prototype Selection Using Polyhedron Curvature
Venue: arXiv cs.LG 2020
Year: 2020

We propose a novel approach to anomaly detection called Curvature Anomaly Detection (CAD) and Kernel CAD based on the idea of polyhedron curvature. Using the nearest neighbors for a point, we consider every data point as the vertex of a polyhedron where the more anomalous point has more curvature. We also propose inverse CAD (iCAD) and Kernel iCAD for instance ranking and prototype selection by looking at CAD from an opposite perspective. We define the concept of anomaly landscape and anomaly path and we demonstrate an application for it which is image denoising. The proposed methods are straightforward and easy to implement. Our experiments on different benchmarks show that the proposed methods are effective for anomaly detection and prototype selection.
Comparative Analysis of Multiple Deep CNN Models for Waste Classification
Venue: arXiv cs.CV 2020
Year: 2020

Waste is a wealth in a wrong place. Our research focuses on analyzing possibilities for automatic waste sorting and collecting in such a way that helps it for further recycling process. Various approaches are being practiced managing waste but not efficient and require human intervention. The automatic waste segregation would fit in to fill the gap. The project tested well known Deep Learning Network architectures for waste classification with dataset combined from own endeavors and Trash Net. The convolutional neural network is used for image classification. The hardware built in the form of dustbin is used to segregate those wastes into different compartments. Without the human exercise in segregating those waste products, the study would save the precious time and would introduce the automation in the area of waste management. Municipal solid waste is a huge, renewable source of energy. The situation is win-win for both government, society and industrialists. Because of fine-tuning of the ResNet18 Network, the best validation accuracy was found to be 87.8%.
FairNN- Conjoint Learning of Fair Representations for Fair Decisions
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we propose FairNN a neural network that performs joint feature representation and classification for fairness-aware learning. Our approach optimizes a multi-objective loss function in which (a) learns a fair representation by suppressing protected attributes (b) maintains the information content by minimizing a reconstruction loss and (c) allows for solving a classification task in a fair manner by minimizing the classification error and respecting the equalized odds-based fairness regularized. Our experiments on a variety of datasets demonstrate that such a joint approach is superior to separate treatment of unfairness in representation learning or supervised learning. Additionally, our regularizers can be adaptively weighted to balance the different components of the loss function, thus allowing for a very general framework for conjoint fair representation learning and decision making.
Mining Shape of Expertise: A Novel Approach Based on Convolutional Neural Network
Venue: arXiv cs.IR 2020
Year: 2020

Expert finding addresses the task of retrieving and ranking talented people on the subject of user query. It is a practical issue in the Community Question Answering networks. Recruiters looking for knowledgeable people for their job positions are the most important clients of expert finding systems. In addition to employee expertise, the cost of hiring new staff is another significant concern for organizations. An efficient solution to cope with this concern is to hire T-shaped experts that are cost-effective. In this study, we have proposed a new deep model for T-shaped experts finding based on Convolutional Neural Networks. The proposed model tries to match queries and users by extracting local and position-invariant features from their corresponding documents. In other words, it detects users' shape of expertise by learning patterns from documents of users and queries simultaneously. The proposed model contains two parallel CNN's that extract latent vectors of users and queries based on their corresponding documents and join them together in the last layer to match queries with users. Experiments on a large subset of Stack Overflow documents indicate the effectiveness of the proposed method against baselines in terms of NDCG, MRR, and ERR evaluation metrics.
From Generalized zero-shot learning to long-tail with class descriptors
Venue: arXiv cs.LG 2020
Year: 2020

Real-world data is predominantly unbalanced and long-tailed, but deep models struggle to recognize rare classes in the presence of frequent classes. Often, classes can be accompanied by side information like textual descriptions, but it is not fully clear how to use them for learning with unbalanced long-tail data. Such descriptions have been mostly used in (Generalized) Zero-shot learning (ZSL), suggesting that ZSL with class descriptions may also be useful for long-tail distributions. We describe DRAGON, a late-fusion architecture for long-tail learning with class descriptors. It learns to (1) correct the bias towards head classes on a sample-by-sample basis; and (2) fuse information from class-descriptions to improve the tail-class accuracy. We also introduce new benchmarks CUB-LT, SUN-LT, AWA-LT for long-tail learning with class-descriptions, building on existing learning-with-attributes datasets and a version of Imagenet-LT with class descriptors. DRAGON outperforms state-of-the-art models on the new benchmark. It is also a new SoTA on existing benchmarks for GFSL with class descriptors (GFSL-d) and standard (vision-only) long-tailed learning ImageNet-LT, CIFAR-10, 100, and Places365.
Reinforcement Learning Architectures: SAC, TAC, and ESAC
Venue: arXiv cs.LG 2020
Year: 2020

The trend is to implement intelligent agents capable of analyzing available information and utilize it efficiently. This work presents a number of reinforcement learning (RL) architectures; one of them is designed for intelligent agents. The proposed architectures are called selector-actor-critic (SAC), tuner-actor-critic (TAC), and estimator-selector-actor-critic (ESAC). These architectures are improved models of a well known architecture in RL called actor-critic (AC). In AC, an actor optimizes the used policy, while a critic estimates a value function and evaluate the optimized policy by the actor. SAC is an architecture equipped with an actor, a critic, and a selector. The selector determines the most promising action at the current state based on the last estimate from the critic. TAC consists of a tuner, a model-learner, an actor, and a critic. After receiving the approximated value of the current state-action pair from the critic and the learned model from the model-learner, the tuner uses the Bellman equation to tune the value of the current state-action pair. ESAC is proposed to implement intelligent agents based on two ideas, which are lookahead and intuition. Lookahead appears in estimating the values of the available actions at the next state, while the intuition appears in maximizing the probability of selecting the most promising action. The newly added elements are an underlying model learner, an estimator, and a selector. The model learner is used to approximate the underlying model. The estimator uses the approximated value function, the learned underlying model, and the Bellman equation to estimate the values of all actions at the next state. The selector is used to determine the most promising action at the next state, which will be used by the actor to optimize the used policy. Finally, the results show the superiority of ESAC compared with the other architectures.
The two-echelon routing problem with truck and drones
Venue: arXiv cs.AI 2020
Year: 2020

In this paper, we study novel variants of the well-known two-echelon vehicle routing problem in which a truck works on the first echelon to transport parcels and a fleet of drones to intermediate depots while in the second echelon, the drones are used to deliver parcels from intermediate depots to customers. The objective is to minimize the completion time instead of the transportation cost as in classical 2-echelon vehicle routing problems. Depending on the context, a drone can be launched from the truck at an intermediate depot once (single trip drone) or several times (multiple trip drone). Mixed Integer Linear Programming (MILP) models are first proposed to formulate mathematically the problems and solve to optimality small-size instances. To handle larger instances, a metaheuristic based on the idea of Greedy Randomized Adaptive Search Procedure (GRASP) is introduced. Experimental results obtained on instances of different contexts are reported and analyzed.
Reducing Data Motion to Accelerate the Training of Deep Neural Networks
Venue: arXiv cs.DC 2020
Year: 2020

This paper reduces the cost of DNNs training by decreasing the amount of data movement across heterogeneous architectures composed of several GPUs and multicore CPU devices. In particular, this paper proposes an algorithm to dynamically adapt the data representation format of network weights during training. This algorithm drives a compression procedure that reduces data size before sending them over the parallel system. We run an extensive evaluation campaign considering several up-to-date deep neural network models and two high-end parallel architectures composed of multiple GPUs and CPU multicore chips. Our solution achieves average performance improvements from 6.18\% up to 11.91\%.
Maximum parsimony distance on phylogenetictrees: a linear kernel and constant factor approximation algorithm
Venue: arXiv cs.DS 2020
Year: 2020

Maximum parsimony distance is a measure used to quantify the dissimilarity of two unrooted phylogenetic trees. It is NP-hard to compute, and very few positive algorithmic results are known due to its complex combinatorial structure. Here we address this shortcoming by showing that the problem is fixed parameter tractable. We do this by establishing a linear kernel i.e., that after applying certain reduction rules the resulting instance has size that is bounded by a linear function of the distance. As powerful corollaries to this result we prove that the problem permits a polynomial-time constant-factor approximation algorithm; that the treewidth of a natural auxiliary graph structure encountered in phylogenetics is bounded by a function of the distance; and that the distance is within a constant factor of the size of a maximum agreement forest of the two trees, a well studied object in phylogenetics.
Enhancing Social Recommendation with Adversarial Graph Convolutional Networks
Venue: arXiv cs.IR 2020
Year: 2020

Social recommender systems are expected to improve recommendation quality by incorporating social information when there is little user-item interaction data. However, recent reports from industry show that social recommender systems consistently fail in practice. According to the negative findings, the failure is attributed to: (1) A majority of users only have a very limited number of neighbors in social networks and can hardly benefit from social relations; (2) Social relations are noisy but they are indiscriminately used; (3) Social relations are assumed to be universally applicable to multiple scenarios while they are actually multi-faceted and show heterogeneous strengths in different scenarios. Most existing social recommendation models only consider the homophily in social networks and neglect these drawbacks. In this paper we propose a deep adversarial framework based on graph convolutional networks (GCN) to address these problems. Concretely, for (1) and (2), a GCN-based autoencoder is developed to augment the relation data by encoding high-order and complex connectivity patterns, and meanwhile is optimized subject to the constraint of reconstructing the social profile to guarantee the validity of the identified neighborhood. After obtaining enough purified social relations for each user, a GCN-based attentive social recommendation module is designed to address (3) by capturing the heterogeneous strengths of social relations. Finally, we adopt adversarial training to unify all the components by playing a Minimax game and ensure a coordinated effort to enhance recommendation performance. Extensive experiments on multiple open datasets demonstrate the superiority of our framework and the ablation study confirms the importance and effectiveness of each component.
Deep Neural Network in Cusp Catastrophe Model
Venue: arXiv cs.LG 2020
Year: 2020

Catastrophe theory was originally proposed to study dynamical systems that exhibit sudden shifts in behavior arising from small changes in input. These models can generate reasonable explanation behind abrupt jumps in nonlinear dynamic models. Among the different catastrophe models, the Cusp Catastrophe model attracted the most attention due to it's relatively simpler dynamics and rich domain of application. Due to the complex behavior of the response, the parameter space becomes highly non-convex and hence it becomes very hard to optimize to figure out the generating parameters. Instead of solving for these generating parameters, we demonstrated how a Machine learning model can be trained to learn the dynamics of the Cusp catastrophe models, without ever really solving for the generating model parameters. Simulation studies and application on a few famous datasets are used to validate our approach. To our knowledge, this is the first paper of such kind where a neural network based approach has been applied in Cusp Catastrophe model.