OpenRaiser/Intern-Atlas huggingface dataset:
Online Pandora's Boxes and Bandits
Venue: arXiv cs.DS 2019
Year: 2019

We consider online variations of the Pandora's box problem (Weitzman. 1979), a standard model for understanding issues related to the cost of acquiring information for decision-making. Our problem generalizes both the classic Pandora's box problem and the prophet inequality framework. Boxes are presented online, each with a random value and cost drew jointly from some known distribution. Pandora chooses online whether to open each box given its cost, and then chooses irrevocably whether to keep the revealed prize or pass on it. We aim for approximation algorithms against adversaries that can choose the largest prize over any opened box, and use optimal offline policies to decide which boxes to open (without knowledge of the value inside). We consider variations where Pandora can collect multiple prizes subject to feasibility constraints, such as cardinality, matroid, or knapsack constraints. We also consider variations related to classic multi-armed bandit problems from reinforcement learning. Our results use a reduction-based framework where we separate the issues of the cost of acquiring information from the online decision process of which prizes to keep. Our work shows that in many scenarios, Pandora can achieve a good approximation to the best possible performance.
Effects of Moderation and Opinion Heterogeneity on Attitude towards the Online Deliberation Experience
Venue: arXiv cs.HC 2019
Year: 2019

Online deliberation offers a way for citizens to collectively discuss an issue and provide input for policy makers. The overall experience of online deliberation can be affected by multiple factors. We decided to investigate the effects of moderation and opinion heterogeneity on the perceived deliberation experience, by running the first online deliberation experiment in Singapore. Our study took place in three months with three phases. In phase 1, our 2,006 participants answered a survey, that we used to create groups of different opinion heterogeneity. During the second phase, 510 participants discussed about the population issue on the online platform we developed. We gathered data on their online deliberation experience during phase 3. We found out that higher levels of moderation negatively impact the experience of deliberation on perceived procedural fairness, validity claim and policy legitimacy; and that high opinion heterogeneity is important in order to get a fair assessment of the deliberation experience.
View Invariant 3D Human Pose Estimation
Venue: arXiv cs.CV 2019
Year: 2019

The recent success of deep networks has significantly advanced 3D human pose estimation from 2D images. The diversity of capturing viewpoints and the flexibility of the human poses, however, remain some significant challenges. In this paper, we propose a view invariant 3D human pose estimation module to alleviate the effects of viewpoint diversity. The framework consists of a base network, which provides an initial estimation of a 3D pose, a view-invariant hierarchical correction network (VI-HC) on top of that to learn the 3D pose refinement under consistent views, and a view-invariant discriminative network (VID) to enforce high-level constraints over body configurations. In VI-HC, the initial 3D pose inputs are automatically transformed to consistent views for further refinements at the global body and local body parts level, respectively. For the VID, under consistent viewpoints, we use adversarial learning to differentiate between estimated poses and real poses to avoid implausible 3D poses. Experimental results demonstrate that the consistent viewpoints can dramatically enhance the performance. Our module shows robustness for different 3D pose base networks and achieves a significant improvement (about 9%) over a powerful baseline on the public 3D pose estimation benchmark Human3.6M.
Comparing Election Methods Where Each Voter Ranks Only Few Candidates
Venue: arXiv cs.DS 2019
Year: 2019

Election rules are formal processes that aggregate voters preferences, typically to select a single candidate, called the winner. Most of the election rules studied in the literature require the voters to rank the candidates from the most to the least preferred one. This method of eliciting preferences is impractical when the number of candidates to be ranked is large. We ask how well certain election rules (focusing on positional scoring rules and the Minimax rule) can be approximated from partial preferences collected through one of the following procedures: (i) randomized-we ask each voter to rank a random subset of $\ell$ candidates, and (ii) deterministic-we ask each voter to provide a ranking of her $\ell$ most preferred candidates (the $\ell$-truncated ballot). We establish theoretical bounds on the approximation ratios and we complement our theoretical analysis with computer simulations. We find that mostly (apart from the cases when the preferences have no or very little structure) it is better to use the randomized approach. While we obtain fairly good approximation guarantees for the Borda rule already for $\ell = 2$, for approximating the Minimax rule one needs to ask each voter to compare a larger set of candidates in order to obtain good guarantees.
Generative Adversarial Network with Multi-Branch Discriminator for Cross-Species Image-to-Image Translation
Venue: arXiv cs.CV 2019
Year: 2019

Current approaches have made great progress on image-to-image translation tasks benefiting from the success of image synthesis methods especially generative adversarial networks (GANs). However, existing methods are limited to handling translation tasks between two species while keeping the content matching on the semantic level. A more challenging task would be the translation among more than two species. To explore this new area, we propose a simple yet effective structure of a multi-branch discriminator for enhancing an arbitrary generative adversarial architecture (GAN), named GAN-MBD. It takes advantage of the boosting strategy to break a common discriminator into several smaller ones with fewer parameters, which can enhance the generation and synthesis abilities of GANs efficiently and effectively. Comprehensive experiments show that the proposed multi-branch discriminator can dramatically improve the performance of popular GANs on cross-species image-to-image translation tasks while reducing the number of parameters for computation. The code and some datasets are attached as supplementary materials for reference.
Evaluation of Appearance-Based Methods and Implications for Gaze-Based Applications
Venue: arXiv cs.HC 2019
Year: 2019

Appearance-based gaze estimation methods that only require an off-the-shelf camera have significantly improved but they are still not yet widely used in the human-computer interaction (HCI) community. This is partly because it remains unclear how they perform compared to model-based approaches as well as dominant, special-purpose eye tracking equipment. To address this limitation, we evaluate the performance of state-of-the-art appearance-based gaze estimation for interaction scenarios with and without personal calibration, indoors and outdoors, for different sensing distances, as well as for users with and without glasses. We discuss the obtained findings and their implications for the most important gaze-based applications, namely explicit eye input, attentive user interfaces, gaze-based user modelling, and passive eye monitoring. To democratise the use of appearance-based gaze estimation and interaction in HCI, we finally present OpenGaze (www.opengaze.org), the first software toolkit for appearance-based gaze estimation and interaction.
A Constructive Equivalence between Computation Tree Logic and Failure Trace Testing
Venue: arXiv cs.LO 2019
Year: 2019

The two major systems of formal verification are model checking and algebraic model-based testing. Model checking is based on some form of temporal logic such as linear temporal logic (LTL) or computation tree logic (CTL). One powerful and realistic logic being used is CTL, which is capable of expressing most interesting properties of processes such as liveness and safety. Model-based testing is based on some operational semantics of processes (such as traces, failures, or both) and its associated preorders. The most fine-grained preorder beside bisimulation (mostly of theoretical importance) is based on failure traces. We show that these two most powerful variants are equivalent; that is, we show that for any failure trace test there exists a CTL formula equivalent to it, and the other way around. All our proofs are constructive and algorithmic. Our result allows for parts of a large system to be specified logically while other parts are specified algebraically, thus combining the best of the two (logic and algebraic) worlds.
Rational Solutions of First-Order Algebraic Ordinary Difference Equations
Venue: arXiv cs.SC 2019
Year: 2019

We propose an algebraic geometric approach for studying rational solutions of first-order algebraic ordinary difference equations. For an autonomous first-order algebraic ordinary difference equations, we give an upper bound for the degrees of its rational solutions, and thus derive a complete algorithm for computing corresponding rational solutions.
On Intra-Class Variance for Deep Learning of Classifiers
Venue: arXiv cs.CV 2019
Year: 2019

A novel technique for deep learning of image classifiers is presented. The learned CNN models offer better separation of deep features (also known as embedded vectors) measured by Euclidean proximity and also no deterioration of the classification results by class membership probability. The latter feature can be used for enhancing image classifiers having the classes at the model's exploiting stage different from from classes during the training stage. While the Shannon information of SoftMax probability for target class is extended for mini-batch by the intra-class variance, the trained network itself is extended by the Hadamard layer with the parameters representing the class centers. Contrary to the existing solutions, this extra neural layer enables interfacing of the training algorithm to the standard stochastic gradient optimizers, e.g. AdaM algorithm. Moreover, this approach makes the computed centroids immediately adapting to the updating embedded vectors and finally getting the comparable accuracy in less epochs.
The Secure Link Prediction Problem
Venue: arXiv cs.CR 2019
Year: 2019

Link Prediction is an important and well-studied problem for social networks. Given a snapshot of a graph, the link prediction problem predicts which new interactions between members are most likely to occur in the near future. As networks grow in size, data owners are forced to store the data in remote cloud servers which reveals sensitive information about the network. The graphs are therefore stored in encrypted form. We study the link prediction problem on encrypted graphs. To the best of our knowledge, this secure link prediction problem has not been studied before. We use the number of common neighbors for prediction. We present three algorithms for the secure link prediction problem. We design prototypes of the schemes and formally prove their security. We execute our algorithms in real-life datasets.
Tree Recognition APP of Mount Tai Based on CNN
Venue: arXiv cs.CV 2019
Year: 2019

Mount Tai has abundant sunshine, abundant rainfall and favorable climatic conditions, forming dense vegetation with various kinds of trees. In order to make it easier for tourists to understand each tree and experience the culture of Mount Tai, this paper develops an App for tree recognition of Mount Tai based on convolution neural network (CNN), taking advantage of CNN efficient image recognition ability and easy-to-carry characteristics of Android mobile phone. The APP can accurately identify several common trees in Mount Tai, and give a brief introduction for tourists.
Funnelling: A New Ensemble Method for Heterogeneous Transfer Learning and its Application to Cross-Lingual Text Classification
Venue: arXiv cs.LG 2019
Year: 2019

Cross-lingual Text Classification (CLC) consists of automatically classifying, according to a common set C of classes, documents each written in one of a set of languages L, and doing so more accurately than when naively classifying each document via its corresponding language-specific classifier. In order to obtain an increase in the classification accuracy for a given language, the system thus needs to also leverage the training examples written in the other languages. We tackle multilabel CLC via funnelling, a new ensemble learning method that we propose here. Funnelling consists of generating a two-tier classification system where all documents, irrespectively of language, are classified by the same (2nd-tier) classifier. For this classifier all documents are represented in a common, language-independent feature space consisting of the posterior probabilities generated by 1st-tier, language-dependent classifiers. This allows the classification of all test documents, of any language, to benefit from the information present in all training documents, of any language. We present substantial experiments, run on publicly available multilingual text collections, in which funnelling is shown to significantly outperform a number of state-of-the-art baselines. All code and datasets (in vector form) are made publicly available.
New insights on Multi-Solution Distribution of the P3P Problem
Venue: arXiv cs.CV 2019
Year: 2019

Traditionally, the P3P problem is solved by firstly transforming its 3 quadratic equations into a quartic one, then by locating the roots of the resulting quartic equation and verifying whether a root does really correspond to a true solution of the P3P problem itself. However, a root of the quartic equation does not always correspond to a solution of the P3P problem. In this work, we show that when the optical center is outside of all the 6 toroids defined by the control point triangle, each positive root of the Grunert's quartic equation must correspond to a true solution of the P3P problem, and the corresponding P3P problem cannot have a unique solution, it must have either 2 positive solutions or 4 positive solutions. In addition, we show that when the optical center passes through any one of the 3 toroids among these 6 toroids ( except possibly for two concentric circles) , the number of the solutions of the corresponding P3P problem always changes by 1, either increased by 1 or decreased by 1.Furthermore we show that such changed solutions always locate in a small neighborhood of control points, hence the 3 toroids are critical surfaces of the P3P problem and the 3 control points are 3 singular points of solutions. A notable example is that when the optical center passes through the outer surface of the union of the 6 toroids from the outside to inside, the number of the solutions must always decrease by 1. Our results are the first to give an explicit and geometrically intuitive relationship between the P3P solutions and the roots of its quartic equation. It could act as some theoretical guidance for P3P practitioners to properly arrange their control points to avoid undesirable solutions.
Text line Segmentation in Compressed Representation of Handwritten Document using Tunneling Algorithm
Venue: arXiv cs.CV 2019
Year: 2019

In this research work, we perform text line segmentation directly in compressed representation of an unconstrained handwritten document image. In this relation, we make use of text line terminal points which is the current state-of-the-art. The terminal points spotted along both margins (left and right) of a document image for every text line are considered as source and target respectively. The tunneling algorithm uses a single agent (or robot) to identify the coordinate positions in the compressed representation to perform text-line segmentation of the document. The agent starts at a source point and progressively tunnels a path routing in between two adjacent text lines and reaches the probable target. The agent's navigation path from source to the target bypassing obstacles, if any, results in segregating the two adjacent text lines. However, the target point would be known only when the agent reaches the destination; this is applicable for all source points and henceforth we could analyze the correspondence between source and target nodes. Artificial Intelligence in Expert systems, dynamic programming and greedy strategies are employed for every search space while tunneling. An exhaustive experimentation is carried out on various benchmark datasets including ICDAR13 and the performances are reported.
Pathologist-level classification of histologic patterns on resected lung adenocarcinoma slides with deep neural networks
Venue: arXiv cs.CV 2019
Year: 2019

Classification of histologic patterns in lung adenocarcinoma is critical for determining tumor grade and treatment for patients. However, this task is often challenging due to the heterogeneous nature of lung adenocarcinoma and the subjective criteria for evaluation. In this study, we propose a deep learning model that automatically classifies the histologic patterns of lung adenocarcinoma on surgical resection slides. Our model uses a convolutional neural network to identify regions of neoplastic cells, then aggregates those classifications to infer predominant and minor histologic patterns for any given whole-slide image. We evaluated our model on an independent set of 143 whole-slide images. It achieved a kappa score of 0.525 and an agreement of 66.6% with three pathologists for classifying the predominant patterns, slightly higher than the inter-pathologist kappa score of 0.485 and agreement of 62.7% on this test set. All evaluation metrics for our model and the three pathologists were within 95% confidence intervals of agreement. If confirmed in clinical practice, our model can assist pathologists in improving classification of lung adenocarcinoma patterns by automatically pre-screening and highlighting cancerous regions prior to review. Our approach can be generalized to any whole-slide image classification task, and code is made publicly available at https://github.com/BMIRDS/deepslide.
Improving generation quality of pointer networks via guided attention
Venue: arXiv cs.LG 2019
Year: 2019

Pointer generator networks have been used successfully for abstractive summarization. Along with the capability to generate novel words, it also allows the model to copy from the input text to handle out-of-vocabulary words. In this paper, we point out two key shortcomings of the summaries generated with this framework via manual inspection, statistical analysis and human evaluation. The first shortcoming is the extractive nature of the generated summaries, since the network eventually learns to copy from the input article most of the times, affecting the abstractive nature of the generated summaries. The second shortcoming is the factual inaccuracies in the generated text despite grammatical correctness. Our analysis indicates that this arises due to incorrect attention transition between different parts of the article. We propose an initial attempt towards addressing both these shortcomings by externally appending traditional linguistic information parsed from the input text, thereby teaching networks on the structure of the underlying text. Results indicate feasibility and potential of such additional cues for improved generation.
Shaping the Narrative Arc: An Information-Theoretic Approach to Collaborative Dialogue
Venue: arXiv cs.HC 2019
Year: 2019

We consider the problem of designing an artificial agent capable of interacting with humans in collaborative dialogue to produce creative, engaging narratives. In this task, the goal is to establish universe details, and to collaborate on an interesting story in that universe, through a series of natural dialogue exchanges. Our model can augment any probabilistic conversational agent by allowing it to reason about universe information established and what potential next utterances might reveal. Ideally, with each utterance, agents would reveal just enough information to add specificity and reduce ambiguity without limiting the conversation. We empirically show that our model allows control over the rate at which the agent reveals information and that doing so significantly improves accuracy in predicting the next line of dialogues from movies. We close with a case-study with four professional theatre performers, who preferred interactions with our model-augmented agent over an unaugmented agent.
Network Parameter Learning Using Nonlinear Transforms, Local Representation Goals and Local Propagation Constraints
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we introduce a novel concept for learning of the parameters in a neural network. Our idea is grounded on modeling a learning problem that addresses a trade-off between (i) satisfying local objectives at each node and (ii) achieving desired data propagation through the network under (iii) local propagation constraints. We consider two types of nonlinear transforms which describe the network representations. One of the nonlinear transforms serves as activation function. The other one enables a locally adjusted, deviation corrective components to be included in the update of the network weights in order to enable attaining target specific representations at the last network node. Our learning principle not only provides insight into the understanding and the interpretation of the learning dynamics, but it offers theoretical guarantees over decoupled and parallel parameter estimation strategy that enables learning in synchronous and asynchronous mode. Numerical experiments validate the potential of our approach on image recognition task. The preliminary results show advantages in comparison to the state-of-the-art methods, w.r.t. the learning time and the network size while having competitive recognition accuracy.
Probabilistic Discriminative Learning with Layered Graphical Models
Venue: arXiv cs.LG 2019
Year: 2019

Probabilistic graphical models are traditionally known for their successes in generative modeling. In this work, we advocate layered graphical models (LGMs) for probabilistic discriminative learning. To this end, we design LGMs in close analogy to neural networks (NNs), that is, they have deep hierarchical structures and convolutional or local connections between layers. Equipped with tensorized truncated variational inference, our LGMs can be efficiently trained via backpropagation on mainstream deep learning frameworks such as PyTorch. To deal with continuous valued inputs, we use a simple yet effective soft-clamping strategy for efficient inference. Through extensive experiments on image classification over MNIST and FashionMNIST datasets, we demonstrate that LGMs are capable of achieving competitive results comparable to NNs of similar architectures, while preserving transparent probabilistic modeling.
On the statistical evaluation of algorithmic's computational experimentation with infeasible solutions
Venue: arXiv cs.LG 2019
Year: 2019

The experimental evaluation of algorithms results in a large set of data which generally do not follow a normal distribution or are not heteroscedastic. Besides, some of its entries may be missing, due to the inability of an algorithm to find a feasible solution until a time limit is met. Those characteristics restrict the statistical evaluation of computational experiments. This work proposes a bi-objective lexicographical ranking scheme to evaluate datasets with such characteristics. The output ranking can be used as input to any desired statistical test. We used the proposed ranking scheme to assess the results obtained by the Iterative Rounding heuristic (IR). A Friedman's test and a subsequent post-hoc test carried out on the ranked data demonstrated that IR performed significantly better than the Feasibility Pump heuristic when solving 152 benchmark problems of Nonconvex Mixed-Integer Nonlinear Problems. However, is also showed that the RECIPE heuristic was significantly better than IR when solving the same benchmark problems.