OpenRaiser/Intern-Atlas huggingface dataset:
Learning Discrete Structures for Graph Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Graph neural networks (GNNs) are a popular class of machine learning models whose major advantage is their ability to incorporate a sparse and discrete dependency structure between data points. Unfortunately, GNNs can only be used when such a graph-structure is available. In practice, however, real-world graphs are often noisy and incomplete or might not be available at all. With this work, we propose to jointly learn the graph structure and the parameters of graph convolutional networks (GCNs) by approximately solving a bilevel program that learns a discrete probability distribution on the edges of the graph. This allows one to apply GCNs not only in scenarios where the given graph is incomplete or corrupted but also in those where a graph is not available. We conduct a series of experiments that analyze the behavior of the proposed method and demonstrate that it outperforms related methods by a significant margin.
KloakDB: A Platform for Analyzing Sensitive Data with $K$-anonymous Query Processing
Venue: arXiv cs.DB 2020
Year: 2020

A private data federation enables data owners to pool their information for querying without disclosing their secret tuples to one another. Here, a client queries the union of the records of all data owners. The data owners work together to answer the query using privacy-preserving algorithms that prevent them from learning unauthorized information about the inputs of their peers. Only the client, and a federation coordinator, learn the query's output. KloakDB is a private data federation that uses trusted hardware to process SQL queries over the inputs of two or more parties. Currently private data federations compute their queries fully-obliviously, guaranteeing that no information is revealed about the sensitive inputs of a data owner to their peers by observing the query's instruction traces and memory access patterns. Oblivious querying almost always exacts multiple orders of magnitude slowdown in query runtimes compared to plaintext execution, making it impractical for many applications. KloakDB offers a semi-oblivious computing framework, $k$-anonymous query processing. We make the query's observable transcript $k$-anonymous because it is a popular standard for data release in many domains including medicine, educational research, and government data. KloakDB's queries run such that each data owner may deduce information about no fewer than $k$ individuals in the data of their peers. In addition, stakeholders set $k$, creating a novel trade-off between privacy and performance. Our results show that KloakDB enjoys speedups of up to $117$X using k-anonymous query processing over full-oblivious evaluation.
ResUNet-a: a deep learning framework for semantic segmentation of remotely sensed data
Venue: arXiv cs.CV 2020
Year: 2020

Scene understanding of high resolution aerial images is of great importance for the task of automated monitoring in various remote sensing applications. Due to the large within-class and small between-class variance in pixel values of objects of interest, this remains a challenging task. In recent years, deep convolutional neural networks have started being used in remote sensing applications and demonstrate state of the art performance for pixel level classification of objects. \textcolor{black}{Here we propose a reliable framework for performant results for the task of semantic segmentation of monotemporal very high resolution aerial images. Our framework consists of a novel deep learning architecture, ResUNet-a, and a novel loss function based on the Dice loss. ResUNet-a uses a UNet encoder/decoder backbone, in combination with residual connections, atrous convolutions, pyramid scene parsing pooling and multi-tasking inference. ResUNet-a infers sequentially the boundary of the objects, the distance transform of the segmentation mask, the segmentation mask and a colored reconstruction of the input. Each of the tasks is conditioned on the inference of the previous ones, thus establishing a conditioned relationship between the various tasks, as this is described through the architecture's computation graph. We analyse the performance of several flavours of the Generalized Dice loss for semantic segmentation, and we introduce a novel variant loss function for semantic segmentation of objects that has excellent convergence properties and behaves well even under the presence of highly imbalanced classes.} The performance of our modeling framework is evaluated on the ISPRS 2D Potsdam dataset. Results show state-of-the-art performance with an average F1 score of 92.9\% over all classes for our best model.
ISS Lyapunov Functions for Cascade Switched Systems and Sampled-Data Control
Venue: arXiv cs.SY 2020
Year: 2020

Input-to-state stability (ISS) of switched systems is studied where the individual subsystems are connected in a serial cascade configuration, and the states are allowed to reset at switching times. An ISS Lyapunov function is associated to each of the two blocks connected in cascade, and these functions are used as building blocks for constructing ISS Lyapunov function for the interconnected system. The derivative of individual Lyapunov functions may be bounded by nonlinear decay functions, and the growth in the value of Lyapunov function at switching times may also be a nonlinear function of the value of other Lyapunov functions. The stability of overall hybrid system is analyzed by constructing a newly constructed ISS-Lyapunov function and deriving lower bounds on the average dwell-time. The particular case of linear subsystems and quadratic Lyapunov functions is also studied. The tools are also used for studying the observer-based feedback stabilization of a nonlinear switched system with event-based sampling of the output and control inputs. We design dynamic sampling algorithms based on the proposed Lyapunov functions and analyze the stability of the resulting closed-loop system.
Dynamic Data Structures for Interval Coloring
Venue: arXiv cs.DS 2020
Year: 2020

We consider the dynamic graph coloring problem restricted to the class of interval graphs. At each update step the algorithm is presented with an interval to be colored, or a previously colored interval to delete. The goal of the algorithm is to efficiently maintain a proper coloring of the intervals with as few colors as possible by an online algorithm. In the incremental model, each update step presents the algorithm with an interval to be colored. The problem is closely connected to the online vertex coloring problem of interval graphs for which the Kierstead-Trotter (KT) algorithm achieves the best possible competitive ratio. We first show that a sub-quadratic time direct implementation of the KT-algorithm is unlikely to exist conditioned on the correctness of the Online Boolean Matrix Vector multiplication conjecture due to Henzinger et al. \cite{DBLP:conf/stoc/HenzingerKNS15}. We then design an incremental algorithm that is subtly different from the KT-algorithm and uses at most $3 ω- 2$ colors, where $ω$ is the maximum clique in the interval graph associated with the set of intervals. Our incremental data structure maintains a proper coloring in amortized $O(\log n + Δ)$ update time where $n$ is the total number of intervals inserted and $Δ$ is the maximum degree of a vertex in the interval graph. We then consider the fully dynamic framework involving insertions and deletions. On each update, our aim is to maintain a $3 ω- 2$ coloring of the remaining set of intervals, where $ω$ is the maximum clique in the interval graph associated with the remaining set of intervals. Our fully dynamic algorithm supports insertion of an interval in $O(\log n + Δ\log ω)$ worst case update time and deletion of an interval in $O(Δ^2 \log n)$ worst case update time.
Categories with Families: Unityped, Simply Typed, and Dependently Typed
Venue: arXiv cs.LO 2020
Year: 2020

We show how the categorical logic of untyped, simply typed and dependently typed lambda calculus can be structured around the notion of category with family (cwf). To this end we introduce subcategories of simply typed cwfs (scwfs), where types do not depend on variables, and unityped cwfs (ucwfs), where there is only one type. We prove several equivalence and biequivalence theorems between cwf-based notions and basic notions of categorical logic, such as cartesian operads, Lawvere theories, categories with finite products and limits, cartesian closed categories, and locally cartesian closed categories. Some of these theorems depend on the restrictions of contextuality (in the sense of Cartmell) or democracy (used by Clairambault and Dybjer for their biequivalence theorems). Some theorems are equivalences between notions with strict preservation of chosen structure. Others are biequivalences between notions where properties are only preserved up to isomorphism. In addition to this we discuss various constructions of initial ucwfs, scwfs, and cwfs with extra structure.
Centerline Depth World Reinforcement Learning-based Left Atrial Appendage Orifice Localization
Venue: arXiv cs.CV 2020
Year: 2020

Left atrial appendage (LAA) closure (LAAC) is a minimally invasive implant-based method to prevent cardiovascular stroke in patients with non-valvular atrial fibrillation. Assessing the LAA orifice in preoperative CT angiography plays a crucial role in choosing an appropriate LAAC implant size and a proper C-arm angulation. However, accurate orifice localization is hard because of the high anatomic variation of LAA, and unclear position and orientation of the orifice in available CT views. Deep localization models also yield high error in localizing the orifice in CT image because of the tiny structure of orifice compared to the vastness of CT image. In this paper, we propose a centerline depth-based reinforcement learning (RL) world for effective orifice localization in a small search space. In our scheme, an RL agent observes the centerline-to-surface distance and navigates through the LAA centerline to localize the orifice. Thus, the search space is significantly reduced facilitating improved localization. The proposed formulation could result in high localization accuracy comparing to the expert-annotations in 98 CT images. Moreover, the localization process takes about 8 seconds which is 18 times more efficient than the existing method. Therefore, this can be a useful aid to physicians during the preprocedural planning of LAAC.
Fundamentals of computability logic 2020
Venue: arXiv cs.LO 2020
Year: 2020

This article is a semitutorial-style survey of computability logic. An extended online version of it is maintained at http://www.csc.villanova.edu/~japaridz/CL/ .
Lautum Regularization for Semi-supervised Transfer Learning
Venue: arXiv cs.LG 2020
Year: 2020

Transfer learning is a very important tool in deep learning as it allows propagating information from one "source dataset" to another "target dataset", especially in the case of a small number of training examples in the latter. Yet, discrepancies between the underlying distributions of the source and target data are commonplace and are known to have a substantial impact on algorithm performance. In this work we suggest a novel information theoretic approach for the analysis of the performance of deep neural networks in the context of transfer learning. We focus on the task of semi-supervised transfer learning, in which unlabeled samples from the target dataset are available during the network training on the source dataset. Our theory suggests that one may improve the transferability of a deep neural network by imposing a Lautum information based regularization that relates the network weights to the target data. We demonstrate the effectiveness of the proposed approach in various transfer learning experiments.
Impact of ASR on Alzheimer's Disease Detection: All Errors are Equal, but Deletions are More Equal than Others
Venue: arXiv cs.CL 2020
Year: 2020

Automatic Speech Recognition (ASR) is a critical component of any fully-automated speech-based dementia detection model. However, despite years of speech recognition research, little is known about the impact of ASR accuracy on dementia detection. In this paper, we experiment with controlled amounts of artificially generated ASR errors and investigate their influence on dementia detection. We find that deletion errors affect detection performance the most, due to their impact on the features of syntactic complexity and discourse representation in speech. We show the trend to be generalisable across two different datasets for cognitive impairment detection. As a conclusion, we propose optimising the ASR to reflect a higher penalty for deletion errors in order to improve dementia detection performance.
M2KD: Multi-model and Multi-level Knowledge Distillation for Incremental Learning
Venue: arXiv cs.CV 2020
Year: 2020

Incremental learning targets at achieving good performance on new categories without forgetting old ones. Knowledge distillation has been shown critical in preserving the performance on old classes. Conventional methods, however, sequentially distill knowledge only from the last model, leading to performance degradation on the old classes in later incremental learning steps. In this paper, we propose a multi-model and multi-level knowledge distillation strategy. Instead of sequentially distilling knowledge only from the last model, we directly leverage all previous model snapshots. In addition, we incorporate an auxiliary distillation to further preserve knowledge encoded at the intermediate feature levels. To make the model more memory efficient, we adapt mask based pruning to reconstruct all previous models with a small memory footprint. Experiments on standard incremental learning benchmarks show that our method preserves the knowledge on old classes better and improves the overall performance over standard distillation techniques.
Tunable Eigenvector-Based Centralities for Multiplex and Temporal Networks
Venue: arXiv cs.SI 2020
Year: 2020

Characterizing the importances (i.e., centralities) of nodes in social, biological, and technological networks is a core topic in both network science and data science. We present a linear-algebraic framework that generalizes eigenvector-based centralities, including PageRank and hub/authority scores, to provide a common framework for two popular classes of multilayer networks: multiplex networks (which have layers that encode different types of relationships) and temporal networks (in which the relationships change over time). Our approach involves the study of joint, marginal, and conditional "supracentralities" that one can calculate from the dominant eigenvector of a supracentrality matrix [Taylor et al., 2017], which couples centrality matrices that are associated with individual network layers. We extend this prior work (which was restricted to temporal networks with layers that are coupled by adjacent-in-time coupling) by allowing the layers to be coupled through a (possibly asymmetric) interlayer-adjacency matrix $\tilde{\bf A}$, where the entry $\tilde{A}_{tt'} \geq 0$ encodes the coupling between layers $t$ and $t'$. Our framework provides a unifying foundation for centrality analysis of multiplex and temporal networks; it also illustrates a complicated dependency of the supracentralities on the topology and weights of interlayer coupling. By scaling $\tilde{\bf A}$ by an interlayer-coupling strength $ω\ge0$ and developing a singular perturbation theory for the limits of weak ($ω\to0^+$) and strong coupling ($ω\to\infty$), we also reveal an interesting dependence of supracentralities on the dominant left and right eigenvectors of $\tilde{\bf A}$.
Target-Tailored Source-Transformation for Scene Graph Generation
Venue: arXiv cs.CV 2020
Year: 2020

Scene graph generation aims to provide a semantic and structural description of an image, denoting the objects (with nodes) and their relationships (with edges). The best performing works to date are based on exploiting the context surrounding objects or relations,e.g., by passing information among objects. In these approaches, to transform the representation of source objects is a critical process for extracting information for the use by target objects. In this work, we argue that a source object should give what tar-get object needs and give different objects different information rather than contributing common information to all targets. To achieve this goal, we propose a Target-TailoredSource-Transformation (TTST) method to efficiently propagate information among object proposals and relations. Particularly, for a source object proposal which will contribute information to other target objects, we transform the source object feature to the target object feature domain by simultaneously taking both the source and target into account. We further explore more powerful representations by integrating language prior with the visual context in the transformation for the scene graph generation. By doing so the target object is able to extract target-specific information from the source object and source relation accordingly to refine its representation. Our framework is validated on the Visual Genome bench-mark and demonstrated its state-of-the-art performance for the scene graph generation. The experimental results show that the performance of object detection and visual relation-ship detection are promoted mutually by our method.
CAN-NER: Convolutional Attention Network for Chinese Named Entity Recognition
Venue: arXiv cs.CL 2020
Year: 2020

Named entity recognition (NER) in Chinese is essential but difficult because of the lack of natural delimiters. Therefore, Chinese Word Segmentation (CWS) is usually considered as the first step for Chinese NER. However, models based on word-level embeddings and lexicon features often suffer from segmentation errors and out-of-vocabulary (OOV) words. In this paper, we investigate a Convolutional Attention Network called CAN for Chinese NER, which consists of a character-based convolutional neural network (CNN) with local-attention layer and a gated recurrent unit (GRU) with global self-attention layer to capture the information from adjacent characters and sentence contexts. Also, compared to other models, not depending on any external resources like lexicons and employing small size of char embeddings make our model more practical. Extensive experimental results show that our approach outperforms state-of-the-art methods without word embedding and external lexicon resources on different domain datasets including Weibo, MSRA and Chinese Resume NER dataset.
Template-Based Automatic Search of Compact Semantic Segmentation Architectures
Venue: arXiv cs.CV 2020
Year: 2020

Automatic search of neural architectures for various vision and natural language tasks is becoming a prominent tool as it allows to discover high-performing structures on any dataset of interest. Nevertheless, on more difficult domains, such as dense per-pixel classification, current automatic approaches are limited in their scope - due to their strong reliance on existing image classifiers they tend to search only for a handful of additional layers with discovered architectures still containing a large number of parameters. In contrast, in this work we propose a novel solution able to find light-weight and accurate segmentation architectures starting from only few blocks of a pre-trained classification network. To this end, we progressively build up a methodology that relies on templates of sets of operations, predicts which template and how many times should be applied at each step, while also generating the connectivity structure and downsampling factors. All these decisions are being made by a recurrent neural network that is rewarded based on the score of the emitted architecture on the holdout set and trained using reinforcement learning. One discovered architecture achieves 63.2% mean IoU on CamVid and 67.8% on CityScapes having only 270K parameters. Pre-trained models and the search code are available at https://github.com/DrSleep/nas-segm-pytorch.
Shape Sensing of Variable Stiffness Soft Robots using Electrical Impedance Tomography
Venue: arXiv cs.RO 2020
Year: 2020

Soft robotic systems offer benefits over traditional rigid systems through reduced contact trauma with soft tissues and by enabling access through tortuous paths in minimally invasive surgery. However, the inherent deformability of soft robots places both a greater onus on accurate modelling of their shape, and greater challenges in realising intraoperative shape sensing. Herein we present a proprioceptive (self-sensing) soft actuator, with an electrically conductive working fluid. Electrical impedance measurements from up to six electrodes enabled tomographic reconstructions using Electrical Impedance Tomography (EIT). A new Frequency Division Multiplexed (FDM) EIT system was developed capable of measurements of 66 dB SNR with 20 ms temporal resolution. The concept was examined in two two-degree-of-freedom designs: a hydraulic hinged actuator and a pneumatic finger actuator with hydraulic beams. Both cases demonstrated that impedance measurements could be used to infer shape changes, and EIT images reconstructed during actuation showed distinct patterns with respect to each degree of freedom (DOF). Whilst there was some mechanical hysteresis observed, the repeatability of the measurements and resultant images was high. The results show the potential of FDM-EIT as a low-cost, low profile shape sensor in soft robots.
An Equivariant Observer Design for Visual Localisation and Mapping
Venue: arXiv cs.RO 2020
Year: 2020

This paper builds on recent work on Simultaneous Localisation and Mapping (SLAM) in the non-linear observer community, by framing the visual localisation and mapping problem as a continuous-time equivariant observer design problem on the symmetry group of a kinematic system. The state-space is a quotient of the robot pose expressed on SE(3) and multiple copies of real projective space, used to represent both points in space and bearings in a single unified framework. An observer with decoupled Riccati-gains for each landmark is derived and we show that its error system is almost globally asymptotically stable and exponentially stable in-the-large.
Overlap matrix concentration in optimal Bayesian inference
Venue: arXiv cs.IT 2020
Year: 2020

We consider models of Bayesian inference of signals with vectorial components of finite dimensionality. We show that, under a proper perturbation, these models are replica symmetric in the sense that the overlap matrix concentrates. The overlap matrix is the order parameter in these models and is directly related to error metrics such as minimum mean-square errors. Our proof is valid in the optimal Bayesian inference setting. This means that it relies on the assumption that the model and all its hyper-parameters are known so that the posterior distribution can be written exactly. Examples of important problems in high-dimensional inference and learning to which our results apply are low-rank tensor factorization, the committee machine neural network with a finite number of hidden neurons in the teacher-student scenario, or multi-layer versions of the generalized linear model.