OpenRaiser/Intern-Atlas huggingface dataset:
Collective Schedules: Scheduling Meets Computational Social Choice
Venue: arXiv cs.GT 2018
Year: 2018

When scheduling public works or events in a shared facility one needs to accommodate preferences of a population. We formalize this problem by introducing the notion of a collective schedule. We show how to extend fundamental tools from social choice theory---positional scoring rules, the Kemeny rule and the Condorcet principle---to collective scheduling. We study the computational complexity of finding collective schedules. We also experimentally demonstrate that optimal collective schedules can be found for instances with realistic sizes.
The Crossing Number of Seq-Shellable Drawings of Complete Graphs
Venue: arXiv cs.CG 2018
Year: 2018

The Harary-Hill conjecture states that for every $n>0$ the complete graph on $n$ vertices $K_n$, the minimum number of crossings over all its possible drawings equals \begin{align*} H(n) := \frac{1}{4}\Big\lfloor\frac{n}{2}\Big\rfloor\Big\lfloor\frac{n-1}{2}\Big\rfloor\Big\lfloor\frac{n-2}{2}\Big\rfloor\Big\lfloor\frac{n-3}{2}\Big\rfloor\text{.} \end{align*} So far, the lower bound of the conjecture could only be verified for arbitrary drawings of $K_n$ with $n\leq 12$. In recent years, progress has been made in verifying the conjecture for certain classes of drawings, for example $2$-page-book, $x$-monotone, $x$-bounded, shellable and bishellable drawings. Up to now, the class of bishellable drawings was the broadest class for which the Harary-Hill conjecture has been verified, as it contains all beforehand mentioned classes. In this work, we introduce the class of seq-shellable drawings and verify the Harary-Hill conjecture for this new class. We show that bishellability implies seq-shellability and exhibit a non-bishellable but seq-shellable drawing of $K_{11}$, therefore the class of seq-shellable drawings strictly contains the class of bishellable drawings.
Stacked Neural Networks for end-to-end ciliary motion analysis
Venue: arXiv cs.LG 2018
Year: 2018

Cilia are hairlike structures protruding from nearly every cell in the body. Diseases known as ciliopathies, where cilia function is disrupted, can result in a wide spectrum of disorders. However, most techniques for assessing ciliary motion rely on manual identification and tracking of cilia; this process is laborious and error-prone, and does not scale well. Even where automated ciliary motion analysis tools exist, their applicability is limited. Here, we propose an end-to-end computational machine learning pipeline that automatically identifies regions of cilia from videos, extracts patches of cilia, and classifies patients as exhibiting normal or abnormal ciliary motion. In particular, we demonstrate how convolutional LSTM are able to encode complex features while remaining sensitive enough to differentiate between a variety of motion patterns. Our framework achieves 90% with only a few hundred training epochs. We find that the combination of segmentation and classification networks in a single pipeline yields performance comparable to existing computational pipelines, while providing the additional benefit of an end-to-end, fully-automated analysis toolbox for ciliary motion.
Enslaving the Algorithm: From a "Right to an Explanation" to a "Right to Better Decisions"?
Venue: arXiv cs.AI 2018
Year: 2018

As concerns about unfairness and discrimination in "black box" machine learning systems rise, a legal "right to an explanation" has emerged as a compellingly attractive approach for challenge and redress. We outline recent debates on the limited provisions in European data protection law, and introduce and analyze newer explanation rights in French administrative law and the draft modernized Council of Europe Convention 108. While individual rights can be useful, in privacy law they have historically unreasonably burdened the average data subject. "Meaningful information" about algorithmic logics is more technically possible than commonly thought, but this exacerbates a new "transparency fallacy"---an illusion of remedy rather than anything substantively helpful. While rights-based approaches deserve a firm place in the toolbox, other forms of governance, such as impact assessments, "soft law," judicial review, and model repositories deserve more attention, alongside catalyzing agencies acting for users to control algorithmic system design.
Exploring the use of time-varying graphs for modelling transit networks
Venue: arXiv cs.SI 2018
Year: 2018

The study of the dynamic relationship between topological structure of a transit network and the mobility patterns of transit vehicles on this network is critical towardsdevising smart and time-aware solutions to transit management and recommendation systems. This paper proposes a time-varying graph (TVG) to model thisrelationship. The effectiveness of this proposed model has been explored by implementing the model in Neo4j graph database using transit feeds generated by bus transit network of the City of Moncton, New Brunswick, Canada. Dynamics in this relationshipalsohave been detected using network metrics such as temporal shortest paths, degree, betweenness and PageRank centralities as well as temporal network diameter and density. Keywords: Transit Networks,Mobility Pattern,Time-Varying Graph model, Graph Databaseand Graph Analytics Keywords: Transit Networks,Mobility Pattern,Time-Varying Graph model, Graph Database and Graph Analytics
Online Learning: Sufficient Statistics and the Burkholder Method
Venue: arXiv cs.LG 2018
Year: 2018

We uncover a fairly general principle in online learning: If regret can be (approximately) expressed as a function of certain "sufficient statistics" for the data sequence, then there exists a special Burkholder function that 1) can be used algorithmically to achieve the regret bound and 2) only depends on these sufficient statistics, not the entire data sequence, so that the online strategy is only required to keep the sufficient statistics in memory. This characterization is achieved by bringing the full power of the Burkholder Method --- originally developed for certifying probabilistic martingale inequalities --- to bear on the online learning setting. To demonstrate the scope and effectiveness of the Burkholder method, we develop a novel online strategy for matrix prediction that attains a regret bound corresponding to the variance term in matrix concentration inequalities. We also present a linear-time/space prediction strategy for parameter free supervised learning with linear classes and general smooth norms.
An ADMM-based Coordination and Control Strategy for PV and Storage to Dispatch Stochastic Prosumers: Theory and Experimental Validation
Venue: arXiv cs.SY 2018
Year: 2018

This paper describes a two-layer control and coordination framework for distributed energy resources. The lower layer is a real-time model predictive control (MPC) executed at 10 s resolution to achieve fine tuning of a given energy set-point. The upper layer is a slower MPC coordination mechanism based on distributed optimization, and solved with the alternating direction method of multipliers (ADMM) at 5 minutes resolution. It is needed to coordinate the power flow among the controllable resources such that enough power is available in real-time to achieve a pre-established energy trajectory in the long term. Although the formulation is generic, it is developed for the case of a battery system and a curtailable PV facility to dispatch stochastic prosumption according to a trajectory at 5 minutes resolution established the day before the operation. The proposed method is experimentally validated in a real-life setup to dispatch the operation of a building with rooftop PV generation (i.e., 101 kW average load, 350 kW peak demand, 82 kW peak PV generation) by controlling a 560 kWh/720 kVA battery and a 13 kW peak curtailable PV facility.
Adaptive Super-twisting Second-order Sliding Mode for Attitude Control of Quadcopter UAVs
Venue: arXiv cs.SY 2018
Year: 2018

This work addresses the modelling and control aspects for quadcopter or drone unmanned aerial vehicles (UAVs). First, the mathematical model of the drone is derived by identifying significant parameters and the negligible ones are treated as disturbances. The control design begins with the switching surface selection, then, an Adaptive Super Twisting Sliding Mode (ASTSM) Control algorithm is applied to adjust attitudes of the quadcopter under harsh conditions such as nonlinear, strong coupling, high uncertainties and disturbances. Simulation results show that the proposed controller can achieve robust operation with disturbance rejection, parametric variation adaptation as well as chattering attenuation. Comparisons with some commonly used and advanced controllers in a quadcopter model show advantages of the proposed control scheme.
Multi-view Metric Learning in Vector-valued Kernel Spaces
Venue: arXiv cs.LG 2018
Year: 2018

We consider the problem of metric learning for multi-view data and present a novel method for learning within-view as well as between-view metrics in vector-valued kernel spaces, as a way to capture multi-modal structure of the data. We formulate two convex optimization problems to jointly learn the metric and the classifier or regressor in kernel feature spaces. An iterative three-step multi-view metric learning algorithm is derived from the optimization problems. In order to scale the computation to large training sets, a block-wise Nystr{ö}m approximation of the multi-view kernel matrix is introduced. We justify our approach theoretically and experimentally, and show its performance on real-world datasets against relevant state-of-the-art methods.
On-demand Relational Concept Analysis
Venue: arXiv cs.DB 2018
Year: 2018

Formal Concept Analysis and its associated conceptual structures have been used to support exploratory search through conceptual navigation. Relational Concept Analysis (RCA) is an extension of Formal Concept Analysis to process relational datasets. RCA and its multiple interconnected structures represent good candidates to support exploratory search in relational datasets, as they are enabling navigation within a structure as well as between the connected structures. However, building the entire structures does not present an efficient solution to explore a small localised area of the dataset, for instance to retrieve the closest alternatives to a given query. In these cases, generating only a concept and its neighbour concepts at each navigation step appears as a less costly alternative. In this paper, we propose an algorithm to compute a concept and its neighbourhood in extended concept lattices. The concepts are generated directly from the relational context family, and possess both formal and relational attributes. The algorithm takes into account two RCA scaling operators. We illustrate it on an example.
Quantification of Lung Abnormalities in Cystic Fibrosis using Deep Networks
Venue: arXiv cs.CV 2018
Year: 2018

Cystic fibrosis is a genetic disease which may appear in early life with structural abnormalities in lung tissues. We propose to detect these abnormalities using a texture classification approach. Our method is a cascade of two convolutional neural networks. The first network detects the presence of abnormal tissues. The second network identifies the type of the structural abnormalities: bronchiectasis, atelectasis or mucus plugging.We also propose a network computing pixel-wise heatmaps of abnormality presence learning only from the patch-wise annotations. Our database consists of CT scans of 194 subjects. We use 154 subjects to train our algorithms and the 40 remaining ones as a test set. We compare our method with random forest and a single neural network approach. The first network reaches an accuracy of 0,94 for disease detection, 0,18 higher than the random forest classifier and 0,37 higher than the single neural network. Our cascade approach yields a final class-averaged F1-score of 0,33, outperforming the baseline method and the single network by 0,10 and 0,12.
Olive Oil is Made of Olives, Baby Oil is Made for Babies: Interpreting Noun Compounds using Paraphrases in a Neural Model
Venue: arXiv cs.CL 2018
Year: 2018

Automatic interpretation of the relation between the constituents of a noun compound, e.g. olive oil (source) and baby oil (purpose) is an important task for many NLP applications. Recent approaches are typically based on either noun-compound representations or paraphrases. While the former has initially shown promising results, recent work suggests that the success stems from memorizing single prototypical words for each relation. We explore a neural paraphrasing approach that demonstrates superior performance when such memorization is not possible.
Extended depth-of-field in holographic image reconstruction using deep learning based auto-focusing and phase-recovery
Venue: arXiv cs.CV 2018
Year: 2018

Holography encodes the three dimensional (3D) information of a sample in the form of an intensity-only recording. However, to decode the original sample image from its hologram(s), auto-focusing and phase-recovery are needed, which are in general cumbersome and time-consuming to digitally perform. Here we demonstrate a convolutional neural network (CNN) based approach that simultaneously performs auto-focusing and phase-recovery to significantly extend the depth-of-field (DOF) in holographic image reconstruction. For this, a CNN is trained by using pairs of randomly de-focused back-propagated holograms and their corresponding in-focus phase-recovered images. After this training phase, the CNN takes a single back-propagated hologram of a 3D sample as input to rapidly achieve phase-recovery and reconstruct an in focus image of the sample over a significantly extended DOF. This deep learning based DOF extension method is non-iterative, and significantly improves the algorithm time-complexity of holographic image reconstruction from O(nm) to O(1), where n refers to the number of individual object points or particles within the sample volume, and m represents the focusing search space within which each object point or particle needs to be individually focused. These results highlight some of the unique opportunities created by data-enabled statistical image reconstruction methods powered by machine learning, and we believe that the presented approach can be broadly applicable to computationally extend the DOF of other imaging modalities.
A Theorem for Secrecy in Tagged Protocols Using the Theory of Witness-Functions
Venue: arXiv cs.CR 2018
Year: 2018

In this paper, we enunciate the theorem of secrecy in tagged protocols using the theory of witness-functions and we run a formal analysis on a new tagged version of the Needham-Schroeder public-key protocol using this theorem. We discuss the significance of tagging in securing cryptographic protocols as well.
Globally Stable Output Feedback Synchronization of Teleoperation with Time-Varying Delays
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents a globally stable teleoperation control strategy for systems with time-varying delays that eliminates the need for velocity measurements through novel augmented Immersion and Invariance velocity observers. The new observers simplify a recent constructive Immersion and Invariance velocity observer to achieve globally convergent velocity estimation with only $n+2$ states, where $n$ is the number of degrees of freedom of the master and slave robots. They introduce dynamic scaling factors to accelerate the speed of convergence of the velocity estimates and, thus, to limit the energy generated by the velocity estimation errors and to guarantee sufficient estimate-based damping injection to dissipate the energy generated by the time-varying delays. The paper shows that Proportional plus damping control with the simplified and augmented Immersion and Invariance-based velocity observers can synchronize the free master and slave motions in the presence of time-varying delays without using velocity measurements. Numerical results illustrate the estimation performance of the new observers and the stability of a simulated two degrees-of-freedom nonlinear teleoperation system with time-varying delays under the proposed output feedback Proportional plus damping control.
The Epistemology of Nondeterminism
Venue: arXiv cs.LO 2018
Year: 2018

This paper proposes new semantics for nondeterministic program execution, replacing the standard relational semantics for propositional dynamic logic (PDL). Under these new semantics, program execution is represented as fundamentally deterministic (i.e., functional), while nondeterminism emerges as an epistemic relationship between the agent and the system: intuitively, the nondeterministic outcomes of a given process are precisely those that cannot be ruled out in advance. We formalize these notions using topology and the framework of dynamic topological logic (DTL). We show that DTL can be used to interpret the language of PDL in a manner that captures the intuition above, and moreover that continuous functions in this setting correspond exactly to deterministic processes. We also prove that certain axiomatizations of PDL remain sound and complete with respect to the corresponding classes of dynamic topological models. Finally, we extend the framework to incorporate knowledge using the machinery of subset space logic, and show that the topological interpretation of public announcements coincides exactly with a natural interpretation of test programs.
Single-Shot Bidirectional Pyramid Networks for High-Quality Object Detection
Venue: arXiv cs.CV 2018
Year: 2018

Recent years have witnessed many exciting achievements for object detection using deep learning techniques. Despite achieving significant progresses, most existing detectors are designed to detect objects with relatively low-quality prediction of locations, i.e., often trained with the threshold of Intersection over Union (IoU) set to 0.5 by default, which can yield low-quality or even noisy detections. It remains an open challenge for how to devise and train a high-quality detector that can achieve more precise localization (i.e., IoU$>$0.5) without sacrificing the detection performance. In this paper, we propose a novel single-shot detection framework of Bidirectional Pyramid Networks (BPN) towards high-quality object detection, which consists of two novel components: (i) a Bidirectional Feature Pyramid structure for more effective and robust feature representations; and (ii) a Cascade Anchor Refinement to gradually refine the quality of predesigned anchors for more effective training. Our experiments showed that the proposed BPN achieves the best performances among all the single-stage object detectors on both PASCAL VOC and MS COCO datasets, especially for high-quality detections.
A Smoke Removal Method for Laparoscopic Images
Venue: arXiv cs.CV 2018
Year: 2018

In laparoscopic surgery, image quality can be severely degraded by surgical smoke, which not only introduces error for the image processing (used in image guided surgery), but also reduces the visibility of the surgeons. In this paper, we propose to enhance the laparoscopic images by decomposing them into unwanted smoke part and enhanced part using a variational approach. The proposed method relies on the observation that smoke has low contrast and low inter-channel differences. A cost function is defined based on this prior knowledge and is solved using an augmented Lagrangian method. The obtained unwanted smoke component is then subtracted from the original degraded image, resulting in the enhanced image. The obtained quantitative scores in terms of FADE, JNBM and RE metrics show that our proposed method performs rather well. Furthermore, the qualitative visual inspection of the results show that it removes smoke effectively from the laparoscopic images.
The Rapidly Changing Landscape of Conversational Agents
Venue: arXiv cs.AI 2018
Year: 2018

Conversational agents have become ubiquitous, ranging from goal-oriented systems for helping with reservations to chit-chat models found in modern virtual assistants. In this survey paper, we explore this fascinating field. We look at some of the pioneering work that defined the field and gradually move to the current state-of-the-art models. We look at statistical, neural, generative adversarial network based and reinforcement learning based approaches and how they evolved. Along the way we discuss various challenges that the field faces, lack of context in utterances, not having a good quantitative metric to compare models, lack of trust in agents because they do not have a consistent persona etc. We structure this paper in a way that answers these pertinent questions and discusses competing approaches to solve them.
Clustering-driven Deep Embedding with Pairwise Constraints
Venue: arXiv cs.CV 2018
Year: 2018

Recently, there has been increasing interest to leverage the competence of neural networks to analyze data. In particular, new clustering methods that employ deep embeddings have been presented. In this paper, we depart from centroid-based models and suggest a new framework, called Clustering-driven deep embedding with PAirwise Constraints (CPAC), for non-parametric clustering using a neural network. We present a clustering-driven embedding based on a Siamese network that encourages pairs of data points to output similar representations in the latent space. Our pair-based model allows augmenting the information with labeled pairs to constitute a semi-supervised framework. Our approach is based on analyzing the losses associated with each pair to refine the set of constraints. We show that clustering performance increases when using this scheme, even with a limited amount of user queries. We demonstrate how our architecture is adapted for various types of data and present the first deep framework to cluster 3D shapes.
Aligning Across Large Gaps in Time
Venue: arXiv cs.CV 2018
Year: 2018

We present a method of temporally-invariant image registration for outdoor scenes, with invariance across time of day, across seasonal variations, and across decade-long periods, for low- and high-texture scenes. Our method can be useful for applications in remote sensing, GPS-denied UAV localization, 3D reconstruction, and many others. Our method leverages a recently proposed approach to image registration, where fully-convolutional neural networks are used to create feature maps which can be registered using the Inverse-Composition Lucas-Kanade algorithm (ICLK). We show that invariance that is learned from satellite imagery can be transferable to time-lapse data captured by webcams mounted on buildings near ground-level.
iBrownout: An Integrated Approach for Managing Energy and Brownout in Container-based Clouds
Venue: arXiv cs.DC 2018
Year: 2018

Energy consumption of Cloud data centers has been a major concern of many researchers, and one of the reasons for huge energy consumption of Clouds lies in the inefficient utilization of computing resources. Besides energy consumption, another challenge of data centers is the unexpected loads, which leads to the overloads and performance degradation. Compared with VM consolidation and Dynamic Voltage Frequency Scaling that cannot function well when the whole data center is overloaded, brownout has shown to be a promising technique to handle both overloads and energy consumption through dynamically deactivating application optional components, which are also identified as containers/microservices. In this work, we propose an integrated approach to manage energy consumption and brownout in container-based cloud data centers. \color{black} We also evaluate our proposed scheduling policies with real traces in a prototype system. The results show that our approach reduces about 40%, 20% and 10% energy than the approach without power-saving techniques, brownout-overbooking approach and auto-scaling approach respectively while ensuring Quality of Service.