OpenRaiser/Intern-Atlas huggingface dataset:
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Venue: arXiv cs.CC 2018
Year: 2018

We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define a generalization based on zeroing outs which subsumes these two approaches, which we call the Solar method, and an even more general method based on monomial degenerations, which we call the Galactic method. We then design a suite of techniques for proving lower bounds on the value of $ω$, the exponent of matrix multiplication, which can be achieved by algorithms using many tensors $T$ and the Galactic method. Some of our techniques exploit `local' properties of $T$, like finding a sub-tensor of $T$ which is so `weak' that $T$ itself couldn't be used to achieve a good bound on $ω$, while others exploit `global' properties, like $T$ being a monomial degeneration of the structural tensor of a group algebra. Our main result is that there is a universal constant $\ell>2$ such that a large class of tensors generalizing the Coppersmith-Winograd tensor $CW_q$ cannot be used within the Galactic method to show a bound on $ω$ better than $\ell$, for any $q$. We give evidence that previous lower-bounding techniques were not strong enough to show this. We also prove a number of complementary results along the way, including that for any group $G$, the structural tensor of $\mathbb{C}[G]$ can be used to recover the best bound on $ω$ which the Coppersmith-Winograd approach gets using $CW_{|G|-2}$ as long as the asymptotic rank of the structural tensor is not too large.
Using Machine Learning to reduce the energy wasted in Volunteer Computing Environments
Venue: arXiv cs.DC 2018
Year: 2018

High Throughput Computing (HTC) provides a convenient mechanism for running thousands of tasks. Many HTC systems exploit computers which are provisioned for other purposes by utilising their idle time - volunteer computing. This has great advantages as it gives access to vast quantities of computational power for little or no cost. The downside is that running tasks are sacrificed if the computer is needed for its primary use. Normally terminating the task which must be restarted on a different computer - leading to wasted energy and an increase in task completion time. We demonstrate, through the use of simulation, how we can reduce this wasted energy by targeting tasks at computers less likely to be needed for primary use, predicting this idle time through machine learning. By combining two machine learning approaches, namely Random Forest and MultiLayer Perceptron, we save 51.4% of the energy without significantly affecting the time to complete tasks.
An Approach to Energy Efficiency in a Multi-Hop Network Control System through a Trade-Off between H-inf Norm and Global Number of Transmissions
Venue: arXiv cs.SY 2018
Year: 2018

The present work proposes a new approach to energy effiency for filtering of a system interconnected by a Multi-Hop network. The minimization of the energy cost per time unit is obtained through limiting the number of packets retransmission in the Hop-by-Hop mechanism. We explore a trade-Off between system performance, measured by estimation error H-inf norm and energy consumption. The proposal is validated using a theoretical model for energy consumption of MICA2 transceivers.
Named Entity Recognition on Twitter for Turkish using Semi-supervised Learning with Word Embeddings
Venue: arXiv cs.CL 2018
Year: 2018

Recently, due to the increasing popularity of social media, the necessity for extracting information from informal text types, such as microblog texts, has gained significant attention. In this study, we focused on the Named Entity Recognition (NER) problem on informal text types for Turkish. We utilized a semi-supervised learning approach based on neural networks. We applied a fast unsupervised method for learning continuous representations of words in vector space. We made use of these obtained word embeddings, together with language independent features that are engineered to work better on informal text types, for generating a Turkish NER system on microblog texts. We evaluated our Turkish NER system on Twitter messages and achieved better F-score performances than the published results of previously proposed NER systems on Turkish tweets. Since we did not employ any language dependent features, we believe that our method can be easily adapted to microblog texts in other morphologically rich languages.
Autonomous Self-Explanation of Behavior for Interactive Reinforcement Learning Agents
Venue: arXiv cs.AI 2018
Year: 2018

In cooperation, the workers must know how co-workers behave. However, an agent's policy, which is embedded in a statistical machine learning model, is hard to understand, and requires much time and knowledge to comprehend. Therefore, it is difficult for people to predict the behavior of machine learning robots, which makes Human Robot Cooperation challenging. In this paper, we propose Instruction-based Behavior Explanation (IBE), a method to explain an autonomous agent's future behavior. In IBE, an agent can autonomously acquire the expressions to explain its own behavior by reusing the instructions given by a human expert to accelerate the learning of the agent's policy. IBE also enables a developmental agent, whose policy may change during the cooperation, to explain its own behavior with sufficient time granularity.
Mobile Robot Localisation and Navigation Using LEGO NXT and Ultrasonic Sensor
Venue: arXiv cs.RO 2018
Year: 2018

Mobile robots are becoming increasingly important both for individuals and industries. Mobile robotic technology is not only utilised by experts in this field but is also very popular among amateurs. However, implementing a mobile robot to perform tasks autonomously can be expensive because of the need for various types of sensors and the high price of robot platforms. Hence, in this paper we present a mobile robot localisation and navigation system which uses a LEGO ultrasonic sensor in an indoor map based on the LEGO MINDSTORM NXT. This provides an affordable and ready-to-use option for most robot fans. In this paper, an effective method is proposed to extract useful information from the distorted readings collected by the ultrasonic sensor. Then, the particle filter is used to localise the robot. After robot's position is estimated, a sampling-based path planning method is proposed for the robot navigation. This method reduces the robot accumulative motion error by minimising robot turning times and covering distances. The robot localisation and navigation algorithms are implemented in MATLAB. Simulation results show an average accuracy between 1 and 3 cm for three different indoor map locations. Furthermore, experiments performed in a real setup show the effectiveness of the proposed methods.
Electricity consumption forecasting method based on MPSO-BP neural network model
Venue: arXiv cs.NE 2018
Year: 2018

This paper deals with the problem of the electricity consumption forecasting method. An MPSO-BP (modified particle swarm optimization-back propagation) neural network model is constructed based on the history data of a mineral company of Anshan in China. The simulation showed that the convergence of the algorithm and forecasting accuracy using the obtained model are better than those of other traditional ones, such as BP, PSO, fuzzy neural network and so on. Then we predict the electricity consumption of each month in 2017 based on the MPSO-BP neural network model.
Label Noise Filtering Techniques to Improve Monotonic Classification
Venue: arXiv cs.AI 2018
Year: 2018

The monotonic ordinal classification has increased the interest of researchers and practitioners within machine learning community in the last years. In real applications, the problems with monotonicity constraints are very frequent. To construct predictive monotone models from those problems, many classifiers require as input a data set satisfying the monotonicity relationships among all samples. Changing the class labels of the data set (relabelling) is useful for this. Relabelling is assumed to be an important building block for the construction of monotone classifiers and it is proved that it can improve the predictive performance. In this paper, we will address the construction of monotone datasets considering as noise the cases that do not meet the monotonicity restrictions. For the first time in the specialized literature, we propose the use of noise filtering algorithms in a preprocessing stage with a double goal: to increase both the monotonicity index of the models and the accuracy of the predictions for different monotonic classifiers. The experiments are performed over 12 datasets coming from classification and regression problems and show that our scheme improves the prediction capabilities of the monotonic classifiers instead of being applied to original and relabeled datasets. In addition, we have included the analysis of noise filtering process in the particular case of wine quality classification to understand its effect in the predictive models generated.
Learning Spectral Transform Network on 3D Surface for Non-rigid Shape Analysis
Venue: arXiv cs.CV 2018
Year: 2018

Designing a network on 3D surface for non-rigid shape analysis is a challenging task. In this work, we propose a novel spectral transform network on 3D surface to learn shape descriptors. The proposed network architecture consists of four stages: raw descriptor extraction, surface second-order pooling, mixture of power function-based spectral transform, and metric learning. The proposed network is simple and shallow. Quantitative experiments on challenging benchmarks show its effectiveness for non-rigid shape retrieval and classification, e.g., it achieved the highest accuracies on SHREC14, 15 datasets as well as the Range subset of SHREC17 dataset.
On DC based Methods for Phase Retrieval
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we develop a new computational approach which is based on minimizing the difference of two convex functionals (DC) to solve a broader class of phase retrieval problems. The approach splits a standard nonlinear least squares minimizing function associated with the phase retrieval problem into the difference of two convex functions and then solves a sequence of convex minimization sub-problems. For each subproblem, the Nesterov's accelerated gradient descent algorithm or the Barzilai-Borwein (BB) algorithm is used. In the setting of sparse phase retrieval, a standard $\ell_1$ norm term is added into the minimization mentioned above. The subproblem is approximated by a proximal gradient method which is solved by the shrinkage-threshold technique directly without iterations. In addition, a modified Attouch-Peypouquet technique is used to accelerate the iterative computation. These lead to more effective algorithms than the Wirtinger flow (WF) algorithm and the Gauss-Newton (GN) algorithm and etc.. A convergence analysis of both DC based algorithms shows that the iterative solutions is convergent linearly to a critical point and will be closer to a global minimizer than the given initial starting point. Our study is a deterministic analysis while the study for the Wirtinger flow (WF) algorithm and its variants, the Gauss-Newton (GN) algorithm, the trust region algorithm is based on the probability analysis. In particular, the DC based algorithms are able to retrieve solutions using a number $m$ of measurements which is about twice of the number $n$ of entries in the solution with high frequency of successes. When $m\approx n$, the $\ell_1$ DC based algorithm is able to retrieve sparse signals.
Can We Gain More from Orthogonality Regularizations in Training Deep CNNs?
Venue: arXiv cs.LG 2018
Year: 2018

This paper seeks to answer the question: as the (near-) orthogonality of weights is found to be a favorable property for training deep convolutional neural networks, how can we enforce it in more effective and easy-to-use ways? We develop novel orthogonality regularizations on training deep CNNs, utilizing various advanced analytical tools such as mutual coherence and restricted isometry property. These plug-and-play regularizations can be conveniently incorporated into training almost any CNN without extra hassle. We then benchmark their effects on state-of-the-art models: ResNet, WideResNet, and ResNeXt, on several most popular computer vision datasets: CIFAR-10, CIFAR-100, SVHN and ImageNet. We observe consistent performance gains after applying those proposed regularizations, in terms of both the final accuracies achieved, and faster and more stable convergences. We have made our codes and pre-trained models publicly available: https://github.com/nbansal90/Can-we-Gain-More-from-Orthogonality.
Norm-Range Partition: A Universal Catalyst for LSH based Maximum Inner Product Search (MIPS)
Venue: arXiv cs.LG 2018
Year: 2018

Recently, locality sensitive hashing (LSH) was shown to be effective for MIPS and several algorithms including $L_2$-ALSH, Sign-ALSH and Simple-LSH have been proposed. In this paper, we introduce the norm-range partition technique, which partitions the original dataset into sub-datasets containing items with similar 2-norms and builds hash index independently for each sub-dataset. We prove that norm-range partition reduces the query processing complexity for all existing LSH based MIPS algorithms under mild conditions. The key to performance improvement is that norm-range partition allows to use smaller normalization factor most sub-datasets. For efficient query processing, we also formulate a unified framework to rank the buckets from the hash indexes of different sub-datasets. Experiments on real datasets show that norm-range partition significantly reduces the number of probed for LSH based MIPS algorithms when achieving the same recall.
Mean-based Heuristic Search for Real-Time Planning
Venue: arXiv cs.AI 2018
Year: 2018

In this paper, we introduce a new heuristic search algorithm based on mean values for real-time planning, called MHSP. It consists in associating the principles of UCT, a bandit-based algorithm which gave very good results in computer games, and especially in Computer Go, with heuristic search in order to obtain a real-time planner in the context of classical planning. MHSP is evaluated on different planning problems and compared to existing algorithms performing on-line search and learning. Besides, our results highlight the capacity of MHSP to return plans in a real-time manner which tend to an optimal plan over the time which is faster and of better quality compared to existing algorithms in the literature.
A Simple Baseline Algorithm for Graph Classification
Venue: arXiv cs.LG 2018
Year: 2018

Graph classification has recently received a lot of attention from various fields of machine learning e.g. kernel methods, sequential modeling or graph embedding. All these approaches offer promising results with different respective strengths and weaknesses. However, most of them rely on complex mathematics and require heavy computational power to achieve their best performance. We propose a simple and fast algorithm based on the spectral decomposition of graph Laplacian to perform graph classification and get a first reference score for a dataset. We show that this method obtains competitive results compared to state-of-the-art algorithms.
Dating Ancient Paintings of Mogao Grottoes Using Deeply Learnt Visual Codes
Venue: arXiv cs.CV 2018
Year: 2018

Cultural heritage is the asset of all the peoples of the world. The preservation and inheritance of cultural heritage is conducive to the progress of human civilization. In northwestern China, there is a world heritage site -- Mogao Grottoes -- that has a plenty of mural paintings showing the historical cultures of ancient China. To study these historical cultures, one critical procedure is to date the mural paintings, i.e., determining the era when they were created. Until now, most mural paintings at Mogao Grottoes have been dated by directly referring to the mural texts or historical documents. However, some are still left with creation-era undetermined due to the lack of reference materials. Considering that the drawing style of mural paintings was changing along the history and the drawing style can be learned and quantified through painting data, we formulate the problem of mural-painting dating into a problem of drawing-style classification. In fact, drawing styles can be expressed not only in color or curvature, but also in some unknown forms -- the forms that have not been observed. To this end, besides sophisticated color and shape descriptors, a deep convolution neural network is designed to encode the implicit drawing styles. 3860 mural paintings collected from 194 different grottoes with determined creation-era labels are used to train the classification model and build the dating method. In experiments, the proposed dating method is applied to seven mural paintings which were previously dated with controversies, and the exciting new dating results are approved by the Dunhuang expert.
Study of Human Push Recovery
Venue: arXiv cs.RO 2018
Year: 2018

Walking and push recovery controllers for humanoid robots have advanced throughout the years while unsolved gaps leading to undesirable behaviours still exist. Because previous studies are mainly pure engineering methods, while the use of data-driven methods has made impressive achievements in the field of control, we set motivation for exploration of control laws applied by human beings. Successful findings may help fill the gaps in current engineering-based controllers and can potentially improve the performance. In this thesis, we show our complete design and implementation of a set of experiments to collect and process human data, as well as data analysis for model fitting. Using the processed motion data and force data collected, we export the position, velocity and acceleration of our participants' centres of mass to form a one-dimensional point mass model defined by the direction of pushes. As a result, we find that proportional-derivative (PD) control can describe the underlying control law that people used and different PD gains are set for different phases of a push recovery trial within the scope of our study. Our final PD control fittings have an average root mean square error below 0.1m with above 90% of a trial's data points are taken into account on average. We also explore how different error metrics that the PD control model uses influence its performance but neither of the two metrics we proposed can help improve the performance. Finally, we have statistics on how people switch push recovery strategies based on their centre of mass properties at the start of the push. We find that the further the centre of mass is from the steady-state point and the higher the velocity it has, a person is more likely to make a step for push force compensation.
Field Of Interest Proposal for Augmented Mitotic Cell Count: Comparison of two Convolutional Networks
Venue: arXiv cs.CV 2018
Year: 2018

Most tumor grading systems for human as for veterinary histopathology are based upon the absolute count of mitotic figures in a certain reference area of a histology slide. Since time for prognostication is limited in a diagnostic setting, the pathologist will often almost arbitrarily choose a certain field of interest assumed to have the highest mitotic activity. However, as mitotic figures are commonly very sparse on the slide and often have a patchy distribution, this poses a sampling problem which is known to be able to influence the tumor prognostication. On the other hand, automatic detection of mitotic figures can't yet be considered reliable enough for clinical application. In order to aid the work of the human expert and at the same time reduce variance in tumor grading, it is beneficial to assess the whole slide image (WSI) for the highest mitotic activity and use this as a reference region for human counting. For this task, we compare two methods for region of interest proposal, both based on convolutional neural networks (CNN). For both approaches, the CNN performs a segmentation of the WSI to assess mitotic activity. The first method performs a segmentation at the original image resolution, while the second approach performs a segmentation operation at a significantly reduced resolution, cutting down on processing complexity. We evaluate the approach using a dataset of 32 completely annotated whole slide images of canine mast cell tumors, where 22 were used for training of the network and 10 for test. Our results indicate that, while the overall correlation to the ground truth mitotic activity is considerably higher (0.94 vs. 0.83) for the approach based upon the fine resolution network, the field of interest choices are only marginally better. Both approaches propose fields of interest that contain a mitotic count in the upper quartile of respective slides.
The complexity of separation for levels in concatenation hierarchies
Venue: arXiv cs.FL 2018
Year: 2018

We investigate the complexity of the separation problem associated to classes of regular languages. For a class C, C-separation takes two regular languages as input and asks whether there exists a third language in C which includes the first and is disjoint from the second. First, in contrast with the situation for the classical membership problem, we prove that for most classes C, the complexity of C-separation does not depend on how the input languages are represented: it is the same for nondeterministic finite automata and monoid morphisms. Then, we investigate specific classes belonging to finitely based concatenation hierarchies. It was recently proved that the problem is always decidable for levels 1/2 and 1 of any such hierarchy (with inefficient algorithms). Here, we build on these results to show that when the alphabet is fixed, there are polynomial time algorithms for both levels. Finally, we investigate levels 3/2 and 2 of the famous Straubing-Thérien hierarchy. We show that separation is PSPACE-complete for level 3/2 and between PSPACE-hard and EXPTIME for level 2.
The Multi-Scale Impact of the Alzheimer's Disease in the Topology Diversity of Astrocytes Molecular Communications Nanonetworks
Venue: arXiv cs.ET 2018
Year: 2018

The Internet of Bio-Nano-Things is a new paradigm that can bring novel remotely controlled actuation and sensing techniques inside the human body. Towards precise bionano sensing techniques in the brain, we investigate the challenges of modelling spatial distribution of astrocyte networks in developing a mathematical framework that lay the groundwork for future early-detection techniques of neurodegenerative disease. In this paper, we investigate the effect of the $β$-amyloid plaques in astrocytes with the Alzheimer's disease. We developed a computation model of healthy and Alzheimer's diseases astrocytes networks from the state of the art models and results that account for the intracellular pathways, IP$_3$ dynamics, gap junctions, voltage-gated calcium channels and astrocytes volumes. We also implemented different types of astrocytes network topologies including shortcut networks, regular degree networks, Erdös Rényi networks and link radius networks. A proposed multi-scale stochastic computational model captures the relationship between the intracellular and intercellular scales. Lastly, we designed and evaluated a single-hop communication system with frequency modulation using metrics such as propagation extend, molecular delay and channel gain. The results show that the more unstable but at the same time lower level oscillations of Alzheimer's astrocyte networks can create a multi-scale effect on communication between astrocytes with increased molecular delay and lower channel gain compared to healthy astrocytes, with an elevated impact on Erdös Rényi networks and link radius networks topologies.