OpenRaiser/Intern-Atlas huggingface dataset:
Can Bio-Inspired Swarm Algorithms Scale to Modern Societal Problems
Venue: arXiv cs.NE 2019
Year: 2019

Taking inspiration from nature for meta-heuristics has proven popular and relatively successful. Many are inspired by the collective intelligence exhibited by insects, fish and birds. However, there is a question over their scalability to the types of complex problems experienced in the modern world. Natural systems evolved to solve simpler problems effectively, replicating these processes for complex problems may suffer from inefficiencies. Several causal factors can impact scalability; computational complexity, memory requirements or pure problem intractability. Supporting evidence is provided using a case study in Ant Colony Optimisation (ACO) regards tackling increasingly complex real-world fleet optimisation problems. This paper hypothesizes that contrary to common intuition, bio-inspired collective intelligence techniques by their very nature exhibit poor scalability in cases of high dimensionality when large degrees of decision making are required. Facilitating scaling of bio-inspired algorithms necessitates reducing this decision making. To support this hypothesis, an enhanced Partial-ACO technique is presented which effectively reduces ant decision making. Reducing the decision making required by ants by up to 90% results in markedly improved effectiveness and reduced runtimes for increasingly complex fleet optimisation problems. Reductions in traversal timings of 40-50% are achieved for problems with up to 45 vehicles and 437 jobs.
Optimisation of Overparametrized Sum-Product Networks
Venue: arXiv cs.LG 2019
Year: 2019

It seems to be a pearl of conventional wisdom that parameter learning in deep sum-product networks is surprisingly fast compared to shallow mixture models. This paper examines the effects of overparameterization in sum-product networks on the speed of parameter optimisation. Using theoretical analysis and empirical experiments, we show that deep sum-product networks exhibit an implicit acceleration compared to their shallow counterpart. In fact, gradient-based optimisation in deep tree-structured sum-product networks is equal to gradient ascend with adaptive and time-varying learning rates and additional momentum terms.
Delay Violation Probability and Age of Information Interplay in the Two-user Multiple Access Channel
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we study the interplay between delay violation probability and average Age of Information (AoI) in a two-user wireless multiple access channel with multipacket reception (MPR) capability. We consider a system in which users have heterogeneous traffic characteristics: one has stringent delay constraints, while the other measures a source and transmits status updates in order to keep the AoI low. We show the effect of sensor sampling rate on the delay violation probability and that of the service rate of the delay-sensitive user on information freshness.
Citizen Science: An Information Quality Research Frontier
Venue: arXiv cs.CY 2019
Year: 2019

The rapid proliferation of online content producing and sharing technologies resulted in an explosion of user-generated content (UGC), which now extends to scientific data. Citizen science, in which ordinary people contribute information for scientific research, epitomizes UGC. Citizen science projects are typically open to everyone, engage diverse audiences, and challenge ordinary people to produce data of highest quality to be usable in science. This also makes citizen science a very exciting area to study both traditional and innovative approaches to information quality management. With this paper we position citizen science as a leading information quality research frontier. We also show how citizen science opens a unique opportunity for the information systems community to contribute to a broad range of disciplines in natural and social sciences and humanities.
DeepCABAC: Context-adaptive binary arithmetic coding for deep neural network compression
Venue: arXiv cs.LG 2019
Year: 2019

We present DeepCABAC, a novel context-adaptive binary arithmetic coder for compressing deep neural networks. It quantizes each weight parameter by minimizing a weighted rate-distortion function, which implicitly takes the impact of quantization on to the accuracy of the network into account. Subsequently, it compresses the quantized values into a bitstream representation with minimal redundancies. We show that DeepCABAC is able to reach very high compression ratios across a wide set of different network architectures and datasets. For instance, we are able to compress by x63.6 the VGG16 ImageNet model with no loss of accuracy, thus being able to represent the entire network with merely 8.7MB.
Measuring the Complexity of Packet Traces
Venue: arXiv cs.NI 2019
Year: 2019

This paper studies the structure of several real-world traces (including Facebook, High-Performance Computing, Machine Learning, and simulation generated traces) and presents a systematic approach to quantify and compare the structure of packet traces based on the entropy contained in the trace file. Insights into the structure of packet traces can lead to improved network algorithms that are optimized toward specific traffic patterns. We then present a methodology to quantify the temporal and non-temporal components of entropy contained in a packet trace, called the trace complexity, using randomization and compression. We show that trace complexity provides unique insights into the characteristics of various applications and argue that there is a need for traffic generation models that preserve the intrinsic structure of empirically measured application traces. We then propose a traffic generator model that is able to produce a synthetic trace that matches the complexity level of its corresponding real-world trace.
Importance of Coordination and Cultural Diversity for an Efficient and Flexible Manufacturing System
Venue: arXiv cs.CY 2019
Year: 2019

Manufacturing systems of the future need to have flexible resources and flexible routing to produce extremely personalized products, even of lot size equal to one. In this paper, we have proposed a framework, which is designed to achieve this goal. Towards this, we have integrated an established cultural evolution model to achieve desired flexibility of resources and acceptable routing time. Promising results are evidenced through a simple proof-of-concept simulation.
S-Flow GAN
Venue: arXiv cs.CV 2019
Year: 2019

Our work offers a new method for domain translation from semantic label maps and Computer Graphic (CG) simulation edge map images to photo-realistic images. We train a Generative Adversarial Network (GAN) in a conditional way to generate a photo-realistic version of a given CG scene. Existing architectures of GANs still lack the photo-realism capabilities needed to train DNNs for computer vision tasks, we address this issue by embedding edge maps, and training it in an adversarial mode. We also offer an extension to our model that uses our GAN architecture to create visually appealing and temporally coherent videos.
SvTPM: A Secure and Efficient vTPM in the Cloud
Venue: arXiv cs.CR 2019
Year: 2019

Virtual Trusted Platform Modules (vTPMs) have been widely used in commercial cloud platforms (e.g. Google Cloud, VMware Cloud, and Microsoft Azure) to provide virtual root-of-trust for virtual machines. Unfortunately, current state-of-the-art vTPM implementations are suffering from confidential data leakage and high performance overhead. In this paper, we present SvTPM, a secure and efficient software-based vTPM implementation based on hardware-rooted Trusted Execution Environment (TEE), providing a whole life cycle protection of vTPMs in the cloud. SvTPM offers strong isolation protection, so that cloud tenants or even cloud administrators cannot get vTPM's private keys or any other sensitive data. In SvTPM, we identify and solve a couple of critical security challenges for vTPM protection with SGX, such as NVRAM replacement attack, rollback attacks, trust establishment, and a fine-grained trusted clock. We implement a prototype of SvTPM on both QEMU and KVM. Performance evaluation results show that SvTPM achieves orders of magnitude of performance gains comparing to the vTPMs protected with physical TPM. The launch time of SvTPM is 2600$\times$ faster than vTPMs built upon hardware TPM. In the micro-benchmarks evaluation, we find that the command execution latency of SvTPM is smaller than or equal to the existing schemes.
Completeness and Incompleteness of Synchronous Kleene Algebra
Venue: arXiv cs.LO 2019
Year: 2019

Synchronous Kleene algebra (SKA), an extension of Kleene algebra (KA), was proposed by Prisacariu as a tool for reasoning about programs that may execute synchronously, i.e., in lock-step. We provide a countermodel witnessing that the axioms of SKA are incomplete w.r.t. its language semantics, by exploiting a lack of interaction between the synchronous product operator and the Kleene star. We then propose an alternative set of axioms for SKA, based on Salomaa's axiomatisation of regular languages, and show that these provide a sound and complete characterisation w.r.t. the original language semantics.
Bayesian Pitch Tracking Based on the Harmonic Model
Venue: arXiv cs.SD 2019
Year: 2019

Fundamental frequency is one of the most important characteristics of speech and audio signals. Harmonic model-based fundamental frequency estimators offer a higher estimation accuracy and robustness against noise than the widely used autocorrelation-based methods. However, the traditional harmonic model-based estimators do not take the temporal smoothness of the fundamental frequency, the model order, and the voicing into account as they process each data segment independently. In this paper, a fully Bayesian fundamental frequency tracking algorithm based on the harmonic model and a first-order Markov process model is proposed. Smoothness priors are imposed on the fundamental frequencies, model orders, and voicing using first-order Markov process models. Using these Markov models, fundamental frequency estimation and voicing detection errors can be reduced. Using the harmonic model, the proposed fundamental frequency tracker has an improved robustness to noise. An analytical form of the likelihood function, which can be computed efficiently, is derived. Compared to the state-of-the-art neural network and non-parametric approaches, the proposed fundamental frequency tracking algorithm reduces the mean absolute errors and gross errors by 15\% and 20\% on the Keele pitch database and 36\% and 26\% on sustained /a/ sounds from a database of Parkinson's disease voices under 0 dB white Gaussian noise. A MATLAB version of the proposed algorithm is made freely available for reproduction of the results\footnote{An implementation of the proposed algorithm using MATLAB may be found in \url{https://tinyurl.com/yxn4a543}
Geometric Estimation of Multivariate Dependency
Venue: arXiv cs.LG 2019
Year: 2019

This paper proposes a geometric estimator of dependency between a pair of multivariate samples. The proposed estimator of dependency is based on a randomly permuted geometric graph (the minimal spanning tree) over the two multivariate samples. This estimator converges to a quantity that we call the geometric mutual information (GMI), which is equivalent to the Henze-Penrose divergence [1] between the joint distribution of the multivariate samples and the product of the marginals. The GMI has many of the same properties as standard MI but can be estimated from empirical data without density estimation; making it scalable to large datasets. The proposed empirical estimator of GMI is simple to implement, involving the construction of an MST spanning over both the original data and a randomly permuted version of this data. We establish asymptotic convergence of the estimator and convergence rates of the bias and variance for smooth multivariate density functions belonging to a Hölder class. We demonstrate the advantages of our proposed geometric dependency estimator in a series of experiments.
Shortest-Path-Preserving Rounding
Venue: arXiv cs.CC 2019
Year: 2019

Various applications of graphs, in particular applications related to finding shortest paths, naturally get inputs with real weights on the edges. However, for algorithmic or visualization reasons, inputs with integer weights would often be preferable or even required. This raises the following question: given an undirected graph with non-negative real weights on the edges and an error threshold $\varepsilon$, how efficiently can we decide whether we can round all weights such that shortest paths are maintained, and the change of weight of each shortest path is less than $\varepsilon$? So far, only for path-shaped graphs a polynomial-time algorithm was known. In this paper we prove, by reduction from 3-SAT, that, in general, the problem is NP-hard. However, if the graph is a tree with $n$ vertices, the problem can be solved in $O(n^2)$ time.
Mathematical method for calculating batch fragmentations and their impacts on product recall within a FIFO assignment policy
Venue: arXiv cs.CE 2019
Year: 2019

This study explores the interactions between order sizes, batch sizes and potential product recalls within a FIFO assignment policy. Evidence is provided that the extent of a product recall is related to the fragmentation of the batches of input materials as it amplifies the impact of a crisis. A new management indicator is proposed in order to quantify the expected number of fragments composing a customer order FrBO. A probabilistic analysis reveals that for a given likelihood of crisis, the presence of different batches in a customer order will largely increase its risk. Accordingly, a new equation is proposed for calculating the expected recall size. Taking into account the fragmentation measure allows, for the first time, for the integration of a proactive product recall policy in the batch sizing decision process. A Monte Carlo simulation is performed to validate the effectiveness of this approach.
Quantifying Novelty and Influence, and the Patterns of Paradigm Shifts
Venue: arXiv cs.SI 2019
Year: 2019

Recent advances in the quantitative, computational methodology for the modeling and analysis of heterogeneous large-scale data are leading to new opportunities for understanding of human behaviors and faculties, including the manifestation of creativity that drives creative enterprises such as science. While innovation is crucial for novel and influential achievements, quantifying these qualities in creative works remains a challenge. Here we present an information-theoretic framework for computing the novelty and influence of creative works based on their generation probabilities reflecting the degree of uniqueness of their elements in comparison with other works. Applying the formalism to the data set of a high-quality, large-scale classical piano compositions represented as symbolic progressions of chords-works of significant scientific and intellectual value-spanning several centuries of musical history, we find that the enterprise's developmental history can be characterized as a dynamic process of the emergence of dominant, paradigmatic creative styles that define distinct historical periods. These findings can lead to a deeper understanding of innovation, human creativity, and the advancement of creative enterprises.
Software Citation Implementation Challenges
Venue: arXiv cs.CY 2019
Year: 2019

The main output of the FORCE11 Software Citation working group (https://www.force11.org/group/software-citation-working-group) was a paper on software citation principles (https://doi.org/10.7717/peerj-cs.86) published in September 2016. This paper laid out a set of six high-level principles for software citation (importance, credit and attribution, unique identification, persistence, accessibility, and specificity) and discussed how they could be used to implement software citation in the scholarly community. In a series of talks and other activities, we have promoted software citation using these increasingly accepted principles. At the time the initial paper was published, we also provided guidance and examples on how to make software citable, though we now realize there are unresolved problems with that guidance. The purpose of this document is to provide an explanation of current issues impacting scholarly attribution of research software, organize updated implementation guidance, and identify where best practices and solutions are still needed.
Voronoi diagram of orthogonal polyhedra in two and three dimensions
Venue: arXiv cs.CG 2019
Year: 2019

Voronoi diagrams are a fundamental geometric data structure for obtaining proximity relations. We consider collections of axis-aligned orthogonal polyhedra in two and three-dimensional space under the max-norm, which is a particularly useful scenario in certain application domains. We construct the exact Voronoi diagram inside an orthogonal polyhedron with holes defined by such polyhedra. Our approach avoids creating full-dimensional elements on the Voronoi diagram and yields a skeletal representation of the input object. We introduce a complete algorithm in 2D and 3D that follows the subdivision paradigm relying on a bounding-volume hierarchy; this is an original approach to the problem. The complexity is adaptive and comparable to that of previous methods. Under a mild assumption it is $O(n / Δ+ 1 / Δ^2)$ in 2D or $O(nα^2 / Δ^2 +1 / Δ^3)$ in 3D, where $n$ is the number of sites, namely edges or facets resp., $Δ$ is the maximum cell size for the subdivision to stop, and $α$ bounds vertex cardinality per facet. We also provide a numerically stable, open-source implementation in Julia, illustrating the practical nature of our algorithm.
Design of conversational humanoid robot based on hardware independent gesture generation
Venue: arXiv cs.RO 2019
Year: 2019

With an increasing need for elderly and disability care, there is an increasing opportunity for intelligent and mobile devices such as robots to provide care and support solutions. In order to naturally assist and interact with humans, a robot must possess effective conversational capabilities. Gestures accompanying spoken sentences are an important factor in human-to-human conversational communication. Humanoid robots must also use gestures if they are to be capable of the rich interactions implied and afforded by their humanlike appearance. However, present systems for gesture generation do not dynamically provide realistic physical gestures that are naturally understood by humans. A method for humanoid robots to generate gestures along with spoken sentences is proposed herein. We emphasize that our gesture-generating architecture can be applied to any type of humanoid robot through the use of labanotation, which is an existing system for notating human dance movements. Labanotation's gesture symbols can computationally transformed to be compatible across a range of robots with doddering physical characteristics. This paper describes a solution as an integrated system for conversational robots whose speech and gestures can supplement each other in human-robot interaction.
A comparison of evaluation methods in coevolution
Venue: arXiv cs.NE 2019
Year: 2019

In this research, we compare four different evaluation methods in coevolution on the Majority Function problem. The size of the problem is selected such that evaluation against all possible test cases is feasible. Two measures are used for the comparisons, i.e., the objective fitness derived from evaluating solutions against all test cases, and the objective fitness correlation (OFC), which is defined as the correlation coefficient between subjective and objective fitness. The results of our experiments suggest that a combination of average score and weighted informativeness may provide a more accurate evaluation in coevolution. In order to confirm this difference, a series of t-tests on the preference between each pair of the evaluation methods is performed. The resulting significance is affirmative, and the tests for two quality measures show similar preference on four evaluation methods. %This study is the first time OFC is actually computed on a real problem. Experiments on Majority Function problems with larger sizes and Parity problems are in progress, and their results will be added in the final version.
aUToTrack: A Lightweight Object Detection and Tracking System for the SAE AutoDrive Challenge
Venue: arXiv cs.RO 2019
Year: 2019

The University of Toronto is one of eight teams competing in the SAE AutoDrive Challenge -- a competition to develop a self-driving car by 2020. After placing first at the Year 1 challenge, we are headed to MCity in June 2019 for the second challenge. There, we will interact with pedestrians, cyclists, and cars. For safe operation, it is critical to have an accurate estimate of the position of all objects surrounding the vehicle. The contributions of this work are twofold: First, we present a new object detection and tracking dataset (UofTPed50), which uses GPS to ground truth the position and velocity of a pedestrian. To our knowledge, a dataset of this type for pedestrians has not been shown in the literature before. Second, we present a lightweight object detection and tracking system (aUToTrack) that uses vision, LIDAR, and GPS/IMU positioning to achieve state-of-the-art performance on the KITTI Object Tracking benchmark. We show that aUToTrack accurately estimates the position and velocity of pedestrians, in real-time, using CPUs only. aUToTrack has been tested in closed-loop experiments on a real self-driving car, and we demonstrate its performance on our dataset.
Toward Learning a Unified Many-to-Many Mapping for Diverse Image Translation
Venue: arXiv cs.CV 2019
Year: 2019

Image-to-image translation, which translates input images to a different domain with a learned one-to-one mapping, has achieved impressive success in recent years. The success of translation mainly relies on the network architecture to reserve the structural information while modify the appearance slightly at the pixel level through adversarial training. Although these networks are able to learn the mapping, the translated images are predictable without exclusion. It is more desirable to diversify them using image-to-image translation by introducing uncertainties, i.e., the generated images hold potential for variations in colors and textures in addition to the general similarity to the input images, and this happens in both the target and source domains. To this end, we propose a novel generative adversarial network (GAN) based model, InjectionGAN, to learn a many-to-many mapping. In this model, the input image is combined with latent variables, which comprise of domain-specific attribute and unspecific random variations. The domain-specific attribute indicates the target domain of the translation, while the unspecific random variations introduce uncertainty into the model. A unified framework is proposed to regroup these two parts and obtain diverse generations in each domain. Extensive experiments demonstrate that the diverse generations have high quality for the challenging image-to-image translation tasks where no pairing information of the training dataset exits. Both quantitative and qualitative results prove the superior performance of InjectionGAN over the state-of-the-art approaches.