OpenRaiser/Intern-Atlas huggingface dataset:
Chronofold: a data structure for versioned text
Venue: arXiv cs.DS 2020
Year: 2020

Chronofold is a replicated data structure for versioned text. It is designed for use in collaborative editors and revision control systems. Past models of this kind either retrofitted local linear orders to a distributed system (the OT approach) or employed distributed data models locally (the CRDT approach). That caused either extreme fragility in a distributed setting or egregious overheads in local use. Overall, that local/distributed impedance mismatch is cognitively taxing and causes lots of complexity. We solve that by using subjective linear orders locally at each replica, while inter-replica communication uses a distributed model. A separate translation layer insulates local data structures from the distributed environment. We modify the Lamport timestamping scheme to make that translation as trivial as possible. We believe our approach has applications beyond the domain of collaborative editing.
Evaluation of Automatic FPGA Offloading for Loop Statements of Applications
Venue: arXiv cs.DC 2020
Year: 2020

In recent years, with the prediction of Moore's law slowing down, utilization of hardware other than CPU such as FPGA which is energy effective is increasing. However, when using heterogeneous hardware other than CPUs, barriers of technical skills such as OpenCL are high. Based on that, I have proposed environment adaptive software that enables automatic conversion, configuration, and high-performance operation of once written code, according to the hardware to be placed. Partly of the offloading to the GPU was automated previously. In this paper, I propose and evaluate an automatic extraction method of appropriate offload target loop statements of source code as the first step of offloading to FPGA. I evaluate the effectiveness of the proposed method using an existing application.
Particle Filter Based Monocular Human Tracking with a 3D Cardbox Model and a Novel Deterministic Resampling Strategy
Venue: arXiv cs.CV 2020
Year: 2020

The challenge of markerless human motion tracking is the high dimensionality of the search space. Thus, efficient exploration in the search space is of great significance. In this paper, a motion capturing algorithm is proposed for upper body motion tracking. The proposed system tracks human motion based on monocular silhouette-matching, and it is built on the top of a hierarchical particle filter, within which a novel deterministic resampling strategy (DRS) is applied. The proposed system is evaluated quantitatively with the ground truth data measured by an inertial sensor system. In addition, we compare the DRS with the stratified resampling strategy (SRS). It is shown in experiments that DRS outperforms SRS with the same amount of particles. Moreover, a new 3D articulated human upper body model with the name 3D cardbox model is created and is proven to work successfully for motion tracking. Experiments show that the proposed system can robustly track upper body motion without self-occlusion. Motions towards the camera can also be well tracked.
Feedback game on Eulerian graphs
Venue: arXiv cs.GT 2020
Year: 2020

In this paper, we introduce a two-player impartial game on graphs, called a {\em feedback game}, which is a variant of the generalized geography. We study the feedback game on Eulerian graphs. In particular, we show that the PSPACE-completeness of the game and determine the winner of the game on several classes of Eulerian graphs.
Dynamics of large scale networks following a merger
Venue: arXiv cs.SI 2020
Year: 2020

We study the dynamic network of relationships among avatars in the massively multiplayer online game Planetside 2. In the spring of 2014, two separate servers of this game were merged, and as a result, two previously distinct networks were combined into one. We observed the evolution of this network in the seven month period following the merger and report our observations. We found that some structures of original networks persist in the combined network for a long time after the merger. As the original avatars are gradually removed, these structures slowly dissolve, but they remain observable for a surprisingly long time. We present a number of visualizations illustrating the post-merger dynamics and discuss time evolution of selected quantities characterizing the topology of the network.
On Layered Fan-Planar Graph Drawings
Venue: arXiv cs.CG 2020
Year: 2020

In this paper, we study fan-planar drawings that use $h$ layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testing the existence of such drawings is fixed-parameter tractable in $h$, via a reduction to a similar result for planar graphs by Dujmović et al. If the embedding is not fixed, then we give partial results for $h=2$: It was already known how to test existence of fan-planar proper 2-layer drawings for 2-connected graphs, and we show here how to test this for trees. Along the way, we exhibit other interesting results for graphs with a fan-planar proper $h$-layer drawings; in particular we bound their pathwidth and show that they have a bar-1-visibility representation.
Towards field-programmable photonic gate arrays
Venue: arXiv cs.ET 2020
Year: 2020

We review some of the basic principles, fundamentals, technologies, architectures and recent advances leading to thefor the implementation of Field Programmable Photonic Field Arrays (FPPGAs).
FMore: An Incentive Scheme of Multi-dimensional Auction for Federated Learning in MEC
Venue: arXiv cs.LG 2020
Year: 2020

Promising federated learning coupled with Mobile Edge Computing (MEC) is considered as one of the most promising solutions to the AI-driven service provision. Plenty of studies focus on federated learning from the performance and security aspects, but they neglect the incentive mechanism. In MEC, edge nodes would not like to voluntarily participate in learning, and they differ in the provision of multi-dimensional resources, both of which might deteriorate the performance of federated learning. Also, lightweight schemes appeal to edge nodes in MEC. These features require the incentive mechanism to be well designed for MEC. In this paper, we present an incentive mechanism FMore with multi-dimensional procurement auction of K winners. Our proposal FMore not only is lightweight and incentive compatible, but also encourages more high-quality edge nodes with low cost to participate in learning and eventually improve the performance of federated learning. We also present theoretical results of Nash equilibrium strategy to edge nodes and employ the expected utility theory to provide guidance to the aggregator. Both extensive simulations and real-world experiments demonstrate that the proposed scheme can effectively reduce the training rounds and drastically improve the model accuracy for challenging AI tasks.
Improving the Tightness of Convex Relaxation Bounds for Training Certifiably Robust Classifiers
Venue: arXiv cs.LG 2020
Year: 2020

Convex relaxations are effective for training and certifying neural networks against norm-bounded adversarial attacks, but they leave a large gap between certifiable and empirical robustness. In principle, convex relaxation can provide tight bounds if the solution to the relaxed problem is feasible for the original non-convex problem. We propose two regularizers that can be used to train neural networks that yield tighter convex relaxation bounds for robustness. In all of our experiments, the proposed regularizers result in higher certified accuracy than non-regularized baselines.
Risk-Aware Optimization of Age of Information in the Internet of Things
Venue: arXiv cs.IT 2020
Year: 2020

Minimization of the expected value of age of information (AoI) is a risk-neutral approach, and it thus cannot capture rare, yet critical, events with potentially large AoI. In order to capture the effect of these events, in this paper, the notion of conditional value-at-risk (CVaR) is proposed as an effective coherent risk measure that is suitable for minimization of AoI for real-time IoT status updates. In the considered monitoring system, an IoT device monitors a physical process and sends the status updates to a remote receiver with an updating cost. The optimal status update process is designed to jointly minimize the AoI at the receiver, the CVaR of the AoI at the receiver, and the energy cost. This stochastic optimization problem is formulated as an infinite horizon discounted risk-aware Markov decision process (MDP), which is computationally intractable due to the time inconsistency of the CVaR. By exploiting the special properties of coherent risk measures, the risk-aware MDP is reduced to a standard MDP with an augmented state space, for which we derive the optimal stationary policy using dynamic programming. In particular, the optimal history-dependent policy of the risk-aware MDP is shown to depend on the history only through the augmented system states and can be readily constructed using the optimal stationary policy of the augmented MDP. The proposed solution is shown to be computationally tractable and able to minimize the AoI in real-time IoT monitoring systems in a risk-aware manner.
Random Bundle: Brain Metastases Segmentation Ensembling through Annotation Randomization
Venue: arXiv cs.CV 2020
Year: 2020

We introduce a novel ensembling method, Random Bundle (RB), that improves performance for brain metastases segmentation. We create our ensemble by training each network on our dataset with 50% of our annotated lesions censored out. We also apply a lopsided bootstrap loss to recover performance after inducing an in silico 50% false negative rate and make our networks more sensitive. We improve our network detection of lesions's mAP value by 39% and more than triple the sensitivity at 80% precision. We also show slight improvements in segmentation quality through DICE score. Further, RB ensembling improves performance over baseline by a larger margin than a variety of popular ensembling strategies. Finally, we show that RB ensembling is computationally efficient by comparing its performance to a single network when both systems are constrained to have the same compute.
Survey Bandits with Regret Guarantees
Venue: arXiv cs.LG 2020
Year: 2020

We consider a variant of the contextual bandit problem. In standard contextual bandits, when a user arrives we get the user's complete feature vector and then assign a treatment (arm) to that user. In a number of applications (like healthcare), collecting features from users can be costly. To address this issue, we propose algorithms that avoid needless feature collection while maintaining strong regret guarantees.
Tree++: Truncated Tree Based Graph Kernels
Venue: arXiv cs.LG 2020
Year: 2020

Graph-structured data arise ubiquitously in many application domains. A fundamental problem is to quantify their similarities. Graph kernels are often used for this purpose, which decompose graphs into substructures and compare these substructures. However, most of the existing graph kernels do not have the property of scale-adaptivity, i.e., they cannot compare graphs at multiple levels of granularities. Many real-world graphs such as molecules exhibit structure at varying levels of granularities. To tackle this problem, we propose a new graph kernel called Tree++ in this paper. At the heart of Tree++ is a graph kernel called the path-pattern graph kernel. The path-pattern graph kernel first builds a truncated BFS tree rooted at each vertex and then uses paths from the root to every vertex in the truncated BFS tree as features to represent graphs. The path-pattern graph kernel can only capture graph similarity at fine granularities. In order to capture graph similarity at coarse granularities, we incorporate a new concept called super path into it. The super path contains truncated BFS trees rooted at the vertices in a path. Our evaluation on a variety of real-world graphs demonstrates that Tree++ achieves the best classification accuracy compared with previous graph kernels.
Mixed Integer Programming for Searching Maximum Quasi-Bicliques
Venue: arXiv cs.DS 2020
Year: 2020

This paper is related to the problem of finding the maximal quasi-bicliques in a bipartite graph (bigraph). A quasi-biclique in the bigraph is its "almost" complete subgraph. The relaxation of completeness can be understood variously; here, we assume that the subgraph is a $γ$-quasi-biclique if it lacks a certain number of edges to form a biclique such that its density is at least $γ\in (0,1]$. For a bigraph and fixed $γ$, the problem of searching for the maximal quasi-biclique consists of finding a subset of vertices of the bigraph such that the induced subgraph is a quasi-biclique and its size is maximal for a given graph. Several models based on Mixed Integer Programming (MIP) to search for a quasi-biclique are proposed and tested for working efficiency. An alternative model inspired by biclustering is formulated and tested; this model simultaneously maximizes both the size of the quasi-biclique and its density, using the least-square criterion similar to the one exploited by triclustering \textsc{TriBox}.
End-To-End Graph-based Deep Semi-Supervised Learning
Venue: arXiv cs.LG 2020
Year: 2020

The quality of a graph is determined jointly by three key factors of the graph: nodes, edges and similarity measure (or edge weights), and is very crucial to the success of graph-based semi-supervised learning (SSL) approaches. Recently, dynamic graph, which means part/all its factors are dynamically updated during the training process, has demonstrated to be promising for graph-based semi-supervised learning. However, existing approaches only update part of the three factors and keep the rest manually specified during the learning stage. In this paper, we propose a novel graph-based semi-supervised learning approach to optimize all three factors simultaneously in an end-to-end learning fashion. To this end, we concatenate two neural networks (feature network and similarity network) together to learn the categorical label and semantic similarity, respectively, and train the networks to minimize a unified SSL objective function. We also introduce an extended graph Laplacian regularization term to increase training efficiency. Extensive experiments on several benchmark datasets demonstrate the effectiveness of our approach.
Efficient Compression of Long Arbitrary Sequences with No Reference at the Encoder
Venue: arXiv cs.IT 2020
Year: 2020

In a distributed information application an encoder compresses an arbitrary vector while a similar reference vector is available to the decoder as side information. For the Hamming-distance similarity measure, and when guaranteed perfect reconstruction is required, we present two contributions to the solution of this problem. One result shows that when a set of potential reference vectors is available to the encoder, lower compression rates can be achieved when the set satisfies a certain clustering property. Another result reduces the best known decoding complexity from exponential in the vector length $n$ to $O(n^{1.5})$ by generalized concatenation of inner coset codes and outer error-correcting codes. One potential application of the results is the compression of DNA sequences, where similar (but not identical) reference vectors are shared among senders and receivers.
Gradual Channel Pruning while Training using Feature Relevance Scores for Convolutional Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

The enormous inference cost of deep neural networks can be scaled down by network compression. Pruning is one of the predominant approaches used for deep network compression. However, existing pruning techniques have one or more of the following limitations: 1) Additional energy cost on top of the compute heavy training stage due to pruning and fine-tuning stages, 2) Layer-wise pruning based on the statistics of a particular, ignoring the effect of error propagation in the network, 3) Lack of an efficient estimate for determining the important channels globally, 4) Unstructured pruning requires specialized hardware for effective use. To address all the above issues, we present a simple-yet-effective gradual channel pruning while training methodology using a novel data-driven metric referred to as feature relevance score. The proposed technique gets rid of the additional retraining cycles by pruning the least important channels in a structured fashion at fixed intervals during the actual training phase. Feature relevance scores help in efficiently evaluating the contribution of each channel towards the discriminative power of the network. We demonstrate the effectiveness of the proposed methodology on architectures such as VGG and ResNet using datasets such as CIFAR-10, CIFAR-100 and ImageNet, and successfully achieve significant model compression while trading off less than $1\%$ accuracy. Notably on CIFAR-10 dataset trained on ResNet-110, our approach achieves $2.4\times$ compression and a $56\%$ reduction in FLOPs with an accuracy drop of $0.01\%$ compared to the unpruned network.
Symbolic Querying of Vector Spaces: Probabilistic Databases Meets Relational Embeddings
Venue: arXiv cs.AI 2020
Year: 2020

We propose unifying techniques from probabilistic databases and relational embedding models with the goal of performing complex queries on incomplete and uncertain data. We formalize a probabilistic database model with respect to which all queries are done. This allows us to leverage the rich literature of theory and algorithms from probabilistic databases for solving problems. While this formalization can be used with any relational embedding model, the lack of a well-defined joint probability distribution causes simple query problems to become provably hard. With this in mind, we introduce \TO, a relational embedding model designed to be a tractable probabilistic database, by exploiting typical embedding assumptions within the probabilistic framework. Using a principled, efficient inference algorithm that can be derived from its definition, we empirically demonstrate that \TOs is an effective and general model for these querying tasks.
Improving the Linkage Construction with Echelon-Ferrers for Constant-Dimension Codes
Venue: arXiv cs.IT 2020
Year: 2020

Echelon-Ferrers is an important method to improve lower bounds for constant-dimension codes, which can be applied on various parameters. Fagang Li [12] combined the linkage construction and echelon-Ferrers to obtain some new lower bounds of constant-dimension codes. In this letter, we generalize this linkage construction to obtain new lower bounds.
Computing Bi-Lipschitz Outlier Embeddings into the Line
Venue: arXiv cs.DS 2020
Year: 2020

The problem of computing a bi-Lipschitz embedding of a graphical metric into the line with minimum distortion has received a lot of attention. The best-known approximation algorithm computes an embedding with distortion $O(c^2)$, where $c$ denotes the optimal distortion [Bădoiu \etal~2005]. We present a bi-criteria approximation algorithm that extends the above results to the setting of \emph{outliers}. Specifically, we say that a metric space $(X,ρ)$ admits a $(k,c)$-embedding if there exists $K\subset X$, with $|K|=k$, such that $(X\setminus K, ρ)$ admits an embedding into the line with distortion at most $c$. Given $k\geq 0$, and a metric space that admits a $(k,c)$-embedding, for some $c\geq 1$, our algorithm computes a $({\mathsf p}{\mathsf o}{\mathsf l}{\mathsf y}(k, c, \log n), {\mathsf p}{\mathsf o}{\mathsf l}{\mathsf y}(c))$-embedding in polynomial time. This is the first algorithmic result for outlier bi-Lipschitz embeddings. Prior to our work, comparable outlier embeddings where known only for the case of additive distortion.
Emosaic: Visualizing Affective Content of Text at Varying Granularity
Venue: arXiv cs.HC 2020
Year: 2020

This paper presents Emosaic, a tool for visualizing the emotional tone of text documents, considering multiple dimensions of emotion and varying levels of semantic granularity. Emosaic is grounded in psychological research on the relationship between language, affect, and color perception. We capitalize on an established three-dimensional model of human emotion: valence (good, nice vs. bad, awful), arousal (calm, passive vs. exciting, active) and dominance (weak, controlled vs. strong, in control). Previously, multi-dimensional models of emotion have been used rarely in visualizations of textual data, due to the perceptual challenges involved. Furthermore, until recently most text visualizations remained at a high level, precluding closer engagement with the deep semantic content of the text. Informed by empirical studies, we introduce a color mapping that translates any point in three-dimensional affective space into a unique color. Emosaic uses affective dictionaries of words annotated with the three emotional parameters of the valence-arousal-dominance model to extract emotional meanings from texts and then assigns to them corresponding color parameters of the hue-saturation-brightness color space. This approach of mapping emotion to color is aimed at helping readers to more easily grasp the emotional tone of the text. Several features of Emosaic allow readers to interactively explore the affective content of the text in more detail; e.g., in aggregated form as histograms, in sequential form following the order of text, and in detail embedded into the text display itself. Interaction techniques have been included to allow for filtering and navigating of text and visualizations.
SMOKE: Single-Stage Monocular 3D Object Detection via Keypoint Estimation
Venue: arXiv cs.CV 2020
Year: 2020

Estimating 3D orientation and translation of objects is essential for infrastructure-less autonomous navigation and driving. In case of monocular vision, successful methods have been mainly based on two ingredients: (i) a network generating 2D region proposals, (ii) a R-CNN structure predicting 3D object pose by utilizing the acquired regions of interest. We argue that the 2D detection network is redundant and introduces non-negligible noise for 3D detection. Hence, we propose a novel 3D object detection method, named SMOKE, in this paper that predicts a 3D bounding box for each detected object by combining a single keypoint estimate with regressed 3D variables. As a second contribution, we propose a multi-step disentangling approach for constructing the 3D bounding box, which significantly improves both training convergence and detection accuracy. In contrast to previous 3D detection techniques, our method does not require complicated pre/post-processing, extra data, and a refinement stage. Despite of its structural simplicity, our proposed SMOKE network outperforms all existing monocular 3D detection methods on the KITTI dataset, giving the best state-of-the-art result on both 3D object detection and Bird's eye view evaluation. The code will be made publicly available.