OpenRaiser/Intern-Atlas huggingface dataset:
Romu: Fast Nonlinear Pseudo-Random Number Generators Providing High Quality
Venue: arXiv cs.DC 2020
Year: 2020

We introduce the Romu family of pseudo-random number generators (PRNGs) which combines the nonlinear operation of rotation with the linear operations of multiplication and (optionally) addition. Compared to conventional linear-only PRNGs, this mixture of linear and nonlinear operations achieves a greater degree of randomness using the same number of arithmetic operations. Or equivalently, it achieves the same randomness with fewer operations, resulting in higher speed. The statistical properties of these generators are strong, as they pass BigCrush and PractRand -- the most stringent test suites available. In addition, Romu generators take maximum advantage of instruction-level parallelism in modern superscalar processors, giving them an output latency of zero clock-cycles when inlined, thus adding no delay to an application. Scaled-down versions of these generators can be created and tested, enabling one to estimate the maximum number of values the full-size generators can supply before their randomness declines, ensuring the success of large jobs. Such capacity-estimates are rare for conventional PRNGs. A linear PRNG has a single cycle of states of known length comprising almost all possible states. However, a Romu generator computes pseudo-random permutations of those states, creating multiple cycles with pseudo-random lengths which cannot be determined by theory. But the ease of creating state-sizes of 128 or more bits allows (1) short cycles to be constrained to vanishingly low probabilities, and (2) thousands of parallel streams to be created having infinitesimal probabilities of overlap.
A multi-sided generalization of the $C^0$ Coons patch
Venue: arXiv cs.GR 2020
Year: 2020

Most multi-sided transfinite surfaces require cross-derivatives at the boundaries. Here we show a general $n$-sided patch that interpolates all boundaries based on only positional information. The surface is a weighted sum of $n$ Coons patches, using a parameterization based on Wachspress coordinates.
PuzzleNet: Scene Text Detection by Segment Context Graph Learning
Venue: arXiv cs.CV 2020
Year: 2020

Recently, a series of decomposition-based scene text detection methods has achieved impressive progress by decomposing challenging text regions into pieces and linking them in a bottom-up manner. However, most of them merely focus on linking independent text pieces while the context information is underestimated. In the puzzle game, the solver often put pieces together in a logical way according to the contextual information of each piece, in order to arrive at the correct solution. Inspired by it, we propose a novel decomposition-based method, termed Puzzle Networks (PuzzleNet), to address the challenging scene text detection task in this work. PuzzleNet consists of the Segment Proposal Network (SPN) that predicts the candidate text segments fitting arbitrary shape of text region, and the two-branch Multiple-Similarity Graph Convolutional Network (MSGCN) that models both appearance and geometry correlations between each segment to its contextual ones. By building segments as context graphs, MSGCN effectively employs segment context to predict combinations of segments. Final detections of polygon shape are produced by merging segments according to the predicted combinations. Evaluations on three benchmark datasets, ICDAR15, MSRA-TD500 and SCUT-CTW1500, have demonstrated that our method can achieve better or comparable performance than current state-of-the-arts, which is beneficial from the exploitation of segment context graph.
Gini Index based Initial Coin Offering Mechanism
Venue: arXiv cs.GT 2020
Year: 2020

As a fundraising method, Initial Coin Offering (ICO) has raised billions of dollars for thousands of startups in the past two years. Existing ICO mechanisms place more emphasis on the short-term benefits of maximal fundraising while ignoring the problem of unbalanced token allocation, which negatively impacts subsequent fundraising and has bad effects on introducing new investors and resources. We propose a new ICO mechanism which uses the concept of Gini index for the very first time as a mechanism design constraint to control allocation inequality. Our mechanism maintains an elegant and straightforward structure. It allows the agents to modify their bids as a price discovery process, while limiting the bids of whales. We analyze the agents' equilibrium behaviors under our mechanism. Under natural technical assumptions, we show that most agents have simple dominant strategies and the equilibrium revenue approaches the optimal revenue asymptotically in the number of agents. We verify our mechanism using real ICO dataset we collected, and confirm that our mechanism performs well in terms of both allocation fairness and revenue.
Detecting Potential Topics In News Using BERT, CRF and Wikipedia
Venue: arXiv cs.CL 2020
Year: 2020

For a news content distribution platform like Dailyhunt, Named Entity Recognition is a pivotal task for building better user recommendation and notification algorithms. Apart from identifying names, locations, organisations from the news for 13+ Indian languages and use them in algorithms, we also need to identify n-grams which do not necessarily fit in the definition of Named-Entity, yet they are important. For example, "me too movement", "beef ban", "alwar mob lynching". In this exercise, given an English language text, we are trying to detect case-less n-grams which convey important information and can be used as topics and/or hashtags for a news. Model is built using Wikipedia titles data, private English news corpus and BERT-Multilingual pre-trained model, Bi-GRU and CRF architecture. It shows promising results when compared with industry best Flair, Spacy and Stanford-caseless-NER in terms of F1 and especially Recall.
Refined Strong Converse for the Constant Composition Codes
Venue: arXiv cs.IT 2020
Year: 2020

A strong converse bound for constant composition codes of the form $P_{e}^{(n)} \geq 1- A n^{-0.5(1-E_{sc}'(R,W,p))} e^{-n E_{sc}(R,W,p)}$ is established using the Berry-Esseen theorem through the concepts of Augustin information and Augustin mean, where $A$ is a constant determined by the channel $W$, the composition $p$, and the rate $R$, i.e., $A$ does not depend on the block length $n$.
PHS: A Toolbox for Parallel Hyperparameter Search
Venue: arXiv cs.LG 2020
Year: 2020

We introduce an open source python framework named PHS - Parallel Hyperparameter Search to enable hyperparameter optimization on numerous compute instances of any arbitrary python function. This is achieved with minimal modifications inside the target function. Possible applications appear in expensive to evaluate numerical computations which strongly depend on hyperparameters such as machine learning. Bayesian optimization is chosen as a sample efficient method to propose the next query set of parameters.
The Efficiency of Best-Response Dynamics
Venue: arXiv cs.GT 2020
Year: 2020

Best response (BR) dynamics is a natural method by which players proceed toward a pure Nash equilibrium via a local search method. The quality of the equilibrium reached may depend heavily on the order by which players are chosen to perform their best response moves. A {\em deviator rule} $S$ is a method for selecting the next deviating player. We provide a measure for quantifying the performance of different deviator rules. The {\em inefficiency} of a deviator rule $S$ is the maximum ratio, over all initial profiles $p$, between the social cost of the worst equilibrium reachable by $S$ from $p$ and the social cost of the best equilibrium reachable from $p$. This inefficiency always lies between $1$ and the {\em price of anarchy}. We study the inefficiency of various deviator rules in network formation games and job scheduling games (both are congestion games, where BR dynamics always converges to a pure NE). For some classes of games, we compute optimal deviator rules. Furthermore, we define and study a new class of deviator rules, called {\em local} deviator rules. Such rules choose the next deviator as a function of a restricted set of parameters, and satisfy a natural condition called {\em independence of irrelevant players}. We present upper bounds on the inefficiency of some local deviator rules, and also show that for some classes of games, no local deviator rule can guarantee inefficiency lower than the price of anarchy.
Cacheable and Non-Cacheable Traffic Interplay in a Relay-Assisted Wireless Network
Venue: arXiv cs.NI 2020
Year: 2020

We study a discrete-time wireless network that serves both cacheable and non-cacheable traffic with assistance of a relay node with storage capabilities for both types of traffic. We investigate how allocating the storage capacity to cacheable and non-cacheable traffic affects the network throughput. Our numerical results provide useful insights by varying not only the allocation of cacheable to non-cacheable storage but also the rate by which non-cacheable content is transmitted, the rate by which cacheable content is requested, as well as different popularity distributions of the cached files.
A Simulation Model Demonstrating the Impact of Social Aspects on Social Internet of Things
Venue: arXiv cs.AI 2020
Year: 2020

In addition to seamless connectivity and smartness, the objects in the Internet of Things (IoT) are expected to have the social capabilities -- these objects are termed as ``social objects''. In this paper, an intuitive paradigm of social interactions between these objects are argued and modeled. The impact of social behavior on the interaction pattern of social objects is studied taking Peer-to-Peer (P2P) resource sharing as an example application. The model proposed in this paper studies the implications of competitive vs. cooperative social paradigm, while peers attempt to attain the shared resources / services. The simulation results divulge that the social capabilities of the peers impart a significant increase in the quality of interactions between social objects. Through an agent-based simulation study, it is proved that cooperative strategy is more efficient than competitive strategy. Moreover, cooperation with an underpinning on real-life networking structure and mobility does not negatively impact the efficiency of the system at all; rather it helps.
Towards Utilizing Unlabeled Data in Federated Learning: A Survey and Prospective
Venue: arXiv cs.LG 2020
Year: 2020

Federated Learning (FL) proposed in recent years has received significant attention from researchers in that it can bring separate data sources together and build machine learning models in a collaborative but private manner. Yet, in most applications of FL, such as keyboard prediction, labeling data requires virtually no additional efforts, which is not generally the case. In reality, acquiring large-scale labeled datasets can be extremely costly, which motivates research works that exploit unlabeled data to help build machine learning models. However, to the best of our knowledge, few existing works aim to utilize unlabeled data to enhance federated learning, which leaves a potentially promising research topic. In this paper, we identify the need to exploit unlabeled data in FL, and survey possible research fields that can contribute to the goal.
Efficient reinforcement learning control for continuum robots based on Inexplicit Prior Knowledge
Venue: arXiv cs.RO 2020
Year: 2020

Compared to rigid robots that are generally studied in reinforcement learning, the physical characteristics of some sophisticated robots such as soft or continuum robots are higher complicated. Moreover, recent reinforcement learning methods are data-inefficient and can not be directly deployed to the robot without simulation. In this paper, we propose an efficient reinforcement learning method based on inexplicit prior knowledge in response to such problems. We first corroborate the method by simulation and employed directly in the real world. By using our method, we can achieve active visual tracking and distance maintenance of a tendon-driven robot which will be critical in minimally invasive procedures. Codes are available at https://github.com/Skylark0924/TendonTrack.
Ranking a set of objects: a graph based least-square approach
Venue: arXiv cs.IR 2020
Year: 2020

We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We assume that objects are endowed with intrinsic qualities and that the probability with which an object is preferred to another depends only on the difference between the qualities of the two competitors. We propose a class of non-adaptive ranking algorithms that rely on a least-squares optimization criterion for the estimation of qualities. Such algorithms are shown to be asymptotically optimal (i.e., they require $O(\frac{N}{ε^2}\log \frac{N}δ)$ comparisons to be $(ε, δ)$-PAC). Numerical results show that our schemes are very efficient also in many non-asymptotic scenarios exhibiting a performance similar to the maximum-likelihood algorithm. Moreover, we show how they can be extended to adaptive schemes and test them on real-world datasets.
The Differentially Private Lottery Ticket Mechanism
Venue: arXiv cs.LG 2020
Year: 2020

We propose the differentially private lottery ticket mechanism (DPLTM). An end-to-end differentially private training paradigm based on the lottery ticket hypothesis. Using "high-quality winners", selected via our custom score function, DPLTM significantly improves the privacy-utility trade-off over the state-of-the-art. We show that DPLTM converges faster, allowing for early stopping with reduced privacy budget consumption. We further show that the tickets from DPLTM are transferable across datasets, domains, and architectures. Our extensive evaluation on several public datasets provides evidence to our claims.
Towards Digital Engineering -- The Advent of Digital Systems Engineering
Venue: arXiv cs.CY 2020
Year: 2020

Digital Engineering, the digital transformation of engineering to leverage digital technologies, is coming globally. This paper explores digital systems engineering, which aims at developing theory, methods, models, and tools to support the emerging digital engineering. A critical task is to digitalize engineering artifacts, thus enabling information sharing across platform, across life cycle, and across domains. We identify significant challenges and enabling digital technologies; analyze the transition from traditional engineering to digital engineering; define core concepts, including "digitalization", "unique identification", "digitalized artifacts", "digital augmentation", and others; present a big picture of digital systems engineering in four levels: vision, strategy, action, and foundation; briefly discuss each of main areas of research issues. Digitalization enables fast infusing and leveraging novel digital technologies; unique identification enables information traceability and accountability in engineering lifecycle; provenance enables tracing dependency relations among engineering artifacts; supporting model reproducibility and replicability; helping with trustworthiness evaluation of digital engineering artifacts.
Knowledge Cores in Large Formal Contexts
Venue: arXiv cs.AI 2020
Year: 2020

Knowledge computation tasks are often infeasible for large data sets. This is in particular true when deriving knowledge bases in formal concept analysis (FCA). Hence, it is essential to come up with techniques to cope with this problem. Many successful methods are based on random processes to reduce the size of the investigated data set. This, however, makes them hardly interpretable with respect to the discovered knowledge. Other approaches restrict themselves to highly supported subsets and omit rare and interesting patterns. An essentially different approach is used in network science, called $k$-cores. These are able to reflect rare patterns if they are well connected in the data set. In this work, we study $k$-cores in the realm of FCA by exploiting the natural correspondence to bi-partite graphs. This structurally motivated approach leads to a comprehensible extraction of knowledge cores from large formal contexts data sets.
Joint Unsupervised Learning of Optical Flow and Egomotion with Bi-Level Optimization
Venue: arXiv cs.CV 2020
Year: 2020

We address the problem of joint optical flow and camera motion estimation in rigid scenes by incorporating geometric constraints into an unsupervised deep learning framework. Unlike existing approaches which rely on brightness constancy and local smoothness for optical flow estimation, we exploit the global relationship between optical flow and camera motion using epipolar geometry. In particular, we formulate the prediction of optical flow and camera motion as a bi-level optimization problem, consisting of an upper-level problem to estimate the flow that conforms to the predicted camera motion, and a lower-level problem to estimate the camera motion given the predicted optical flow. We use implicit differentiation to enable back-propagation through the lower-level geometric optimization layer independent of its implementation, allowing end-to-end training of the network. With globally-enforced geometric constraints, we are able to improve the quality of the estimated optical flow in challenging scenarios and obtain better camera motion estimates compared to other unsupervised learning methods.
Policy Evaluation Networks
Venue: arXiv cs.LG 2020
Year: 2020

Many reinforcement learning algorithms use value functions to guide the search for better policies. These methods estimate the value of a single policy while generalizing across many states. The core idea of this paper is to flip this convention and estimate the value of many policies, for a single set of states. This approach opens up the possibility of performing direct gradient ascent in policy space without seeing any new data. The main challenge for this approach is finding a way to represent complex policies that facilitates learning and generalization. To address this problem, we introduce a scalable, differentiable fingerprinting mechanism that retains essential policy information in a concise embedding. Our empirical results demonstrate that combining these three elements (learned Policy Evaluation Network, policy fingerprints, gradient ascent) can produce policies that outperform those that generated the training data, in zero-shot manner.
Squashed Shifted PMI Matrix: Bridging Word Embeddings and Hyperbolic Spaces
Venue: arXiv cs.CL 2020
Year: 2020

We show that removing sigmoid transformation in the skip-gram with negative sampling (SGNS) objective does not harm the quality of word vectors significantly and at the same time is related to factorizing a squashed shifted PMI matrix which, in turn, can be treated as a connection probabilities matrix of a random graph. Empirically, such graph is a complex network, i.e. it has strong clustering and scale-free degree distribution, and is tightly connected with hyperbolic spaces. In short, we show the connection between static word embeddings and hyperbolic spaces through the squashed shifted PMI matrix using analytical and empirical methods.
Meta-Learned Confidence for Few-shot Learning
Venue: arXiv cs.LG 2020
Year: 2020

Transductive inference is an effective means of tackling the data deficiency problem in few-shot learning settings. A popular transductive inference technique for few-shot metric-based approaches, is to update the prototype of each class with the mean of the most confident query examples, or confidence-weighted average of all the query samples. However, a caveat here is that the model confidence may be unreliable, which may lead to incorrect predictions. To tackle this issue, we propose to meta-learn the confidence for each query sample, to assign optimal weights to unlabeled queries such that they improve the model's transductive inference performance on unseen tasks. We achieve this by meta-learning an input-adaptive distance metric over a task distribution under various model and data perturbations, which will enforce consistency on the model predictions under diverse uncertainties for unseen tasks. Moreover, we additionally suggest a regularization which explicitly enforces the consistency on the predictions across the different dimensions of a high-dimensional embedding vector. We validate our few-shot learning model with meta-learned confidence on four benchmark datasets, on which it largely outperforms strong recent baselines and obtains new state-of-the-art results. Further application on semi-supervised few-shot learning tasks also yields significant performance improvements over the baselines. The source code of our algorithm is available at https://github.com/seongmin-kye/MCT.
Exploration-efficient Deep Reinforcement Learning with Demonstration Guidance for Robot Control
Venue: arXiv cs.RO 2020
Year: 2020

Although deep reinforcement learning (DRL) algorithms have made important achievements in many control tasks, they still suffer from the problems of sample inefficiency and unstable training process, which are usually caused by sparse rewards. Recently, some reinforcement learning from demonstration (RLfD) methods have shown to be promising in overcoming these problems. However, they usually require considerable demonstrations. In order to tackle these challenges, on the basis of the SAC algorithm we propose a sample efficient DRL-EG (DRL with efficient guidance) algorithm, in which a discriminator D(s) and a guider G(s) are modeled by a small number of expert demonstrations. The discriminator will determine the appropriate guidance states and the guider will guide agents to better exploration in the training phase. Empirical evaluation results from several continuous control tasks verify the effectiveness and performance improvements of our method over other RL and RLfD counterparts. Experiments results also show that DRL-EG can help the agent to escape from a local optimum.
The Data Representativeness Criterion: Predicting the Performance of Supervised Classification Based on Data Set Similarity
Venue: arXiv cs.CV 2020
Year: 2020

In a broad range of fields it may be desirable to reuse a supervised classification algorithm and apply it to a new data set. However, generalization of such an algorithm and thus achieving a similar classification performance is only possible when the training data used to build the algorithm is similar to new unseen data one wishes to apply it to. It is often unknown in advance how an algorithm will perform on new unseen data, being a crucial reason for not deploying an algorithm at all. Therefore, tools are needed to measure the similarity of data sets. In this paper, we propose the Data Representativeness Criterion (DRC) to determine how representative a training data set is of a new unseen data set. We present a proof of principle, to see whether the DRC can quantify the similarity of data sets and whether the DRC relates to the performance of a supervised classification algorithm. We compared a number of magnetic resonance imaging (MRI) data sets, ranging from subtle to severe difference is acquisition parameters. Results indicate that, based on the similarity of data sets, the DRC is able to give an indication as to when the performance of a supervised classifier decreases. The strictness of the DRC can be set by the user, depending on what one considers to be an acceptable underperformance.