OpenRaiser/Intern-Atlas huggingface dataset:
Derivation of an Algorithm for Calculation of the Intersection Area of a Circle with a Grid with Finite Fill Factor
Venue: arXiv cs.GR 2018
Year: 2018

The problem deals with an exact calculation of the intersection area of a circle arbitrary placed on a grid of square shaped elements with gaps between them (finite fill factor). Usually an approximation is used for the calculation of the intersection area of the circle and the squares of the grid. We analyze the geometry of the problem and derive an algorithm for the exact computation of the intersection areas. The results of the analysis are summarized in the tally sheet. In a real world example this might be a CCD or CMOS chip, or the tile structure of a floor.
Capacity Results for the K-User Broadcast Channel with Two Nested Multicast Messages
Venue: arXiv cs.IT 2018
Year: 2018

The K-user discrete memoryless (DM) broadcast channel (BC) with two nested multicast messages is studied in which one common message is to be multicast to all receivers and the second private message to a subset of receivers. The receivers that must decode both messages are referred to as private receivers and the others that must decode only the common message as common receivers. For two nested multicast messages, we establish the capacity region for several classes of DM BCs characterized by the respective associated sets of pair-wise relationships between and among the common and private receivers, each described by the well-known more capable or less noisy conditions. For three classes of DM BCs, the capacity region is simply achieved by superposition coding and the proofs of the converses rely on a recently found information inequality. The achievable rate region is then enhanced through the addition of a splitting of the private message into as many parts as there are common receivers and indirect decoding. A closed-form two-dimensional polyhedral description is obtained for it for a given coding distribution. Through a converse result that relies on the well-known Csiszar sum lemma and the information inequality, a specialization of this region that involves splitting the private message into just two sub-messages is proved to be the capacity region for several classes of DM BCs, beyond those for which superposition coding alone is capacity optimal, thereby underscoring the benefit of rate-splitting. All previously known capacity results for DM BCs with two nested multicast messages for the two and three-receiver DM BCs as well as DM BCs with one private or one common receiver are included in the general framework presented in this work.
Group evolution patterns in running races
Venue: arXiv cs.CG 2018
Year: 2018

We address the problem of tracking and detecting interactions between the different groups of runners that form during a race. In athletic races control points are set to monitor the progress of athletes over the course. Intuitively, a {\it group} is a sufficiently large set of athletes that cross a control point together. After adapting an existing definition of group to our setting we go on to study two types of group evolution patterns. The primary focus of this work are {\it evolution patterns}, i.e. the transformation and interaction of groups of athletes between two consecutive control points. We provide an accurate geometric model of the following evolution patterns: survives, appears, disappears, expands, shrinks, merges, splits, coheres and disbands, and present algorithms to efficiently compute these patterns. Next, based on the algorithms introduced for identifying evolution patterns, algorithms to detect {\it long-term patterns} are introduced. These patterns track global properties over several control points: surviving, traceable forward, traceable backward and related forward and backward. Experimental evaluation of the algorithms provided is presented using real and synthetic data. Using the data currently available, our experiments show how our algorithms can provide valuable insight into how running races develop. Moreover, we also show how, even if dense (synthetic) data is considered, our algorithms are also able to process it in real time.
Automatic Summarization of Natural Language
Venue: arXiv cs.CL 2018
Year: 2018

Automatic summarization of natural language is a current topic in computer science research and industry, studied for decades because of its usefulness across multiple domains. For example, summarization is necessary to create reviews such as this one. Research and applications have achieved some success in extractive summarization (where key sentences are curated), however, abstractive summarization (synthesis and re-stating) is a hard problem and generally unsolved in computer science. This literature review contrasts historical progress up through current state of the art, comparing dimensions such as: extractive vs. abstractive, supervised vs. unsupervised, NLP (Natural Language Processing) vs Knowledge-based, deep learning vs algorithms, structured vs. unstructured sources, and measurement metrics such as Rouge and BLEU. Multiple dimensions are contrasted since current research uses combinations of approaches as seen in the review matrix. Throughout this summary, synthesis and critique is provided. This review concludes with insights for improved abstractive summarization measurement, with surprising implications for detecting understanding and comprehension in general.
Solving Archaeological Puzzles
Venue: arXiv cs.CV 2018
Year: 2018

Puzzle solving is a difficult problem in its own right, even when the pieces are all square and build up a natural image. But what if these ideal conditions do not hold? One such application domain is archaeology, where restoring an artifact from its fragments is highly important. From the point of view of computer vision, archaeological puzzle solving is very challenging, due to three additional difficulties: the fragments are of general shape; they are abraded, especially at the boundaries (where the strongest cues for matching should exist); and the domain of valid transformations between the pieces is continuous. The key contribution of this paper is a fully-automatic and general algorithm that addresses puzzle solving in this intriguing domain. We show that our state-of-the-art approach manages to correctly reassemble dozens of broken artifacts and frescoes.
The Prophet Inequality Can Be Solved Optimally with a Single Set of Samples
Venue: arXiv cs.DS 2018
Year: 2018

The setting of the classic prophet inequality is as follows: a gambler is shown the probability distributions of $n$ independent, non-negative random variables with finite expectations. In their indexed order, a value is drawn from each distribution, and after every draw the gambler may choose to accept the value and end the game, or discard the value permanently and continue the game. What is the best performance that the gambler can achieve in comparison to a prophet who can always choose the highest value? Krengel, Sucheston, and Garling solved this problem in 1978, showing that there exists a strategy for which the gambler can achieve half as much reward as the prophet in expectation. Furthermore, this result is tight. In this work, we consider a setting in which the gambler is allowed much less information. Suppose that the gambler can only take one sample from each of the distributions before playing the game, instead of knowing the full distributions. We provide a simple and intuitive algorithm that recovers the original approximation of $\frac{1}{2}$. Our algorithm works against even an almighty adversary who always chooses a worst-case ordering, rather than the standard offline adversary. The result also has implications for mechanism design -- there is much interest in designing competitive auctions with a finite number of samples from value distributions rather than full distributional knowledge.
Secure Estimation under Causative Attacks
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers the problem of secure parameter estimation when the estimation algorithm is prone to causative attacks. Causative attacks, in principle, target decision-making algorithms to alter their decisions by making them oblivious to specific attacks. Such attacks influence inference algorithms by tampering with the mechanism through which the algorithm is provided with the statistical model of the population about which an inferential decision is made. Causative attacks are viable, for instance, by contaminating the historical or training data, or by compromising an expert who provides the model. In the presence of causative attacks, the inference algorithms operate under a distorted statistical model for the population from which they collect data samples. This paper introduces specific notions of secure estimation and provides a framework under which secure estimation under causative attacks can be formulated. A central premise underlying the secure estimation framework is that forming secure estimates introduces a new dimension to the estimation objective, which pertains to detecting attacks and isolating the true model. Since detection and isolation decisions are imperfect, their inclusion induces an inherent coupling between the desired secure estimation objective and the auxiliary detection and isolation decisions that need to be formed in conjunction with the estimates. This paper establishes the fundamental interplay among the decisions involved and characterizes the general decision rules in closed-form for any desired estimation cost function. Furthermore, to circumvent the computational complexity associated with growing parameter dimension or attack complexity, a scalable estimation algorithm and its attendant optimality guarantees are provided. The theory developed is applied to secure parameter estimation in a sensor network.
Towards effective AI-powered agile project management
Venue: arXiv cs.SE 2018
Year: 2018

The rise of Artificial intelligence (AI) has the potential to significantly transform the practice of project management. Project management has a large socio-technical element with many uncertainties arising from variability in human aspects e.g., customers' needs, developers' performance and team dynamics. AI can assist project managers and team members by automating repetitive, high-volume tasks to enable project analytics for estimation and risk prediction, providing actionable recommendations, and even making decisions. AI is potentially a game changer for project management in helping to accelerate productivity and increase project success rates. In this paper, we propose a framework where AI technologies can be leveraged to offer support for managing agile projects, which have become increasingly popular in the industry.
Double Neural Counterfactual Regret Minimization
Venue: arXiv cs.AI 2018
Year: 2018

Counterfactual Regret Minimization (CRF) is a fundamental and effective technique for solving Imperfect Information Games (IIG). However, the original CRF algorithm only works for discrete state and action spaces, and the resulting strategy is maintained as a tabular representation. Such tabular representation limits the method from being directly applied to large games and continuing to improve from a poor strategy profile. In this paper, we propose a double neural representation for the imperfect information games, where one neural network represents the cumulative regret, and the other represents the average strategy. Furthermore, we adopt the counterfactual regret minimization algorithm to optimize this double neural representation. To make neural learning efficient, we also developed several novel techniques including a robust sampling method, mini-batch Monte Carlo Counterfactual Regret Minimization (MCCFR) and Monte Carlo Counterfactual Regret Minimization Plus (MCCFR+) which may be of independent interests. Experimentally, we demonstrate that the proposed double neural algorithm converges significantly better than the reinforcement learning counterpart.
Identifying translational science through embeddings of controlled vocabularies
Venue: arXiv cs.DL 2018
Year: 2018

Objective: Translational science aims at "translating" basic scientific discoveries into clinical applications. The identification of translational science has practicality such as evaluating the effectiveness of investments made into large programs like the Clinical and Translational Science Awards. Despite several proposed methods that group publications---the primary unit of research output---into some categories, we still lack a quantitative way to place papers onto the full, continuous spectrum from basic research to clinical medicine. Methods: Here we learn vector-representations of controlled vocabularies assigned to MEDLINE papers to obtain a Translational Axis (TA) that points from basic science to clinical medicine. The projected position of a term on the TA, expressed by a continuous quantity, indicates the term's "appliedness." The position of a paper, determined by the average location over its terms, quantifies the degree of its "appliedness," which we term as "level score." Results: We validate our method by comparing with previous techniques, showing excellent agreement yet uncovering significant variations of scores of papers in previously defined categories. The measure allows us to characterize the standing of journals, disciplines, and the entire biomedical literature along the basic-applied spectrum. Analysis on large-scale citation network reveals two main findings. First, direct citations mainly occurred between papers with similar scores. Second, shortest paths are more likely ended up with a paper closer to the basic end of the spectrum, regardless of where the starting paper is on the spectrum. Conclusions: The proposed method provides a quantitative way to identify translational science.
Neuromemrisitive Architecture of HTM with On-Device Learning and Neurogenesis
Venue: arXiv cs.ET 2018
Year: 2018

Hierarchical temporal memory (HTM) is a biomimetic sequence memory algorithm that holds promise for invariant representations of spatial and spatiotemporal inputs. This paper presents a comprehensive neuromemristive crossbar architecture for the spatial pooler (SP) and the sparse distributed representation classifier, which are fundamental to the algorithm. There are several unique features in the proposed architecture that tightly link with the HTM algorithm. A memristor that is suitable for emulating the HTM synapses is identified and a new Z-window function is proposed. The architecture exploits the concept of synthetic synapses to enable potential synapses in the HTM. The crossbar for the SP avoids dark spots caused by unutilized crossbar regions and supports rapid on-chip training within 2 clock cycles. This research also leverages plasticity mechanisms such as neurogenesis and homeostatic intrinsic plasticity to strengthen the robustness and performance of the SP. The proposed design is benchmarked for image recognition tasks using MNIST and Yale faces datasets, and is evaluated using different metrics including entropy, sparseness, and noise robustness. Detailed power analysis at different stages of the SP operations is performed to demonstrate the suitability for mobile platforms.
Facetize: An Interactive Tool for Cleaning and Transforming Datasets for Facilitating Exploratory Search
Venue: arXiv cs.DB 2018
Year: 2018

There is a plethora of datasets in various formats which are usually stored in files, hosted in catalogs, or accessed through SPARQL endpoints. In most cases, these datasets cannot be straightforwardly explored by end users, for satisfying recall-oriented information needs. To fill this gap, in this paper we present the design and implementation of Facetize, an editor that allows users to transform (in an interactive manner) datasets, either static (i.e. stored in files), or dynamic (i.e. being the results of SPARQL queries), to datasets that can be directly explored effectively by themselves or other users. The latter (exploration) is achieved through the familiar interaction paradigm of Faceted Search (and Preference-enriched Faceted Search). Specifically in this paper we describe the requirements, we introduce the required set of transformations, and then we detail the functionality and the implementation of the editor Facetize that realizes these transformations. The supported operations cover a wide range of tasks (selection, visibility, deletions, edits, definition of hierarchies, intervals, derived attributes, and others) and Facetize enables the user to carry them out in a user-friendly and guided manner, without presupposing any technical background (regarding data representation or query languages). Finally we present the results of an evaluation with users. To the best of your knowledge, this is the first editor for this kind of tasks.
Analysis of Difficulty Control in Bitcoin and Proof-of-Work Blockchains
Venue: arXiv cs.CR 2018
Year: 2018

This paper presents a stochastic model for block arrival times based on the difficulty retargeting rule used in Bitcoin, as well as other proof-of-work blockchains. Unlike some previous work, this paper explicitly models the difficulty target as a random variable which is a function of the previous block arrival times and affecting the block times in the next retargeting period. An explicit marginal distribution is derived for the time between successive blocks (the blocktime), while allowing for randomly changing difficulty. This paper also aims to serve as an introduction to Bitcoin and proof-of-work blockchains for the controls community, focusing on the difficulty retargeting procedure used in Bitcoin.
On the Secrecy Performance of Generalized User Selection for Interference-Limited Multiuser Wireless Networks
Venue: arXiv cs.IT 2018
Year: 2018

We investigate the secrecy performance of a multiuser diversity scheme for an interference-limited wireless network with a base-station (BS), $N$ legitimate users and an eavesdropper, in the presence of a single dominant interferer. Assuming interference dominates noise power at the eavesdropper and at each legitimate user's receiver, the BS transmits information to the legitimate user with the $k$-th best (highest) signal-to-interference ratio. We derive a closed-form expression for the secrecy outage probability for an arbitrary $N$ and an asymptotic expression for a fixed $k$ and large $N$. Furthermore, we derive a closed form asymptotic expression for the ergodic secrecy capacity of the $k$-th best user and show that it scales like $O\left(\log(N)\right)$ for a fixed $k$ and large $N$.
Coarse-to-fine Semantic Segmentation from Image-level Labels
Venue: arXiv cs.CV 2018
Year: 2018

Deep neural network-based semantic segmentation generally requires large-scale cost extensive annotations for training to obtain better performance. To avoid pixel-wise segmentation annotations which are needed for most methods, recently some researchers attempted to use object-level labels (e.g. bounding boxes) or image-level labels (e.g. image categories). In this paper, we propose a novel recursive coarse-to-fine semantic segmentation framework based on only image-level category labels. For each image, an initial coarse mask is first generated by a convolutional neural network-based unsupervised foreground segmentation model and then is enhanced by a graph model. The enhanced coarse mask is fed to a fully convolutional neural network to be recursively refined. Unlike existing image-level label-based semantic segmentation methods which require to label all categories for images contain multiple types of objects, our framework only needs one label for each image and can handle images contains multi-category objects. With only trained on ImageNet, our framework achieves comparable performance on PASCAL VOC dataset as other image-level label-based state-of-the-arts of semantic segmentation. Furthermore, our framework can be easily extended to foreground object segmentation task and achieves comparable performance with the state-of-the-art supervised methods on the Internet Object dataset.
Knowledge Representation Learning: A Quantitative Review
Venue: arXiv cs.CL 2018
Year: 2018

Knowledge representation learning (KRL) aims to represent entities and relations in knowledge graph in low-dimensional semantic space, which have been widely used in massive knowledge-driven tasks. In this article, we introduce the reader to the motivations for KRL, and overview existing approaches for KRL. Afterwards, we extensively conduct and quantitative comparison and analysis of several typical KRL methods on three evaluation tasks of knowledge acquisition including knowledge graph completion, triple classification, and relation extraction. We also review the real-world applications of KRL, such as language modeling, question answering, information retrieval, and recommender systems. Finally, we discuss the remaining challenges and outlook the future directions for KRL. The codes and datasets used in the experiments can be found in https://github.com/thunlp/OpenKE.
Deep Convolutional Neural Networks in the Face of Caricature: Identity and Image Revealed
Venue: arXiv cs.CV 2018
Year: 2018

Real-world face recognition requires an ability to perceive the unique features of an individual face across multiple, variable images. The primate visual system solves the problem of image invariance using cascades of neurons that convert images of faces into categorical representations of facial identity. Deep convolutional neural networks (DCNNs) also create generalizable face representations, but with cascades of simulated neurons. DCNN representations can be examined in a multidimensional "face space", with identities and image parameters quantified via their projections onto the axes that define the space. We examined the organization of viewpoint, illumination, gender, and identity in this space. We show that the network creates a highly organized, hierarchically nested, face similarity structure in which information about face identity and imaging characteristics coexist. Natural image variation is accommodated in this hierarchy, with face identity nested under gender, illumination nested under identity, and viewpoint nested under illumination. To examine identity, we caricatured faces and found that network identification accuracy increased with caricature level, and--mimicking human perception--a caricatured distortion of a face "resembled" its veridical counterpart. Caricatures improved performance by moving the identity away from other identities in the face space and minimizing the effects of illumination and viewpoint. Deep networks produce face representations that solve long-standing computational problems in generalized face recognition. They also provide a unitary theoretical framework for reconciling decades of behavioral and neural results that emphasized either the image or the object/face in representations, without understanding how a neural code could seamlessly accommodate both.
A Grammar-based Compressed Representation of 3D Trajectories
Venue: arXiv cs.DS 2018
Year: 2018

Much research has been published about trajectory management on the ground or at the sea, but compression or indexing of flight trajectories have usually been less explored. However, air traffic management is a challenge because airspace is becoming more and more congested, and large flight data collections must be preserved and exploited for varied purposes. This paper proposes 3DGraCT, a new method for representing these flight trajectories. It extends the GraCT compact data structure to cope with a third dimension (altitude), while retaining its space/time complexities. 3DGraCT improves space requirements of traditional spatio-temporal data structures by two orders of magnitude, being competitive for the considered types of queries, even leading the comparison for a particular one.