OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchical Clustering Supported by Reciprocal Nearest Neighbors
Venue: arXiv cs.IR 2019
Year: 2019

Clustering is a fundamental analysis tool aiming at classifying data points into groups based on their similarity or distance. It has found successful applications in all natural and social sciences, including biology, physics, economics, chemistry, astronomy, psychology, and so on. Among numerous existent algorithms, hierarchical clustering algorithms are of a particular advantage as they can provide results under different resolutions without any predetermined number of clusters and unfold the organization of resulted clusters. At the same time, they suffer a variety of drawbacks and thus are either time-consuming or inaccurate. We propose a novel hierarchical clustering approach on the basis of a simple hypothesis that two reciprocal nearest data points should be grouped in one cluster. Extensive tests on data sets across multiple domains show that our method is much faster and more accurate than the state-of-the-art benchmarks. We further extend our method to deal with the community detection problem in real networks, achieving remarkably better results in comparison with the well-known Girvan-Newman algorithm.
A Novel Approach to OCR using Image Recognition based Classification for Ancient Tamil Inscriptions in Temples
Venue: arXiv cs.CV 2019
Year: 2019

Recognition of ancient Tamil characters has always been a challenge for epigraphers. This is primarily because the language has evolved over the several centuries and the character set over this time has both expanded and diversified. This proposed work focuses on improving optical character recognition techniques for ancient Tamil script which was in use between the 7th and 12th centuries. While comprehensively curating a functional data set for ancient Tamil characters is an arduous task, in this work, a data set has been curated using cropped images of characters found on certain temple inscriptions, specific to this time as a case study. After using Otsu thresholding method for binarization of the image a two dimensional convolution neural network is defined and used to train, classify and, recognize the ancient Tamil characters. To implement the optical character recognition techniques, the neural network is linked to the Tesseract using the pytesseract library of Python. As an added feature, the work also incorporates Google's text to speech voice engine to produce an audio output of the digitized text. Various samples for both modern and ancient Tamil were collected and passed through the system. It is found that for Tamil inscriptions studied over the considered time period, a combined efficiency of 77.7 percent can be achieved.
Analysis of Ward's Method
Venue: arXiv cs.DS 2019
Year: 2019

We study Ward's method for the hierarchical $k$-means problem. This popular greedy heuristic is based on the \emph{complete linkage} paradigm: Starting with all data points as singleton clusters, it successively merges two clusters to form a clustering with one cluster less. The pair of clusters is chosen to (locally) minimize the $k$-means cost of the clustering in the next step. Complete linkage algorithms are very popular for hierarchical clustering problems, yet their theoretical properties have been studied relatively little. For the Euclidean $k$-center problem, Ackermann et al. show that the $k$-clustering in the hierarchy computed by complete linkage has a worst-case approximation ratio of $Θ(\log k)$. If the data lies in $\mathbb{R}^d$ for constant dimension $d$, the guarantee improves to $\mathcal{O}(1)$, but the $\mathcal{O}$-notation hides a linear dependence on $d$. Complete linkage for $k$-median or $k$-means has not been analyzed so far. In this paper, we show that Ward's method computes a $2$-approximation with respect to the $k$-means objective function if the optimal $k$-clustering is well separated. If additionally the optimal clustering also satisfies a balance condition, then Ward's method fully recovers the optimum solution. These results hold in arbitrary dimension. We accompany our positive results with a lower bound of $Ω((3/2)^d)$ for data sets in $\mathbb{R}^d$ that holds if no separation is guaranteed, and with lower bounds when the guaranteed separation is not sufficiently strong. Finally, we show that Ward produces an $\mathcal{O}(1)$-approximative clustering for one-dimensional data sets.
Approximate Model Counting, Sparse XOR Constraints and Minimum Distance
Venue: arXiv cs.LO 2019
Year: 2019

The problem of counting the number of models of a given Boolean formula has numerous applications, including computing the leakage of deterministic programs in Quantitative Information Flow. Model counting is a hard, #P-complete problem. For this reason, many approximate counters have been developed in the last decade, offering formal guarantees of confidence and accuracy. A popular approach is based on the idea of using random XOR constraints to, roughly, successively halving the solution set until no model is left: this is checked by invocations to a SAT solver. The effectiveness of this procedure hinges on the ability of the SAT solver to deal with XOR constraints, which in turn crucially depends on the length of such constraints. We study to what extent one can employ sparse, hence short, constraints, keeping guarantees of correctness. We show that the resulting bounds are closely related to the geometry of the set of models, in particular to the minimum Hamming distance between models. We evaluate our theoretical results on a few concrete formulae. Based on our findings, we finally discuss possible directions for improvements of the current state of the art in approximate model counting.
Enhancing Spectral Utilization by Maximizing the Reuse in LTE Network
Venue: arXiv cs.NI 2019
Year: 2019

Need for increased spectral efficiency is key to improve the quality of experience for next-generation wireless applications like online gaming, HD Video, etc.,. In our work, we consider an LTE Device-to-device (D2D) network where LTE UEs have primary access to the spectrum and D2D pairs have secondary access. To enhance spectral efficiency, BS can offload the traffic by activating multiple D2D pairs within the serving cell. This ensures that the same radio resource will be reused across the primary LTE UEs and different D2D pairs. In this context, we propose to enable more D2D secondary users in the serving cell, by utilizing neighboring BS spectrum to fairly co-exist with neighboring LTE primary users. We model the system and show via extensive simulations, that the above configuration guarantees good throughput for the D2D pairs in the serving cell while ensuring that the primary LTE throughput demand is not compromised.
Cross-layer Design for Mission-Critical IoT in Mobile Edge Computing Systems
Venue: arXiv cs.NI 2019
Year: 2019

In this work, we propose a cross-layer framework for optimizing user association, packet offloading rates, and bandwidth allocation for Mission-Critical Internet-of-Things (MC-IoT) services with short packets in Mobile Edge Computing (MEC) systems, where enhanced Mobile BroadBand (eMBB) services with long packets are considered as background services. To reduce communication delay, the 5th generation new radio is adopted in radio access networks. To avoid long queueing delay for short packets from MC-IoT, Processor-Sharing (PS) servers are deployed at MEC systems, where the service rate of the server is equally allocated to all the packets in the buffer. We derive the distribution of latency experienced by short packets in closed-form, and minimize the overall packet loss probability subject to the end-to-end delay requirement. To solve the non-convex optimization problem, we propose an algorithm that converges to a near optimal solution when the throughput of eMBB services is much higher than MC-IoT services, and extend it into more general scenarios. Furthermore, we derive the optimal solutions in two asymptotic cases: communication or computing is the bottleneck of reliability. Simulation and numerical results validate our analysis and show that the PS server outperforms first-come-first-serve servers.
Visualizing and Describing Fine-grained Categories as Textures
Venue: arXiv cs.CV 2019
Year: 2019

We analyze how categories from recent FGVC challenges can be described by their textural content. The motivation is that subtle differences between species of birds or butterflies can often be described in terms of the texture associated with them and that several top-performing networks are inspired by texture-based representations. These representations are characterized by orderless pooling of second-order filter activations such as in bilinear CNNs and the winner of the iNaturalist 2018 challenge. Concretely, for each category we (i) visualize the "maximal images" by obtaining inputs x that maximize the probability of the particular class according to a texture-based deep network, and (ii) automatically describe the maximal images using a set of texture attributes. The models for texture captioning were trained on our ongoing efforts on collecting a dataset of describable textures building on the DTD dataset. These visualizations indicate what aspects of the texture is most discriminative for each category while the descriptions provide a language-based explanation of the same.
Beyond Imitation: Generative and Variational Choreography via Machine Learning
Venue: arXiv cs.LG 2019
Year: 2019

Our team of dance artists, physicists, and machine learning researchers has collectively developed several original, configurable machine-learning tools to generate novel sequences of choreography as well as tunable variations on input choreographic sequences. We use recurrent neural network and autoencoder architectures from a training dataset of movements captured as 53 three-dimensional points at each timestep. Sample animations of generated sequences and an interactive version of our model can be found at http: //www.beyondimitation.com.
Time2Vec: Learning a Vector Representation of Time
Venue: arXiv cs.LG 2019
Year: 2019

Time is an important feature in many applications involving events that occur synchronously and/or asynchronously. To effectively consume time information, recent studies have focused on designing new architectures. In this paper, we take an orthogonal but complementary approach by providing a model-agnostic vector representation for time, called Time2Vec, that can be easily imported into many existing and future architectures and improve their performances. We show on a range of models and problems that replacing the notion of time with its Time2Vec representation improves the performance of the final model.
Improving Neural Relation Extraction with Implicit Mutual Relations
Venue: arXiv cs.CL 2019
Year: 2019

Relation extraction (RE) aims at extracting the relation between two entities from the text corpora. It is a crucial task for Knowledge Graph (KG) construction. Most existing methods predict the relation between an entity pair by learning the relation from the training sentences, which contain the targeted entity pair. In contrast to existing distant supervision approaches that suffer from insufficient training corpora to extract relations, our proposal of mining implicit mutual relation from the massive unlabeled corpora transfers the semantic information of entity pairs into the RE model, which is more expressive and semantically plausible. After constructing an entity proximity graph based on the implicit mutual relations, we preserve the semantic relations of entity pairs via embedding each vertex of the graph into a low-dimensional space. As a result, we can easily and flexibly integrate the implicit mutual relations and other entity information, such as entity types, into the existing RE methods. Our experimental results on a New York Times and another Google Distant Supervision datasets suggest that our proposed neural RE framework provides a promising improvement for the RE task, and significantly outperforms the state-of-the-art methods. Moreover, the component for mining implicit mutual relations is so flexible that can help to improve the performance of both CNN-based and RNN-based RE models significant.
Online Inference and Detection of Curbs in Partially Occluded Scenes with Sparse LIDAR
Venue: arXiv cs.RO 2019
Year: 2019

Road boundaries, or curbs, provide autonomous vehicles with essential information when interpreting road scenes and generating behaviour plans. Although curbs convey important information, they are difficult to detect in complex urban environments (in particular in comparison to other elements of the road such as traffic signs and road markings). These difficulties arise from occlusions by other traffic participants as well as changing lighting and/or weather conditions. Moreover, road boundaries have various shapes, colours and structures while motion planning algorithms require accurate and precise metric information in real-time to generate their plans. In this paper, we present a real-time LIDAR-based approach for accurate curb detection around the vehicle (360 degree). Our approach deals with both occlusions from traffic and changing environmental conditions. To this end, we project 3D LIDAR pointcloud data into 2D bird's-eye view images (akin to Inverse Perspective Mapping). These images are then processed by trained deep networks to infer both visible and occluded road boundaries. Finally, a post-processing step filters detected curb segments and tracks them over time. Experimental results demonstrate the effectiveness of the proposed approach on real-world driving data. Hence, we believe that our LIDAR-based approach provides an efficient and effective way to detect visible and occluded curbs around the vehicles in challenging driving scenarios.
Provably Efficient Reinforcement Learning with Linear Function Approximation
Venue: arXiv cs.LG 2019
Year: 2019

Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation tradeoff. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic setting with linear dynamics and linear rewards, for which only linear function approximation is needed. This paper presents the first provable RL algorithm with both polynomial runtime and polynomial sample complexity in this linear setting, without requiring a "simulator" or additional assumptions. Concretely, we prove that an optimistic modification of Least-Squares Value Iteration (LSVI)---a classical algorithm frequently studied in the linear setting---achieves $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret, where $d$ is the ambient dimension of feature space, $H$ is the length of each episode, and $T$ is the total number of steps. Importantly, such regret is independent of the number of states and actions.
Timely Cloud Computing: Preemption and Waiting
Venue: arXiv cs.IT 2019
Year: 2019

The notion of timely status updating is investigated in the context of cloud computing. Measurements of a time-varying process of interest are acquired by a sensor node, and uploaded to a cloud server to undergo some required computations. These computations consume random amounts of service time that are independent and identically distributed across different uploads. After the computations are done, the results are delivered to a monitor, constituting an update. The goal is to keep the monitor continuously fed with fresh updates over time, which is assessed by an age-of-information (AoI) metric. A scheduler is employed to optimize the measurement acquisition times. Following an update, an idle waiting period may be imposed by the scheduler before acquiring a new measurement. The scheduler also has the capability to preempt a measurement in progress if its service time grows above a certain cutoff time, and upload a fresher measurement in its place. Focusing on stationary deterministic policies, in which waiting times are deterministic functions of the instantaneous AoI and the cutoff time is fixed for all uploads, it is shown that the optimal waiting policy that minimizes the long term average AoI has a threshold structure, in which a new measurement is uploaded following an update only if the AoI grows above a certain threshold that is a function of the service time distribution and the cutoff time. The optimal cutoff is then found for standard and shifted exponential service times. While it has been previously reported that waiting before updating can be beneficial for AoI, it is shown in this work that preemption of late updates can be even more beneficial.
Learning Key-Value Store Design
Venue: arXiv cs.DB 2019
Year: 2019

We introduce the concept of design continuums for the data layout of key-value stores. A design continuum unifies major distinct data structure designs under the same model. The critical insight and potential long-term impact is that such unifying models 1) render what we consider up to now as fundamentally different data structures to be seen as views of the very same overall design space, and 2) allow seeing new data structure designs with performance properties that are not feasible by existing designs. The core intuition behind the construction of design continuums is that all data structures arise from the very same set of fundamental design principles, i.e., a small set of data layout design concepts out of which we can synthesize any design that exists in the literature as well as new ones. We show how to construct, evaluate, and expand, design continuums and we also present the first continuum that unifies major data structure designs, i.e., B+tree, B-epsilon-tree, LSM-tree, and LSH-table. The practical benefit of a design continuum is that it creates a fast inference engine for the design of data structures. For example, we can predict near instantly how a specific design change in the underlying storage of a data system would affect performance, or reversely what would be the optimal data structure (from a given set of designs) given workload characteristics and a memory budget. In turn, these properties allow us to envision a new class of self-designing key-value stores with a substantially improved ability to adapt to workload and hardware changes by transitioning between drastically different data structure designs to assume a diverse set of performance properties at will.
Compositional Inference Metaprogramming with Convergence Guarantees
Venue: arXiv cs.PL 2019
Year: 2019

Inference metaprogramming enables effective probabilistic programming by supporting the decomposition of executions of probabilistic programs into subproblems and the deployment of hybrid probabilistic inference algorithms that apply different probabilistic inference algorithms to different subproblems. We introduce the concept of independent subproblem inference (as opposed to entangled subproblem inference in which the subproblem inference algorithm operates over the full program trace) and present a mathematical framework for studying convergence properties of hybrid inference algorithms that apply different Markov-Chain Monte Carlo algorithms to different parts of the inference problem. We then use this formalism to prove asymptotic convergence results for probablistic programs with inference metaprogramming. To the best of our knowledge this is the first asymptotic convergence result for hybrid probabilistic inference algorithms defined by (subproblem-based) inference metaprogramming.
Data by Proxy -- Material Traces as Autographic Visualizations
Venue: arXiv cs.HC 2019
Year: 2019

Information visualization limits itself, per definition, to the domain of symbolic information. This paper discusses arguments why the field should also consider forms of data that are not symbolically encoded, including physical traces and material indicators. Continuing a provocation presented by Pat Hanrahan in his 2004 IEEE Vis capstone address, this paper compares physical traces to visualizations and describes the techniques and visual practices for producing, revealing, and interpreting them. By contrasting information visualization with a speculative counter model of autographic visualization, this paper examines the design principles for material data. Autographic visualization addresses limitations of information visualization, such as the inability to directly reflect the material circumstances of data generation. The comparison between the two models allows probing the epistemic assumptions behind information visualization and uncovers linkages with the rich history of scientific visualization and trace reading.
Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere
Venue: arXiv cs.CC 2019
Year: 2019

Inspired by the boolean discrepancy problem, we study the following optimization problem which we term \textsc{Spherical Discrepancy}: given $m$ unit vectors $v_1, \dots, v_m$, find another unit vector $x$ that minimizes $\max_i \langle x, v_i\rangle$. We show that \textsc{Spherical Discrepancy} is APX-hard and develop a multiplicative weights-based algorithm that achieves optimal worst-case error bounds up to lower order terms. We use our algorithm to give the first non-trivial lower bounds for the problem of covering a hypersphere by hyperspherical caps of uniform volume at least $2^{-o(\sqrt{n})}$. We accomplish this by proving a related covering bound in Gaussian space and showing that in this \textit{large cap regime} the bound transfers to spherical space. Up to a log factor, our lower bounds match known upper bounds in the large cap regime.
MLR (Memory, Learning and Recognition): A General Cognitive Model -- applied to Intelligent Robots and Systems Control
Venue: arXiv cs.AI 2019
Year: 2019

This paper introduces a new perspective of intelligent robots and systems control. The presented and proposed cognitive model: Memory, Learning and Recognition (MLR), is an effort to bridge the gap between Robotics, AI, Cognitive Science, and Neuroscience. The currently existing gap prevents us from integrating the current advancement and achievements of these four research fields which are actively trying to define intelligence in either application-based way or in generic way. This cognitive model defines intelligence more specifically, parametrically and detailed. The proposed MLR model helps us create a general control model for robots and systems independent of their application domains and platforms since it is mainly based on the dataset provided for robots and systems controls. This paper is mainly proposing and introducing this concept and trying to prove this concept in a small scale, firstly through experimentation. The proposed concept is also applicable to other different platforms in real-time as well as in simulation.