OpenRaiser/Intern-Atlas huggingface dataset:
Implicit Entity Linking in Tweets
Venue: arXiv cs.CL 2017
Year: 2017

Over the years, Twitter has become one of the largest communication platforms providing key data to various applications such as brand monitoring, trend detection, among others. Entity linking is one of the major tasks in natural language understanding from tweets and it associates entity mentions in text to corresponding entries in knowledge bases in order to provide unambiguous interpretation and additional con- text. State-of-the-art techniques have focused on linking explicitly mentioned entities in tweets with reasonable success. However, we argue that in addition to explicit mentions i.e. The movie Gravity was more ex- pensive than the mars orbiter mission entities (movie Gravity) can also be mentioned implicitly i.e. This new space movie is crazy. you must watch it!. This paper introduces the problem of implicit entity linking in tweets. We propose an approach that models the entities by exploiting their factual and contextual knowledge. We demonstrate how to use these models to perform implicit entity linking on a ground truth dataset with 397 tweets from two domains, namely, Movie and Book. Specifically, we show: 1) the importance of linking implicit entities and its value addition to the standard entity linking task, and 2) the importance of exploiting contextual knowledge associated with an entity for linking their implicit mentions. We also make the ground truth dataset publicly available to foster the research in this new research area.
A Guided Spatial Transformer Network for Histology Cell Differentiation
Venue: arXiv cs.CV 2017
Year: 2017

Identification and counting of cells and mitotic figures is a standard task in diagnostic histopathology. Due to the large overall cell count on histological slides and the potential sparse prevalence of some relevant cell types or mitotic figures, retrieving annotation data for sufficient statistics is a tedious task and prone to a significant error in assessment. Automatic classification and segmentation is a classic task in digital pathology, yet it is not solved to a sufficient degree. We present a novel approach for cell and mitotic figure classification, based on a deep convolutional network with an incorporated Spatial Transformer Network. The network was trained on a novel data set with ten thousand mitotic figures, about ten times more than previous data sets. The algorithm is able to derive the cell class (mitotic tumor cells, non-mitotic tumor cells and granulocytes) and their position within an image. The mean accuracy of the algorithm in a five-fold cross-validation is 91.45%. In our view, the approach is a promising step into the direction of a more objective and accurate, semi-automatized mitosis counting supporting the pathologist.
Public Evidence from Secret Ballots
Venue: arXiv cs.CR 2017
Year: 2017

Elections seem simple---aren't they just counting? But they have a unique, challenging combination of security and privacy requirements. The stakes are high; the context is adversarial; the electorate needs to be convinced that the results are correct; and the secrecy of the ballot must be ensured. And they have practical constraints: time is of the essence, and voting systems need to be affordable and maintainable, and usable by voters, election officials, and pollworkers. It is thus not surprising that voting is a rich research area spanning theory, applied cryptography, practical systems analysis, usable security, and statistics. Election integrity involves two key concepts: convincing evidence that outcomes are correct and privacy, which amounts to convincing assurance that there is no evidence about how any given person voted. These are obviously in tension. We examine how current systems walk this tightrope.
A Feasibility Study of Using Light Fidelity With Multiple Unmanned Aerial Vehicles For Indoor Collaborative And Cooperative Networking
Venue: arXiv cs.NI 2017
Year: 2017

This paper evaluates the feasibility of using light fidelity with multiple Unmanned Aerial Vehicles (UAVs) for indoor collaborative and cooperative networking. A number of works have presentedchallenges for wireless networking with multiple UAVs such as bandwidth efficiency, security and environment amongst others. Due to this fact, there is a need to secure information and data in UAV ad hoc network (FANETs) using a secure transmission medium that guarantees bandwidth efficiency such as the light fidelity (Li-Fi). Li-Fi enables data transmission using visible light through a light emitting diode (LED) and is chosen as against wireless fidelity (Wi- Fi) because it is more ideal for high density wireless data coverage in confined areas, better at addressing radio interference related issues and provides better bandwidth, efficiency, availability and security. Thus, using Light Fidelity as a means of communication necessitates the need to develop a Link Velocity Based Connectivity Algorithm (LVCA) that governs communication between the UAVs and the Li-Fi transmitter and receiver circuits for collaborative and cooperative networking.
An Epistemic Foundation for Authentication Logics (Extended Abstract)
Venue: arXiv cs.CR 2017
Year: 2017

While there have been many attempts, going back to BAN logic, to base reasoning about security protocols on epistemic notions, they have not been all that successful. Arguably, this has been due to the particular logics chosen. We present a simple logic based on the well-understood modal operators of knowledge, time, and probability, and show that it is able to handle issues that have often been swept under the rug by other approaches, while being flexible enough to capture all the higher- level security notions that appear in BAN logic. Moreover, while still assuming that the knowledge operator allows for unbounded computation, it can handle the fact that a computationally bounded agent cannot decrypt messages in a natural way, by distinguishing strings and message terms. We demonstrate that our logic can capture BAN logic notions by providing a translation of the BAN operators into our logic, capturing belief by a form of probabilistic knowledge.
Indicative Conditionals and Dynamic Epistemic Logic
Venue: arXiv cs.LO 2017
Year: 2017

Recent ideas about epistemic modals and indicative conditionals in formal semantics have significant overlap with ideas in modal logic and dynamic epistemic logic. The purpose of this paper is to show how greater interaction between formal semantics and dynamic epistemic logic in this area can be of mutual benefit. In one direction, we show how concepts and tools from modal logic and dynamic epistemic logic can be used to give a simple, complete axiomatization of Yalcin's [16] semantic consequence relation for a language with epistemic modals and indicative conditionals. In the other direction, the formal semantics for indicative conditionals due to Kolodny and MacFarlane [9] gives rise to a new dynamic operator that is very natural from the point of view of dynamic epistemic logic, allowing succinct expression of dependence (as in dependence logic) or supervenience statements. We prove decidability for the logic with epistemic modals and Kolodny and MacFarlane's indicative conditional via a full and faithful computable translation from their logic to the modal logic K45.
Group Recommendations: Axioms, Impossibilities, and Random Walks
Venue: arXiv cs.SI 2017
Year: 2017

We introduce an axiomatic approach to group recommendations, in line of previous work on the axiomatic treatment of trust-based recommendation systems, ranking systems, and other foundational work on the axiomatic approach to internet mechanisms in social choice settings. In group recommendations we wish to recommend to a group of agents, consisting of both opinionated and undecided members, a joint choice that would be acceptable to them. Such a system has many applications, such as choosing a movie or a restaurant to go to with a group of friends, recommending games for online game players, & other communal activities. Our method utilizes a given social graph to extract information on the undecided, relying on the agents influencing them. We first show that a set of fairly natural desired requirements (a.k.a axioms) leads to an impossibility, rendering mutual satisfaction of them unreachable. However, we also show a modified set of axioms that fully axiomatize a group variant of the random-walk recommendation system, expanding a previous result from the individual recommendation case.
Argument-based Belief in Topological Structures
Venue: arXiv cs.AI 2017
Year: 2017

This paper combines two studies: a topological semantics for epistemic notions and abstract argumentation theory. In our combined setting, we use a topological semantics to represent the structure of an agent's collection of evidence, and we use argumentation theory to single out the relevant sets of evidence through which a notion of beliefs grounded on arguments is defined. We discuss the formal properties of this newly defined notion, providing also a formal language with a matching modality together with a sound and complete axiom system for it. Despite the fact that our agent can combine her evidence in a 'rational' way (captured via the topological structure), argument-based beliefs are not closed under conjunction. This illustrates the difference between an agent's reasoning abilities (i.e. the way she is able to combine her available evidence) and the closure properties of her beliefs. We use this point to argue for why the failure of closure under conjunction of belief should not bear the burden of the failure of rationality.
Reconciling Bayesian Epistemology and Narration-based Approaches to Judiciary Fact-finding
Venue: arXiv cs.AI 2017
Year: 2017

Legal probabilism (LP) claims the degrees of conviction in juridical fact-finding are to be modeled exactly the way degrees of beliefs are modeled in standard bayesian epistemology. Classical legal probabilism (CLP) adds that the conviction is justified if the credence in guilt given the evidence is above an appropriate guilt probability threshold. The views are challenged on various counts, especially by the proponents of the so-called narrative approach, on which the fact-finders' decision is the result of a dynamic interplay between competing narratives of what happened. I develop a way a bayesian epistemologist can make sense of the narrative approach. I do so by formulating a probabilistic framework for evaluating competing narrations in terms of formal explications of the informal evaluation criteria used in the narrative approach.
A New Modal Framework for Epistemic Logic
Venue: arXiv cs.AI 2017
Year: 2017

Recent years witnessed a growing interest in non-standard epistemic logics of knowing whether, knowing how, knowing what, knowing why and so on. The new epistemic modalities introduced in those logics all share, in their semantics, the general schema of $\exists x \Box ϕ$, e.g., knowing how to achieve $ϕ$ roughly means that there exists a way such that you know that it is a way to ensure that $ϕ$. Moreover, the resulting logics are decidable. Inspired by those particular logics, in this work, we propose a very general and powerful framework based on quantifier-free predicate language extended by a new modality $\Box^x$, which packs exactly $\exists x \Box$ together. We show that the resulting language, though much more expressive, shares many good properties of the basic propositional modal logic over arbitrary models, such as finite-tree-model property and van Benthem-like characterization w.r.t.\ first-order modal logic. We axiomatize the logic over S5 frames with intuitive axioms to capture the interaction between $\Box^x$ and know-that operator in an epistemic setting.
Food Ingredients Recognition through Multi-label Learning
Venue: arXiv cs.CV 2017
Year: 2017

Automatically constructing a food diary that tracks the ingredients consumed can help people follow a healthy diet. We tackle the problem of food ingredients recognition as a multi-label learning problem. We propose a method for adapting a highly performing state of the art CNN in order to act as a multi-label predictor for learning recipes in terms of their list of ingredients. We prove that our model is able to, given a picture, predict its list of ingredients, even if the recipe corresponding to the picture has never been seen by the model. We make public two new datasets suitable for this purpose. Furthermore, we prove that a model trained with a high variability of recipes and ingredients is able to generalize better on new data, and visualize how it specializes each of its neurons to different ingredients.
Serious Games Application for Memory Training Using Egocentric Images
Venue: arXiv cs.CV 2017
Year: 2017

Mild cognitive impairment is the early stage of several neurodegenerative diseases, such as Alzheimer's. In this work, we address the use of lifelogging as a tool to obtain pictures from a patient's daily life from an egocentric point of view. We propose to use them in combination with serious games as a way to provide a non-pharmacological treatment to improve their quality of life. To do so, we introduce a novel computer vision technique that classifies rich and non rich egocentric images and uses them in serious games. We present results over a dataset composed by 10,997 images, recorded by 7 different users, achieving 79% of F1-score. Our model presents the first method used for automatic egocentric images selection applicable to serious games.
Approximations and Bounds for (n, k) Fork-Join Queues: A Linear Transformation Approach
Venue: arXiv cs.PF 2017
Year: 2017

Compared to basic fork-join queues, a job in (n, k) fork-join queues only needs its k out of all n sub-tasks to be finished. Since (n, k) fork-join queues are prevalent in popular distributed systems, erasure coding based cloud storages, and modern network protocols like multipath routing, estimating the sojourn time of such queues is thus critical for the performance measurement and resource plan of computer clusters. However, the estimating keeps to be a well-known open challenge for years, and only rough bounds for a limited range of load factors have been given. In this paper, we developed a closed-form linear transformation technique for jointly-identical random variables: An order statistic can be represented by a linear combination of maxima. This brand-new technique is then used to transform the sojourn time of non-purging (n, k) fork-join queues into a linear combination of the sojourn times of basic (k, k), (k+1, k+1), ..., (n, n) fork-join queues. Consequently, existing approximations for basic fork-join queues can be bridged to the approximations for non-purging (n, k) fork-join queues. The uncovered approximations are then used to improve the upper bounds for purging (n, k) fork-join queues. Simulation experiments show that this linear transformation approach is practiced well for moderate n and relatively large k.
Effective Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges
Venue: arXiv cs.DS 2017
Year: 2017

Computing \emph{all best swap edges} (ABSE) of a spanning tree $T$ of a given $n$-vertex and $m$-edge undirected and weighted graph $G$ means to select, for each edge $e$ of $T$, a corresponding non-tree edge $f$, in such a way that the tree obtained by replacing $e$ with $f$ enjoys some optimality criterion (which is naturally defined according to some objective function originally addressed by $T$). Solving efficiently an ABSE problem is by now a classic algorithmic issue, since it conveys a very successful way of coping with a (transient) \emph{edge failure} in tree-based communication networks: just replace the failing edge with its respective swap edge, so as that the connectivity is promptly reestablished by minimizing the rerouting and set-up costs. In this paper, we solve the ABSE problem for the case in which $T$ is a \emph{single-source shortest-path tree} of $G$, and our two selected swap criteria aim to minimize either the \emph{maximum} or the \emph{average stretch} in the swap tree of all the paths emanating from the source. Having these criteria in mind, the obtained structures can then be reviewed as \emph{edge-fault-tolerant single-source spanners}. For them, we propose two efficient algorithms running in $O(m n +n^2 \log n)$ and $O(m n \log α(m,n))$ time, respectively, and we show that the guaranteed (either maximum or average, respectively) stretch factor is equal to 3, and this is tight. Moreover, for the maximum stretch, we also propose an almost linear $O(m \log α(m,n))$ time algorithm computing a set of \emph{good} swap edges, each of which will guarantee a relative approximation factor on the maximum stretch of $3/2$ (tight) as opposed to that provided by the corresponding BSE. Surprisingly, no previous results were known for these two very natural swap problems.
Non-Coherent Detection for Diffusive Molecular Communications
Venue: arXiv cs.IT 2017
Year: 2017

We study non-coherent detection schemes for molecular communication (MC) systems that do not require knowledge of the channel state information (CSI). In particular, we first derive the optimal maximum likelihood (ML) multiple-symbol (MS) detector for MC systems. As a special case of the optimal MS detector, we show that the optimal ML symbol-by-symbol (SS) detector can be equivalently written in the form of a threshold-based detector, where the optimal decision threshold is constant and depends only on the statistics of the MC channel. The main challenge of the MS detector is the complexity associated with the calculation of the optimal detection metric. To overcome this issue, we propose an approximate MS detection metric which can be expressed in closed form. To reduce complexity even further, we develop a non-coherent decision-feedback (DF) detector and a suboptimal blind detector. Finally, we derive analytical expressions for the bit error rate (BER) of the optimal SS detector, as well as upper and lower bounds for the BER of the optimal MS detector. Simulation results confirm the analysis and reveal the effectiveness of the proposed optimal and suboptimal detection schemes compared to a benchmark scheme that assumes perfect CSI knowledge, particularly when the number of observations used for detection is sufficiently large.
Line codes generated by finite Coxeter groups
Venue: arXiv cs.IT 2017
Year: 2017

Using an algebraic approach based on the theory of Coxeter groups, we design, and describe the performance of, a class of line codes for parallel transmission of $b$ bits over $b+1$ wires that admit especially simple encoding and decoding algorithms. A number of designs are exhibited, some of them being novel or improving on previously obtained codes.
Evolution towards Smart Optical Networking: Where Artificial Intelligence (AI) meets the World of Photonics
Venue: arXiv cs.NI 2017
Year: 2017

Smart optical networks are the next evolution of programmable networking and programmable automation of optical networks, with human-in-the-loop network control and management. The paper discusses this evolution and the role of Artificial Intelligence (AI).
The Convergence of Least-Squares Progressive Iterative Approximation with Singular Iterative Matrix
Venue: arXiv cs.NA 2017
Year: 2017

Developed in [Deng and Lin, 2014], Least-Squares Progressive Iterative Approximation (LSPIA) is an efficient iterative method for solving B-spline curve and surface least-squares fitting systems. In [Deng and Lin 2014], it was shown that LSPIA is convergent when the iterative matrix is nonsingular. In this paper, we will show that LSPIA is still convergent even the iterative matrix is singular.
Deep Co-Space: Sample Mining Across Feature Transformation for Semi-Supervised Learning
Venue: arXiv cs.CV 2017
Year: 2017

Aiming at improving performance of visual classification in a cost-effective manner, this paper proposes an incremental semi-supervised learning paradigm called Deep Co-Space (DCS). Unlike many conventional semi-supervised learning methods usually performing within a fixed feature space, our DCS gradually propagates information from labeled samples to unlabeled ones along with deep feature learning. We regard deep feature learning as a series of steps pursuing feature transformation, i.e., projecting the samples from a previous space into a new one, which tends to select the reliable unlabeled samples with respect to this setting. Specifically, for each unlabeled image instance, we measure its reliability by calculating the category variations of feature transformation from two different neighborhood variation perspectives, and merged them into an unified sample mining criterion deriving from Hellinger distance. Then, those samples keeping stable correlation to their neighboring samples (i.e., having small category variation in distribution) across the successive feature space transformation, are automatically received labels and incorporated into the model for incrementally training in terms of classification. Our extensive experiments on standard image classification benchmarks (e.g., Caltech-256 and SUN-397) demonstrate that the proposed framework is capable of effectively mining from large-scale unlabeled images, which boosts image classification performance and achieves promising results compared to other semi-supervised learning methods.
Efficient Algorithms for Non-convex Isotonic Regression through Submodular Optimization
Venue: arXiv cs.LG 2017
Year: 2017

We consider the minimization of submodular functions subject to ordering constraints. We show that this optimization problem can be cast as a convex optimization problem on a space of uni-dimensional measures, with ordering constraints corresponding to first-order stochastic dominance. We propose new discretization schemes that lead to simple and efficient algorithms based on zero-th, first, or higher order oracles; these algorithms also lead to improvements without isotonic constraints. Finally, our experiments show that non-convex loss functions can be much more robust to outliers for isotonic regression, while still leading to an efficient optimization problem.
Mining Device-Specific Apps Usage Patterns from Large-Scale Android Users
Venue: arXiv cs.SE 2017
Year: 2017

When smartphones, applications (a.k.a, apps), and app stores have been widely adopted by the billions, an interesting debate emerges: whether and to what extent do device models influence the behaviors of their users? The answer to this question is critical to almost every stakeholder in the smartphone app ecosystem, including app store operators, developers, end-users, and network providers. To approach this question, we collect a longitudinal data set of app usage through a leading Android app store in China, called Wandoujia. The data set covers the detailed behavioral profiles of 0.7 million (761,262) unique users who use 500 popular types of Android devices and about 0.2 million (228,144) apps, including their app management activities, daily network access time, and network traffic of apps. We present a comprehensive study on investigating how the choices of device models affect user behaviors such as the adoption of app stores, app selection and abandonment, data plan usage, online time length, the tendency to use paid/free apps, and the preferences to choosing competing apps. Some significant correlations between device models and app usage are derived, leading to important findings on the various user behaviors. For example, users owning different device models have a substantial diversity of selecting competing apps, and users owning lower-end devices spend more money to purchase apps and spend more time under cellular network.