OpenRaiser/Intern-Atlas huggingface dataset:
Fair Division with a Secretive Agent
Venue: arXiv cs.GT 2018
Year: 2018

We study classic fair-division problems in a partial information setting. This paper respectively addresses fair division of rent, cake, and indivisible goods among agents with cardinal preferences. We will show that, for all of these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n-1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation. For the rent-division setting we prove that the (well-behaved) utilities of n-1 agents suffice to find a rent division among n rooms such that, for every possible room selection of the secretive agent, there exists an allocation (of the remaining n-1 rooms among the n-1 agents) which ensures overall envy freeness (fairness). We complement this existential result by developing a polynomial-time algorithm that finds such a fair rent division under quasilinear utilities. In this partial information setting, we also develop efficient algorithms to compute allocations that are envy-free up to one good (EF1) and epsilon-approximate envy free. These two notions of fairness are applicable in the context of indivisible goods and divisible goods (cake cutting), respectively. This work also addresses fairness in terms of proportionality and maximin shares. Our key result here is an efficient algorithm that, even with a secretive agent, finds a 1/19-approximate maximin fair allocation (of indivisible goods) under submodular valuations of the non-secretive agents. One of the main technical contributions of this paper is the development of novel connections between different fair-division paradigms, e.g., we use our existential results for envy-free rent-division to develop an efficient EF1 algorithm.
AstroServ: Distributed Database for Serving Large-Scale Full Life-Cycle Astronomical Data
Venue: arXiv cs.DB 2018
Year: 2018

In time-domain astronomy, STLF (Short-Timescale and Large Field-of-view) sky survey is the latest way of sky observation. Compared to traditional sky survey who can only find astronomical phenomena, STLF sky survey can even reveal how short astronomical phenomena evolve. The difference does not only lead the new survey data but also the new analysis style. It requires that database behind STLF sky survey should support continuous analysis on data streaming, real-time analysis on short-term data and complex analysis on long-term historical data. In addition, both insertion and query latencies have strict requirements to ensure that scientific phenomena can be discovered. However, the existing databases cannot support our scenario. In this paper, we propose AstroServ, a distributed system for analysis and management of large-scale and full life-cycle astronomical data. AstroServ's core components include three data service layers and a query engine. Each data service layer serves for a specific time period of data and query engine can provide the uniform analysis interface on different data. In addition, we also provide many applications including interactive analysis interface and data mining tool to help scientists efficiently use data. The experimental results show that AstroServ can meet the strict performance requirements and the good recognition accuracy.
Are 2D-LSTM really dead for offline text recognition?
Venue: arXiv cs.CV 2018
Year: 2018

There is a recent trend in handwritten text recognition with deep neural networks to replace 2D recurrent layers with 1D, and in some cases even completely remove the recurrent layers, relying on simple feed-forward convolutional only architectures. The most used type of recurrent layer is the Long-Short Term Memory (LSTM). The motivations to do so are many: there are few open-source implementations of 2D-LSTM, even fewer supporting GPU implementations (currently cuDNN only implements 1D-LSTM); 2D recurrences reduce the amount of computations that can be parallelized, and thus possibly increase the training/inference time; recurrences create global dependencies with respect to the input, and sometimes this may not be desirable. Many recent competitions were won by systems that employed networks that use 2D-LSTM layers. Most previous work that compared 1D or pure feed-forward architectures to 2D recurrent models have done so on simple datasets or did not fully optimize the "baseline" 2D model compared to the challenger model, which was dully optimized. In this work, we aim at a fair comparison between 2D and competing models and also extensively evaluate them on more complex datasets that are more representative of challenging "real-world" data, compared to "academic" datasets that are more restricted in their complexity. We aim at determining when and why the 1D and 2D recurrent models have different results. We also compare the results with a language model to assess if linguistic constraints do level the performance of the different networks. Our results show that for challenging datasets, 2D-LSTM networks still seem to provide the highest performances and we propose a visualization strategy to explain it.
Large-scale analysis of user exposure to online advertising in Facebook
Venue: arXiv cs.SI 2018
Year: 2018

Online advertising is the major source of income for a large portion of Internet Services. There exists a body of literature aiming at optimizing ads engagement, understanding the privacy and ethical implications of online advertising, etc. However, to the best of our knowledge, no previous work analyses at large scale the exposure of real users to online advertising. This paper performs a comprehensive analysis of the exposure of users to ads and advertisers using a dataset including more than 7M ads from 140K unique advertisers delivered to more than 5K users that was collected between October 2016 and May 2018. The study focuses on Facebook, which is the second largest advertising platform only to Google in terms of revenue, and accounts for more than 2.2B monthly active users. Our analysis reveals that Facebook users are exposed (in median) to 70 ads per week, which come from 12 advertisers. Ads represent between 10% and 15% of all the information received in users' newsfeed. A small increment of 1% in the portion of ads in the newsfeed could roughly represent a revenue increase of 8.17M USD per week for Facebook. Finally, we also reveal that Facebook users are overprofiled since in the best case only 22.76% of the interests Facebook assigns to users for advertising purpose are actually related to the ads those users receive.
Adaptive Edge Process Migration for IoT in Heterogeneous Cloud-Fog-Edge Computing Environment
Venue: arXiv cs.DC 2018
Year: 2018

The latency issue of the cloud-centric IoT management system has motivated Fog and Edge Computing (FEC) architecture, which distributes the tasks from the cloud to the edge resources such as routers, switches or the IoT devices themselves. Specifically, mobile sensors of IoT system can also carry certain tasks for FEC. Considering the need of dynamic process migration from the mobile sensors to other resources when the mobile sensors unable to continue their tasks, the IoT system needs to provide a flexible mechanism that allows the mobile sensors dynamically migrate their tasks to the other FEC resource at runtime. However, it raises a question in what is the optimal approach when the mobile sensors intend to migrate their tasks to multiple heterogeneous FEC resource? In order to address the question, the authors propose REM scheme, which is capable of optimising the process migration decision. Further, in order to realise such a system and to validate the REM scheme, the authors have developed EPIoT host framework. Finally, the authors have implemented and have evaluated the REM scheme and framework, the results have shown that the REM scheme is capable of enhancing the performance of the process migration in heterogeneous FEC environment.
Modelling Agents Endowed with Social Practices: Static Aspects
Venue: arXiv cs.MA 2018
Year: 2018

To understand societal phenomena through simulation, we need computational variants of socio-cognitive theories. Social Practice Theory has provided a unique understanding of social phenomena regarding the routinized, social and interconnected aspects of behaviour. This paper provides the Social Practice Agent (SoPrA) model that enables the use of Social Practice Theory (SPT) for agent-based simulations. We extract requirements from SPT, construct a computational model in the Unified Modelling Language, verify its implementation in Netlogo and Protégé and show how SoPrA maps on a use case of commuting. The next step is to model the dynamic aspect of SPT and validate SoPrA's ability to provide understanding in different scenario's. This paper provides the groundwork with a computational model that is a correct depiction of SPT, computational feasible and can be directly mapped to the habitual, social and interconnected aspects of a target scenario.
Application of Clinical Concept Embeddings for Heart Failure Prediction in UK EHR data
Venue: arXiv cs.CL 2018
Year: 2018

Electronic health records (EHR) are increasingly being used for constructing disease risk prediction models. Feature engineering in EHR data however is challenging due to their highly dimensional and heterogeneous nature. Low-dimensional representations of EHR data can potentially mitigate these challenges. In this paper, we use global vectors (GloVe) to learn word embeddings for diagnoses and procedures recorded using 13 million ontology terms across 2.7 million hospitalisations in national UK EHR. We demonstrate the utility of these embeddings by evaluating their performance in identifying patients which are at higher risk of being hospitalised for congestive heart failure. Our findings indicate that embeddings can enable the creation of robust EHR-derived disease risk prediction models and address some the limitations associated with manual clinical feature engineering.
Understanding the Importance of Single Directions via Representative Substitution
Venue: arXiv cs.CV 2018
Year: 2018

Understanding the internal representations of deep neural networks (DNNs) is crucal to explain their behavior. The interpretation of individual units, which are neurons in MLPs or convolution kernels in convolutional networks, has been paid much attention given their fundamental role. However, recent research (Morcos et al. 2018) presented a counterintuitive phenomenon, which suggests that an individual unit with high class selectivity, called interpretable units, has poor contributions to generalization of DNNs. In this work, we provide a new perspective to understand this counterintuitive phenomenon, which makes sense when we introduce Representative Substitution (RS). Instead of individually selective units with classes, the RS refers to the independence of a unit's representations in the same layer without any annotation. Our experiments demonstrate that interpretable units have high RS which are not critical to network's generalization. The RS provides new insights into the interpretation of DNNs and suggests that we need to focus on the independence and relationship of the representations.
Integrating Topological Proofs with Model Checking to Instrument Iterative Design
Venue: arXiv cs.LO 2018
Year: 2018

System development is not a linear, one-shot process. It proceeds through refinements and revisions. To support assurance that the system satisfies its requirements, it is desirable that continuous verification can be performed after each refinement or revision step. To achieve practical adoption, formal system modeling and verification must accommodate continuous verification efficiently and effectively. Our proposal to address this problem is TOrPEDO, a verification approach where models are given via Partial Kripke Structures (PKSs) and requirements are specified as Linear-time Temporal Logic (LTL) properties. PKSs support refinement, by deliberately indicating unspecified parts of the model that are later completed. We support verification in two complementary forms: via model checking and proofs. Model checking is useful to provide counterexamples, i.e., pinpoint model behaviors that violate requirements. Proofs are instead useful since they can explain why requirements are satisfied. In our work, we introduce a specific concept of proof, called topological proof (TP). A TP produces a slice of the original PKS which justifies the property satisfaction. Because models can be incomplete, TOrPEDO supports reasoning on requirements satisfaction, violation, and possible satisfaction (in the case where the satisfaction depends on unknown parts).
MG-WFBP: Efficient Data Communication for Distributed Synchronous SGD Algorithms
Venue: arXiv cs.DC 2018
Year: 2018

Distributed synchronous stochastic gradient descent has been widely used to train deep neural networks on computer clusters. With the increase of computational power, network communications have become one limiting factor on system scalability. In this paper, we observe that many deep neural networks have a large number of layers with only a small amount of data to be communicated. Based on the fact that merging some short communication tasks into a single one may reduce the overall communication time, we formulate an optimization problem to minimize the training iteration time. We develop an optimal solution named merged-gradient WFBP (MG-WFBP) and implement it in our open-source deep learning platform B-Caffe. Our experimental results on an 8-node GPU cluster with 10GbE interconnect and trace-based simulation results on a 64-node cluster both show that the MG-WFBP algorithm can achieve much better scaling efficiency than existing methods WFBP and SyncEASGD.
Understanding and Improving Kernel Local Descriptors
Venue: arXiv cs.CV 2018
Year: 2018

We propose a multiple-kernel local-patch descriptor based on efficient match kernels from pixel gradients. It combines two parametrizations of gradient position and direction, each parametrization provides robustness to a different type of patch mis-registration: polar parametrization for noise in the patch dominant orientation detection, Cartesian for imprecise location of the feature point. Combined with whitening of the descriptor space, that is learned with or without supervision, the performance is significantly improved. We analyze the effect of the whitening on patch similarity and demonstrate its semantic meaning. Our unsupervised variant is the best performing descriptor constructed without the need of labeled data. Despite the simplicity of the proposed descriptor, it competes well with deep learning approaches on a number of different tasks.
Cross-Lingual Approaches to Reference Resolution in Dialogue Systems
Venue: arXiv cs.CL 2018
Year: 2018

In the slot-filling paradigm, where a user can refer back to slots in the context during the conversation, the goal of the contextual understanding system is to resolve the referring expressions to the appropriate slots in the context. In this paper, we build on the context carryover system~\citep{Naik2018ContextualSC}, which provides a scalable multi-domain framework for resolving references. However, scaling this approach across languages is not a trivial task, due to the large demand on acquisition of annotated data in the target language. Our main focus is on cross-lingual methods for reference resolution as a way to alleviate the need for annotated data in the target language. In the cross-lingual setup, we assume there is access to annotated resources as well as a well trained model in the source language and little to no annotated data in the target language. In this paper, we explore three different approaches for cross-lingual transfer \textemdash~\ delexicalization as data augmentation, multilingual embeddings and machine translation. We compare these approaches both on a low resource setting as well as a large resource setting. Our experiments show that multilingual embeddings and delexicalization via data augmentation have a significant impact in the low resource setting, but the gains diminish as the amount of available data in the target language increases. Furthermore, when combined with machine translation we can get performance very close to actual live data in the target language, with only 25\% of the data projected into the target language.
DLHub: Model and Data Serving for Science
Venue: arXiv cs.LG 2018
Year: 2018

While the Machine Learning (ML) landscape is evolving rapidly, there has been a relative lag in the development of the "learning systems" needed to enable broad adoption. Furthermore, few such systems are designed to support the specialized requirements of scientific ML. Here we present the Data and Learning Hub for science (DLHub), a multi-tenant system that provides both model repository and serving capabilities with a focus on science applications. DLHub addresses two significant shortcomings in current systems. First, its selfservice model repository allows users to share, publish, verify, reproduce, and reuse models, and addresses concerns related to model reproducibility by packaging and distributing models and all constituent components. Second, it implements scalable and low-latency serving capabilities that can leverage parallel and distributed computing resources to democratize access to published models through a simple web interface. Unlike other model serving frameworks, DLHub can store and serve any Python 3-compatible model or processing function, plus multiple-function pipelines. We show that relative to other model serving systems including TensorFlow Serving, SageMaker, and Clipper, DLHub provides greater capabilities, comparable performance without memoization and batching, and significantly better performance when the latter two techniques can be employed. We also describe early uses of DLHub for scientific applications.
A Compositional Textual Model for Recognition of Imperfect Word Images
Venue: arXiv cs.CV 2018
Year: 2018

Printed text recognition is an important problem for industrial OCR systems. Printed text is constructed in a standard procedural fashion in most settings. We develop a mathematical model for this process that can be applied to the backward inference problem of text recognition from an image. Through ablation experiments we show that this model is realistic and that a multi-task objective setting can help to stabilize estimation of its free parameters, enabling use of conventional deep learning methods. Furthermore, by directly modeling the geometric perturbations of text synthesis we show that our model can help recover missing characters from incomplete text regions, the bane of multicomponent OCR systems, enabling recognition even when the detection returns incomplete information.
eXclusive Autoencoder (XAE) for Nucleus Detection and Classification on Hematoxylin and Eosin (H&E) Stained Histopathological Images
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we introduced a novel feature extraction approach, named exclusive autoencoder (XAE), which is a supervised version of autoencoder (AE), able to largely improve the performance of nucleus detection and classification on hematoxylin and eosin (H&E) histopathological images. The proposed XAE can be used in any AE-based algorithm, as long as the data labels are also provided in the feature extraction phase. In the experiments, we evaluated the performance of an approach which is the combination of an XAE and a fully connected neural network (FCN) and compared with some AE-based methods. For a nucleus detection problem (considered as a nucleus/non-nucleus classification problem) on breast cancer H&E images, the F-score of the proposed XAE+FCN approach achieved 96.64% while the state-of-the-art was at 84.49%. For nucleus classification on colorectal cancer H&E images, with the annotations of four categories of epithelial, inflammatory, fibroblast and miscellaneous nuclei. The F-score of the proposed method reached 70.4%. We also proposed a lymphocyte segmentation method. In the step of lymphocyte detection, we have compared with cutting-edge technology and gained improved performance from 90% to 98.67%. We also proposed an algorithm for lymphocyte segmentation based on nucleus detection and classification. The obtained Dice coefficient achieved 88.31% while the cutting-edge approach was at 74%.
Improved upper bound on root number of linearized polynomials and its application to nonlinearity estimation of Boolean functions
Venue: arXiv cs.IT 2018
Year: 2018

To determine the dimension of null space of any given linearized polynomial is one of vital problems in finite field theory, with concern to design of modern symmetric cryptosystems. But, the known general theory for this task is much far from giving the exact dimension when applied to a specific linearized polynomial. The first contribution of this paper is to give a better general method to get more precise upper bound on the root number of any given linearized polynomial. We anticipate this result would be applied as a useful tool in many research branches of finite field and cryptography. Really we apply this result to get tighter estimations of the lower bounds on the second order nonlinearities of general cubic Boolean functions, which has been being an active research problem during the past decade, with many examples showing great improvements. Furthermore, this paper shows that by studying the distribution of radicals of derivatives of a given Boolean functions one can get a better lower bound of the second-order nonlinearity, through an example of the monomial Boolean function $g_μ=Tr(μx^{2^{2r}+2^r+1})$ over any finite field $\GF{n}$.
Using Computer Vision Techniques for Moving Poster Design
Venue: arXiv cs.HC 2018
Year: 2018

Graphic Design encompasses a wide range of activities from the design of traditional print media (e.g., books and posters) to site-specific (e.g., signage systems) and electronic media (e.g., interfaces). Its practice always explores the new possibilities of information and communication technologies. Therefore, interactivity and participation have become key features in the design process. Even in traditional print media, graphic designers are trying to enhance user experience and exploring new interaction models. Moving posters are an example of this. This type of posters combine the specific features of motion and print worlds in order to produce attractive forms of communication that explore and exploit the potential of digital screens. In our opinion, the next step towards the integration of moving posters with the surroundings, where they operate, is incorporating data from the environment, which also enables the seamless participation of the audience. As such, the adoption of computer vision techniques for moving poster design becomes a natural approach. Following this line of thought, we present a system wherein computer vision techniques are used to shape a moving poster. Although it is still a work in progress, the system is already able to sense the surrounding physical environment and translate the collected data into graphical information. The data is gathered from the environment in two ways: (1) directly using motion tracking; and (2) indirectly via contextual ambient data. In this sense, each user interaction with the system results in a different experience and in a unique poster design.