OpenRaiser/Intern-Atlas huggingface dataset:
Automated Verification of Neural Networks: Advances, Challenges and Perspectives
Venue: arXiv cs.AI 2018
Year: 2018

Neural networks are one of the most investigated and widely used techniques in Machine Learning. In spite of their success, they still find limited application in safety- and security-related contexts, wherein assurance about networks' performances must be provided. In the recent past, automated reasoning techniques have been proposed by several researchers to close the gap between neural networks and applications requiring formal guarantees about their behavior. In this work, we propose a primer of such techniques and a comprehensive categorization of existing approaches for the automated verification of neural networks. A discussion about current limitations and directions for future investigation is provided to foster research on this topic at the crossroads of Machine Learning and Automated Reasoning.
Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary
Venue: arXiv cs.DS 2018
Year: 2018

We study the classical Node-Disjoint Paths (NDP) problem: given an undirected $n$-vertex graph G, together with a set {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called source-destination, or demand pairs, find a maximum-cardinality set of mutually node-disjoint paths that connect the demand pairs. The best current approximation for the problem is achieved by a simple greedy $O(\sqrt{n})$-approximation algorithm. A special case of the problem called NDP-Grid, where the underlying graph is a grid, has been studied extensively. The best current approximation algorithm for NDP-Grid achieves an $\tilde{O}(n^{1/4})$-approximation factor. On the negative side, a recent result by the authors shows that NDP is hard to approximate to within factor $2^{Ω(\sqrt{\log n})}$, even if the underlying graph is a sub-graph of a grid, and all source vertices lie on the grid boundary. In a follow-up work, the authors further show that NDP-Grid is hard to approximate to within factor $Ω(2^{\log^{1-ε}n})$ for any constant $ε$ under standard complexity assumptions, and to within factor $n^{Ω(1/(\log\log n)^2)}$ under randomized ETH. In this paper we study NDP-Grid, where all source vertices {s_1,...,s_k} appear on the grid boundary. Our main result is an efficient randomized $2^{O(\sqrt{\log n} \cdot \log\log n)}$-approximation algorithm for this problem. We generalize this result to instances where the source vertices lie within a prescribed distance from the grid boundary. Much of the work on approximation algorithms for NDP relies on the multicommodity flow relaxation of the problem, which is known to have an $Ω(\sqrt n)$ integrality gap, even in grid graphs. Our work departs from this paradigm, and uses a (completely different) linear program only to select the pairs to be routed, while the routing itself is computed by other methods.
Impact of Cooperation in Flow-Induced Diffusive Mobile Molecular Communication
Venue: arXiv cs.IT 2018
Year: 2018

Motivated by the numerous healthcare applications of molecular communication (MC) inside blood vessels, this work considers relay/cooperative nanomachine (CN)-assisted mobile MC between a source nanomachine (SN) and a destination nanomachine (DN) where each nanomachine is mobile in a flow-induced diffusive channel. Using the first hitting time model, the impact of an intermediate CN on the performance of the CN-assisted diffusive mobile MC system with fully absorbing receivers is analyzed in the presence of inter-symbol interference, multi-source interference, and counting errors. For this purpose, the likelihood ratio test based optimal symbol detection scheme is obtained at the DN considering the non-ideal nature of CN, i.e., CN can be in error with a finite probability. Further, to characterize the system performance, closed-form expressions for the end-to-end probabilities of detection and false alarm at the DN are derived between the SN-DN pair incorporating the detection performance of the intermediate CN. In addition, the channel capacity expression is also derived for the aforementioned scenario. Simulation results are presented to corroborate the theoretical results derived and also, to yield insights into system performance.
Causal dynamics of discrete manifolds
Venue: arXiv cs.DM 2018
Year: 2018

We extend Cellular Automata to time-varying discrete geometries. In other words we formalize, and prove theorems about, the intuitive idea of a discrete manifold which evolves in time, subject to two natural constraints: the evolution does not propagate information too fast; and it acts everywhere the same. For this purpose we develop a correspondence between complexes and labeled graphs. In particular we reformulate the properties that characterize discrete manifolds amongst complexes, solely in terms of graphs. In dimensions $n<4$, over bounded-star graphs, it is decidable whether a Cellular Automaton maps discrete manifolds into discrete manifolds.
Cross Domain Image Generation through Latent Space Exploration with Adversarial Loss
Venue: arXiv cs.LG 2018
Year: 2018

Conditional domain generation is a good way to interactively control sample generation process of deep generative models. However, once a conditional generative model has been created, it is often expensive to allow it to adapt to new conditional controls, especially the network structure is relatively deep. We propose a conditioned latent domain transfer framework across latent spaces of unconditional variational autoencoders(VAE). With this framework, we can allow unconditionally trained VAEs to generate images in its domain with conditionals provided by a latent representation of another domain. This framework does not assume commonalities between two domains. We demonstrate effectiveness and robustness of our model under widely used image datasets.
Reconciling complexities: for a stronger integration of approaches to complex socio-technical systems
Venue: arXiv cs.CY 2018
Year: 2018

Systems engineering has developed a mature knowledge on how to design, integrate and manage complex industrial systems, whereas disciplines studying complex systems in nature or society also propose numerous tools for their understanding. Socio-technical systems, that situate at their intersection, could benefit from a higher integration between these. This position paper advocates for such integrated approaches. A bibliometric study through citation networks first illustrates the respective isolation of some of these approaches. We then produce a proof-of-concept of how the transfer of concepts from biology can be useful for the design of complex systems, in the particular case of transportation networks, using a biological network growth model to produce various optimal networks in terms of cost and efficiency. We finally discuss possible disciplinary positioning of such hybrid approaches.
Conditional Generative Adversarial and Convolutional Networks for X-ray Breast Mass Segmentation and Shape Classification
Venue: arXiv cs.CV 2018
Year: 2018

This paper proposes a novel approach based on conditional Generative Adversarial Networks (cGAN) for breast mass segmentation in mammography. We hypothesized that the cGAN structure is well-suited to accurately outline the mass area, especially when the training data is limited. The generative network learns intrinsic features of tumors while the adversarial network enforces segmentations to be similar to the ground truth. Experiments performed on dozens of malignant tumors extracted from the public DDSM dataset and from our in-house private dataset confirm our hypothesis with very high Dice coefficient and Jaccard index (>94% and >89%, respectively) outperforming the scores obtained by other state-of-the-art approaches. Furthermore, in order to detect portray significant morphological features of the segmented tumor, a specific Convolutional Neural Network (CNN) have also been designed for classifying the segmented tumor areas into four types (irregular, lobular, oval and round), which provides an overall accuracy about 72% with the DDSM dataset.
Consequence-Based Axiom Pinpointing
Venue: arXiv cs.LO 2018
Year: 2018

Axiom pinpointing refers to the problem of finding the axioms in an ontology that are relevant for understanding a given entailment or consequence. One approach for axiom pinpointing, known as glass-box, is to modify a classical decision procedure for the entailments into a method that computes the solutions for the pinpointing problem. Recently, consequence-based decision procedures have been proposed as a promising alternative for tableaux-based reasoners for standard ontology languages. In this work, we present a general framework to extend consequence-based algorithms with axiom pinpointing.
Unsupervised Learning for Large-Scale Fiber Detection and Tracking in Microscopic Material Images
Venue: arXiv cs.CV 2018
Year: 2018

Constructing 3D structures from serial section data is a long standing problem in microscopy. The structure of a fiber reinforced composite material can be reconstructed using a tracking-by-detection model. Tracking-by-detection algorithms rely heavily on detection accuracy, especially the recall performance. The state-of-the-art fiber detection algorithms perform well under ideal conditions, but are not accurate where there are local degradations of image quality, due to contaminants on the material surface and/or defocus blur. Convolutional Neural Networks (CNN) could be used for this problem, but would require a large number of manual annotated fibers, which are not available. We propose an unsupervised learning method to accurately detect fibers on the large scale, that is robust against local degradations of image quality. The proposed method does not require manual annotations, but uses fiber shape/size priors and spatio-temporal consistency in tracking to simulate the supervision in the training of the CNN. Experiments show significant improvements over state-of-the-art fiber detection algorithms together with advanced tracking performance.
E-Voting with Blockchain: An E-Voting Protocol with Decentralisation and Voter Privacy
Venue: arXiv cs.CR 2018
Year: 2018

Technology has positive impacts on many aspects of our social life. Designing a 24hour globally connected architecture enables ease of access to a variety of resources and services. Furthermore, technology like Internet has been a fertile ground for innovation and creativity. One of such disruptive innovation is blockchain -- a keystone of cryptocurrencies. The blockchain technology is presented as a game changer for many of the existing and emerging technologies/services. With its immutability property and decentralised architecture, it is taking centre stage in many services as an equalisation factor to the current parity between consumers and large corporations/governments. One of such potential applications of the blockchain is in e-voting schemes. The objective of such a scheme would be to provide a decentralised architecture to run and support a voting scheme that is open, fair and independently verifiable. In this paper, we propose potentially a new e-voting protocol that utilises the blockchain as a transparent ballot box. The protocol has been designed with adhering to the fundamental e-voting properties in mind as well as offering a degree of decentralisation and allowing for the voter to change/update their vote (within the permissible voting period). The paper highlights the pros and cons of using blockchain for such a proposal from practical point view in both development/deployment and usage contexts. Concluding the paper with a potential roadmap for blockchain technology to be able to support complex applications.
Scraping SERPs for Archival Seeds: It Matters When You Start
Venue: arXiv cs.DL 2018
Year: 2018

Event-based collections are often started with a web search, but the search results you find on Day 1 may not be the same as those you find on Day 7. In this paper, we consider collections that originate from extracting URIs (Uniform Resource Identifiers) from Search Engine Result Pages (SERPs). Specifically, we seek to provide insight about the retrievability of URIs of news stories found on Google, and to answer two main questions: first, can one "refind" the same URI of a news story (for the same query) from Google after a given time? Second, what is the probability of finding a story on Google over a given period of time? To answer these questions, we issued seven queries to Google every day for over seven months (2017-05-25 to 2018-01-12) and collected links from the first five SERPs to generate seven collections for each query. The queries represent public interest stories: "healthcare bill," "manchester bombing," "london terrorism," "trump russia," "travel ban," "hurricane harvey," and "hurricane irma." We tracked each URI in all collections over time to estimate the discoverability of URIs from the first five SERPs. Our results showed that the daily average rate at which stories were replaced on the default Google SERP ranged from 0.21 -0.54, and a weekly rate of 0.39 - 0.79, suggesting the fast replacement of older stories by newer stories. The probability of finding the same URI of a news story after one day from the initial appearance on the SERP ranged from 0.34 - 0.44. After a week, the probability of finding the same news stories diminishes rapidly to 0.01 - 0.11. Our findings suggest that due to the difficulty in retrieving the URIs of news stories from Google, collection building that originates from search engines should begin as soon as possible in order to capture the first stages of events, and should persist in order to capture the evolution of the events...
Duluth UROP at SemEval-2018 Task 2: Multilingual Emoji Prediction with Ensemble Learning and Oversampling
Venue: arXiv cs.CL 2018
Year: 2018

This paper describes the Duluth UROP systems that participated in SemEval--2018 Task 2, Multilingual Emoji Prediction. We relied on a variety of ensembles made up of classifiers using Naive Bayes, Logistic Regression, and Random Forests. We used unigram and bigram features and tried to offset the skewness of the data through the use of oversampling. Our task evaluation results place us 19th of 48 systems in the English evaluation, and 5th of 21 in the Spanish. After the evaluation we realized that some simple changes to preprocessing could significantly improve our results. After making these changes we attained results that would have placed us sixth in the English evaluation, and second in the Spanish.
Analysing Symbolic Regression Benchmarks under a Meta-Learning Approach
Venue: arXiv cs.NE 2018
Year: 2018

The definition of a concise and effective testbed for Genetic Programming (GP) is a recurrent matter in the research community. This paper takes a new step in this direction, proposing a different approach to measure the quality of the symbolic regression benchmarks quantitatively. The proposed approach is based on meta-learning and uses a set of dataset meta-features---such as the number of examples or output skewness---to describe the datasets. Our idea is to correlate these meta-features with the errors obtained by a GP method. These meta-features define a space of benchmarks that should, ideally, have datasets (points) covering different regions of the space. An initial analysis of 63 datasets showed that current benchmarks are concentrated in a small region of this benchmark space. We also found out that number of instances and output skewness are the most relevant meta-features to GP output error. Both conclusions can help define which datasets should compose an effective testbed for symbolic regression methods.
Less is More: Simultaneous View Classification and Landmark Detection for Abdominal Ultrasound Images
Venue: arXiv cs.CV 2018
Year: 2018

An abdominal ultrasound examination, which is the most common ultrasound examination, requires substantial manual efforts to acquire standard abdominal organ views, annotate the views in texts, and record clinically relevant organ measurements. Hence, automatic view classification and landmark detection of the organs can be instrumental to streamline the examination workflow. However, this is a challenging problem given not only the inherent difficulties from the ultrasound modality, e.g., low contrast and large variations, but also the heterogeneity across tasks, i.e., one classification task for all views, and then one landmark detection task for each relevant view. While convolutional neural networks (CNN) have demonstrated more promising outcomes on ultrasound image analytics than traditional machine learning approaches, it becomes impractical to deploy multiple networks (one for each task) due to the limited computational and memory resources on most existing ultrasound scanners. To overcome such limits, we propose a multi-task learning framework to handle all the tasks by a single network. This network is integrated to perform view classification and landmark detection simultaneously; it is also equipped with global convolutional kernels, coordinate constraints, and a conditional adversarial module to leverage the performances. In an experimental study based on 187,219 ultrasound images, with the proposed simplified approach we achieve (1) view classification accuracy better than the agreement between two clinical experts and (2) landmark-based measurement errors on par with inter-user variability. The multi-task approach also benefits from sharing the feature extraction during the training process across all tasks and, as a result, outperforms the approaches that address each task individually.
A novel hybrid score level and decision level fusion scheme for cancelable multi-biometric verification
Venue: arXiv cs.CV 2018
Year: 2018

In spite of the benefits of biometric-based authentication systems, there are few concerns raised because of the sensitivity of biometric data to outliers, low performance caused due to intra-class variations and privacy invasion caused by information leakage. To address these issues, we propose a hybrid fusion framework where only the protected modalities are combined to fulfill the requirement of secrecy and performance improvement. This paper presents a method to integrate cancelable modalities utilizing mean-closure weighting (MCW) score level and Dempster-Shafer (DS) theory based decision level fusion for iris and fingerprint to mitigate the limitations in the individual score or decision fusion mechanisms. The proposed hybrid fusion scheme incorporates the similarity scores from different matchers corresponding to each protected modality. The individual scores obtained from different matchers for each modality are combined using MCW score fusion method. The MCW technique achieves the optimal weight for each matcher involved in the score computation. Further, DS theory is applied to the induced scores to output the final decision. The rigorous experimental evaluations on three virtual databases indicate that the proposed hybrid fusion framework outperforms over the component level or individual fusion methods (score level and decision level fusion). As a result, we achieve (48%,66%), (72%,86%) and (49%,38%) of performance improvement over unimodal cancelable iris and unimodal cancelable fingerprint verification systems for Virtual_A, Virtual_B and Virtual_C databases, respectively. Also, the proposed method is robust enough to the variability of scores and outliers satisfying the requirement of secure authentication.
Geometric Understanding of Deep Learning
Venue: arXiv cs.LG 2018
Year: 2018

Deep learning is the mainstream technique for many machine learning tasks, including image recognition, machine translation, speech recognition, and so on. It has outperformed conventional methods in various fields and achieved great successes. Unfortunately, the understanding on how it works remains unclear. It has the central importance to lay down the theoretic foundation for deep learning. In this work, we give a geometric view to understand deep learning: we show that the fundamental principle attributing to the success is the manifold structure in data, namely natural high dimensional data concentrates close to a low-dimensional manifold, deep learning learns the manifold and the probability distribution on it. We further introduce the concepts of rectified linear complexity for deep neural network measuring its learning capability, rectified linear complexity of an embedding manifold describing the difficulty to be learned. Then we show for any deep neural network with fixed architecture, there exists a manifold that cannot be learned by the network. Finally, we propose to apply optimal mass transportation theory to control the probability distribution in the latent space.
SJTU-NLP at SemEval-2018 Task 9: Neural Hypernym Discovery with Term Embeddings
Venue: arXiv cs.CL 2018
Year: 2018

This paper describes a hypernym discovery system for our participation in the SemEval-2018 Task 9, which aims to discover the best (set of) candidate hypernyms for input concepts or entities, given the search space of a pre-defined vocabulary. We introduce a neural network architecture for the concerned task and empirically study various neural network models to build the representations in latent space for words and phrases. The evaluated models include convolutional neural network, long-short term memory network, gated recurrent unit and recurrent convolutional neural network. We also explore different embedding methods, including word embedding and sense embedding for better performance.
Data-Aware Approximate Workflow Scheduling
Venue: arXiv cs.DC 2018
Year: 2018

Optimization of data placement in complex scientific workflows has become very crucial since the large amounts of data generated by these workflows significantly increases the turnaround time of the end-to-end application. It is almost impossible to make an optimal scheduling for the end-to-end workflow without considering the intermediate data movement. In order to reduce the complexity of the workflow-scheduling problem, most of the existing work constrains the problem space by some unrealistic assumptions, which result in non-optimal scheduling in practice. In this study, we propose a genetic data-aware algorithm for the end-to-end workflow scheduling problem. Distinct from the past research, we develop a novel data-aware evaluation function for each chromosome, a common augmenting crossover operator and a simple but effective mutation operator. Our experiments on different workflow structures show that the proposed GA based approach gives a scheduling close to the optimal one.
NetSim -- The framework for complex network generator
Venue: arXiv cs.SI 2018
Year: 2018

Networks are everywhere and their many types, including social networks, the Internet, food webs etc., have been studied for the last few decades. However, in real-world networks, it's hard to find examples that can be easily comparable, i.e. have the same density or even number of nodes and edges. We propose a flexible and extensible NetSim framework to understand how properties in different types of networks change with varying number of edges and vertices. Our approach enables to simulate three classical network models (random, small-world and scale-free) with easily adjustable model parameters and network size. To be able to compare different networks, for a single experimental setup we kept the number of edges and vertices fixed across the models. To understand how they change depending on the number of nodes and edges we ran over 30,000 simulations and analysed different network characteristics that cannot be derived analytically. Two of the main findings from the analysis are that the average shortest path does not change with the density of the scale-free network but changes for small-world and random networks; the apparent difference in mean betweenness centrality of the scale-free network compared with random and small-world networks.