OpenRaiser/Intern-Atlas huggingface dataset:
Bibliometrics-based heuristics: What is their definition and how can they be studied?
Venue: arXiv cs.DL 2020
Year: 2020

When scientists study the phenomena they are interested in, they apply sound methods and base their work on theoretical considerations. In contrast, when the fruits of their research is being evaluated, basic scientific standards do not seem to matter. Instead, simplistic bibliometric indicators (i.e., publications and citation counts) are, paradoxically, both widely used and criticized without any methodological and theoretical framework that would serve to ground both use and critique. Yet, Bornmann and Marewski [1] proposed such a framework recently. They developed bibliometrics-based heuristics (BBHs) based on the fast-and-frugal heuristics approach [2] to decision making, in order to conceptually understand and empirically investigate the quantitative evaluation of research as well as to effectively train end-users of bibliometrics (e.g., science managers, scientists). Heuristics are decision strategies that use part of the available information and ignore the rest. By exploiting the statistical structure of task environments, they can aid to make accurate, fast, effortless, and cost-efficient decisions without that trade-offs are incurred. Because of their simplicity, heuristics are easy to understand and communicate, enhancing the transparency of decision processes. In this commentary, we explain several BBHs and discuss how such heuristics can be employed in practice (using the evaluation of applicants for funding programs as one example). Furthermore, we outline why heuristics can perform well, and how they and their fit to task environments can be studied. In pointing to the potential of research on BBHs and to the risks that come with an under-researched, mindless usage of bibliometrics, this commentary contributes to make research evaluation more scientific.
Multilingual Embeddings Jointly Induced from Contexts and Concepts: Simple, Strong and Scalable
Venue: arXiv cs.CL 2020
Year: 2020

Word embeddings induced from local context are prevalent in NLP. A simple and effective context-based multilingual embedding learner is Levy et al. (2017)'s S-ID (sentence ID) method. Another line of work induces high-performing multilingual embeddings from concepts (Dufter et al., 2018). In this paper, we propose Co+Co, a simple and scalable method that combines context-based and concept-based learning. From a sentence aligned corpus, concepts are extracted via sampling; words are then associated with their concept ID and sentence ID in embedding learning. This is the first work that successfully combines context-based and concept-based embedding learning. We show that Co+Co performs well for two different application scenarios: the Parallel Bible Corpus (1000+ languages, low-resource) and EuroParl (12 languages, high-resource). Among methods applicable to both corpora, Co+Co performs best in our evaluation setup of six tasks.
Multidimensional segment trees can do range updates in poly-logarithmic time
Venue: arXiv cs.DS 2020
Year: 2020

Updating and querying on a range is a classical algorithmic problem with a multitude of applications. The Segment Tree data structure is particularly notable in handling the range query and update operations. A Segment Tree divides the range into disjoint segments and merges them together to perform range queries and range updates elegantly. Although this data structure is remarkably potent for 1-dimensional problems, it falls short in higher dimensions. Lazy Propagation enables the operations to be computed in $O(logn)$ time in a single dimension. However, the concept of lazy propagation could not be translated to higher-dimensional cases, which imposes a time complexity of $O(n^{k-1} \; logn)$ for operations on $k$-dimensional data. In this work, we have made an attempt to emulate the idea of lazy propagation differently so that it can be applied for 2-dimensional cases. Moreover, the proposed modification should be capable of performing most general aggregate functions similar to the original Segment Tree, and can also be extended to even higher dimensions. Our proposed algorithm manages to perform range sum queries and updates in $O(\log^2 n)$ time for a 2-dimensional problem, which becomes $O(\log^d n)$ for a $d$-dimensional situation.
Automaticity and invariant measures of linear cellular automata
Venue: arXiv cs.FL 2020
Year: 2020

We show that spacetime diagrams of linear cellular automata $Φ: {\mathbb F}_p^{\mathbb Z} \to {\mathbb F}_p^{\mathbb Z}$ with $(-p)$-automatic initial conditions are automatic. This extends existing results on initial conditions which are eventually constant. Each automatic spacetime diagram defines a $(σ, Φ)$-invariant subset of ${\mathbb F}_p^{\mathbb Z}$, where $σ$ is the left shift map, and if the initial condition is not eventually periodic then this invariant set is nontrivial. For the Ledrappier cellular automaton we construct a family of nontrivial $(σ, Φ)$-invariant measures on ${\mathbb F}_3^{\mathbb Z}$. Finally, given a linear cellular automaton $Φ$, we construct a nontrivial $(σ, Φ)$-invariant measure on ${\mathbb F}_p^{\mathbb Z}$ for all but finitely many $p$.
Auto-ML Deep Learning for Rashi Scripts OCR
Venue: arXiv cs.CV 2020
Year: 2020

In this work we propose an OCR scheme for manuscripts printed in Rashi font that is an ancient Hebrew font and corresponding dialect used in religious Jewish literature, for more than 600 years. The proposed scheme utilizes a convolution neural network (CNN) for visual inference and Long-Short Term Memory (LSTM) to learn the Rashi scripts dialect. In particular, we derive an AutoML scheme to optimize the CNN architecture, and a book-specific CNN training to improve the OCR accuracy. The proposed scheme achieved an accuracy of more than 99.8% using a dataset of more than 3M annotated letters from the Responsa Project dataset.
Logic Attention Based Neighborhood Aggregation for Inductive Knowledge Graph Embedding
Venue: arXiv cs.AI 2020
Year: 2020

Knowledge graph embedding aims at modeling entities and relations with low-dimensional vectors. Most previous methods require that all entities should be seen during training, which is unpractical for real-world knowledge graphs with new entities emerging on a daily basis. Recent efforts on this issue suggest training a neighborhood aggregator in conjunction with the conventional entity and relation embeddings, which may help embed new entities inductively via their existing neighbors. However, their neighborhood aggregators neglect the unordered and unequal natures of an entity's neighbors. To this end, we summarize the desired properties that may lead to effective neighborhood aggregators. We also introduce a novel aggregator, namely, Logic Attention Network (LAN), which addresses the properties by aggregating neighbors with both rules- and network-based attention weights. By comparing with conventional aggregators on two knowledge graph completion tasks, we experimentally validate LAN's superiority in terms of the desired properties.
Why Extension-Based Proofs Fail
Venue: arXiv cs.DC 2020
Year: 2020

We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k > 1 processes in a wait-free manner in certain asynchronous models. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained for one of these models by an extension-based proof and, hence, extension-based proofs are limited in power.
Towards a Zero-One Law for Column Subset Selection
Venue: arXiv cs.DS 2020
Year: 2020

There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank-$k$ matrix $B$ minimizing the sum of absolute values of differences to a given $n$-by-$n$ matrix $A$, $\min_{\textrm{rank-}k~B}\|A-B\|_1$, or more generally finding a rank-$k$ matrix $B$ which minimizes the sum of $p$-th powers of absolute values of differences, $\min_{\textrm{rank-}k~B}\|A-B\|_p^p$. Many of these algorithms are linear time columns subset selection algorithms, returning a subset of $\mathrm{poly}(k \log n)$ columns whose cost is no more than a $\mathrm{poly}(k)$ factor larger than the cost of the best rank-$k$ matrix. The above error measures are special cases of the following general entrywise low rank approximation problem: given an arbitrary function $g:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}$, find a rank-$k$ matrix $B$ which minimizes $\|A-B\|_g = \sum_{i,j}g(A_{i,j}-B_{i,j})$. A natural question is which functions $g$ admit efficient approximation algorithms? Indeed, this is a central question of recent work studying generalized low rank models. In this work we give approximation algorithms for $\textit{every}$ function $g$ which is approximately monotone and satisfies an approximate triangle inequality, and we show both of these conditions are necessary. Further, our algorithm is efficient if the function $g$ admits an efficient approximate regression algorithm. Our approximation algorithms handle functions which are not even scale-invariant, such as the Huber loss function, which we show have very different structural properties than $\ell_p$-norms, e.g., one can show the lack of scale-invariance causes any column subset selection algorithm to provably require a $\sqrt{\log n}$ factor larger number of columns than $\ell_p$-norms; nevertheless we design the first efficient column subset selection algorithms for such error measures.
ConvS2S-VC: Fully convolutional sequence-to-sequence voice conversion
Venue: arXiv cs.SD 2020
Year: 2020

This paper proposes a voice conversion (VC) method using sequence-to-sequence (seq2seq or S2S) learning, which flexibly converts not only the voice characteristics but also the pitch contour and duration of input speech. The proposed method, called ConvS2S-VC, has three key features. First, it uses a model with a fully convolutional architecture. This is particularly advantageous in that it is suitable for parallel computations using GPUs. It is also beneficial since it enables effective normalization techniques such as batch normalization to be used for all the hidden layers in the networks. Second, it achieves many-to-many conversion by simultaneously learning mappings among multiple speakers using only a single model instead of separately learning mappings between each speaker pair using a different model. This enables the model to fully utilize available training data collected from multiple speakers by capturing common latent features that can be shared across different speakers. Owing to this structure, our model works reasonably well even without source speaker information, thus making it able to handle any-to-many conversion tasks. Third, we introduce a mechanism, called the conditional batch normalization that switches batch normalization layers in accordance with the target speaker. This particular mechanism has been found to be extremely effective for our many-to-many conversion model. We conducted speaker identity conversion experiments and found that ConvS2S-VC obtained higher sound quality and speaker similarity than baseline methods. We also found from audio examples that it could perform well in various tasks including emotional expression conversion, electrolaryngeal speech enhancement, and English accent conversion.
On Relating Technical, Social Factors, and the Introduction of Bugs
Venue: arXiv cs.SE 2020
Year: 2020

As collaborative coding environments make it easier to contribute to software projects, the number of developers involved in these projects keeps increasing. This increase makes it more difficult for code reviewers to deal with buggy contributions. Collaborative environments like GitHub provide a rich source of data on developers' contributions. Such data can be used to extract information about developers regarding technical (e.g., their experience) and social (e.g., their interactions) factors. Recent studies analyzed the influence of these factors on different activities of software development. However, there is still room for improvement on the relation between these factors and the introduction of bugs. We present a broader study, including 8 projects from different domains and 6,537 bug reports, on relating five technical, three social factors, and the introduction of bugs. The results indicate that technical and social factors can discriminate between buggy and clean commits. But, the technical factors are more determining than social ones. Particularly, the developers' habits of not following technical contribution norms and the developer's commit bugginess are associated with an increase on commit bugginess. On the other hand, project's establishment, ownership level of developers' commit, and social influence are related to a lower chance of introducing bugs.
Neural Image Compression for Gigapixel Histopathology Image Analysis
Venue: arXiv cs.CV 2020
Year: 2020

We propose Neural Image Compression (NIC), a two-step method to build convolutional neural networks for gigapixel image analysis solely using weak image-level labels. First, gigapixel images are compressed using a neural network trained in an unsupervised fashion, retaining high-level information while suppressing pixel-level noise. Second, a convolutional neural network (CNN) is trained on these compressed image representations to predict image-level labels, avoiding the need for fine-grained manual annotations. We compared several encoding strategies, namely reconstruction error minimization, contrastive training and adversarial feature learning, and evaluated NIC on a synthetic task and two public histopathology datasets. We found that NIC can exploit visual cues associated with image-level labels successfully, integrating both global and local visual information. Furthermore, we visualized the regions of the input gigapixel images where the CNN attended to, and confirmed that they overlapped with annotations from human experts.
RGB-D SLAM in Dynamic Environments Using Point Correlations
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, a simultaneous localization and mapping (SLAM) method that eliminates the influence of moving objects in dynamic environments is proposed. This method utilizes the correlation between map points to separate points that are part of the static scene and points that are part of different moving objects into different groups. A sparse graph is first created using Delaunay triangulation from all map points. In this graph, the vertices represent map points, and each edge represents the correlation between adjacent points. If the relative position between two points remains consistent over time, there is correlation between them, and they are considered to be moving together rigidly. If not, they are considered to have no correlation and to be in separate groups. After the edges between the uncorrelated points are removed during point-correlation optimization, the remaining graph separates the map points of the moving objects from the map points of the static scene. The largest group is assumed to be the group of reliable static map points. Finally, motion estimation is performed using only these points. The proposed method was implemented for RGB-D sensors, evaluated with a public RGB-D benchmark, and tested in several additional challenging environments. The experimental results demonstrate that robust and accurate performance can be achieved by the proposed SLAM method in both slightly and highly dynamic environments. Compared with other state-of-the-art methods, the proposed method can provide competitive accuracy with good real-time performance.
Statistical Characteristics of Deep Representations: An Empirical Investigation
Venue: arXiv cs.LG 2020
Year: 2020

In this study, the effects of eight representation regularization methods are investigated, including two newly developed rank regularizers (RR). The investigation shows that the statistical characteristics of representations such as correlation, sparsity, and rank can be manipulated as intended, during training. Furthermore, it is possible to improve the baseline performance simply by trying all the representation regularizers and fine-tuning the strength of their effects. In contrast to performance improvement, no consistent relationship between performance and statistical characteristics was observable. The results indicate that manipulation of statistical characteristics can be helpful for improving performance, but only indirectly through its influence on learning dynamics or its tuning effects.
Near Zero-Energy Computation Using Quantum-dot Cellular Automata
Venue: arXiv cs.ET 2020
Year: 2020

Near zero-energy computing describes the concept of executing logic operations below the (kBT ln 2) energy limit. Landauer discussed that it is impossible to break this limit as long as the computations are performed in the conventional, non-reversible way. But even if reversible computations were performed, the basic energy needed for operating circuits realized in conventional technologies is still far above the (kBT ln 2) energy limit, i.e. the circuits do not operate physically reversible. In contrast, novel nanotechnologies like Quantum-dot Cellular Automata (QCA) allow for computations with very low energy dissipation and, hence, are promising candidates for breaking this limit. Accordingly, the design of reversible QCA circuits is an active field of research. But whether QCA in general (and the proposed circuits in particular) are indeed able to operate in a logically and physically reversible fashion is unknown thus far, because neither physical realizations nor appropriate simulation approaches were available yet. In this work, we address this gap by utilizing an established theoretical model that has been implemented in a physics simulator enabling a precise consideration of how energy is dissipated in QCA designs. Our results provide strong evidence that QCA is indeed a suitable technology for near zero-energy computing. Further, the first design of a logically and physically reversible adder circuit is presented which serves as proof-of-concept for future circuits with the ability of near zero-energy computing.
Broadcasting on Random Directed Acyclic Graphs
Venue: arXiv cs.IT 2020
Year: 2020

We study a generalization of the well-known model of broadcasting on trees. Consider a directed acyclic graph (DAG) with a unique source vertex $X$, and suppose all other vertices have indegree $d\geq 2$. Let the vertices at distance $k$ from $X$ be called layer $k$. At layer $0$, $X$ is given a random bit. At layer $k\geq 1$, each vertex receives $d$ bits from its parents in layer $k-1$, which are transmitted along independent binary symmetric channel edges, and combines them using a $d$-ary Boolean processing function. The goal is to reconstruct $X$ with probability of error bounded away from $1/2$ using the values of all vertices at an arbitrarily deep layer. This question is closely related to models of reliable computation and storage, and information flow in biological networks. In this paper, we analyze randomly constructed DAGs, for which we show that broadcasting is only possible if the noise level is below a certain degree and function dependent critical threshold. For $d\geq 3$, and random DAGs with layer sizes $Ω(\log k)$ and majority processing functions, we identify the critical threshold. For $d=2$, we establish a similar result for NAND processing functions. We also prove a partial converse for odd $d\geq 3$ illustrating that the identified thresholds are impossible to improve by selecting different processing functions if the decoder is restricted to using a single vertex. Finally, for any noise level, we construct explicit DAGs (using expander graphs) with bounded degree and layer sizes $Θ(\log k)$ admitting reconstruction. In particular, we show that such DAGs can be generated in deterministic quasi-polynomial time or randomized polylogarithmic time in the depth. These results portray a doubly-exponential advantage for storing a bit in DAGs compared to trees, where $d=1$ but layer sizes must grow exponentially with depth in order to enable broadcasting.
Forecasting People's Needs in Hurricane Events from Social Network
Venue: arXiv cs.CL 2020
Year: 2020

Social networks can serve as a valuable communication channel for calls for help, offering assistance, and coordinating rescue activities in disaster. Social networks such as Twitter allow users to continuously update relevant information, which is especially useful during a crisis, where the rapidly changing conditions make it crucial to be able to access accurate information promptly. Social media helps those directly affected to inform others of conditions on the ground in real time and thus enables rescue workers to coordinate their efforts more effectively, better meeting the survivors' need. This paper presents a new sequence to sequence based framework for forecasting people's needs during disasters using social media and weather data. It consists of two Long Short-Term Memory (LSTM) models, one of which encodes input sequences of weather information and the other plays as a conditional decoder that decodes the encoded vector and forecasts the survivors' needs. Case studies utilizing data collected during Hurricane Sandy in 2012, Hurricane Harvey and Hurricane Irma in 2017 were analyzed and the results compared with those obtained using a statistical language model n-gram and an LSTM generative model. Our proposed sequence to sequence method forecast people's needs more successfully than either of the other models. This new approach shows great promise for enhancing disaster management activities such as evacuation planning and commodity flow management.
Learning Temporal Point Processes via Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

Social goods, such as healthcare, smart city, and information networks, often produce ordered event data in continuous time. The generative processes of these event data can be very complex, requiring flexible models to capture their dynamics. Temporal point processes offer an elegant framework for modeling event data without discretizing the time. However, the existing maximum-likelihood-estimation (MLE) learning paradigm requires hand-crafting the intensity function beforehand and cannot directly monitor the goodness-of-fit of the estimated model in the process of training. To alleviate the risk of model-misspecification in MLE, we propose to generate samples from the generative model and monitor the quality of the samples in the process of training until the samples and the real data are indistinguishable. We take inspiration from reinforcement learning (RL) and treat the generation of each event as the action taken by a stochastic policy. We parameterize the policy as a flexible recurrent neural network and gradually improve the policy to mimic the observed event distribution. Since the reward function is unknown in this setting, we uncover an analytic and nonparametric form of the reward function using an inverse reinforcement learning formulation. This new RL framework allows us to derive an efficient policy gradient algorithm for learning flexible point process models, and we show that it performs well in both synthetic and real data.