OpenRaiser/Intern-Atlas huggingface dataset:
Towards a Semantic Measure of the Execution Time in Call-by-Value lambda-Calculus
Venue: arXiv cs.LO 2019
Year: 2019

We investigate the possibility of a semantic account of the execution time (i.e. the number of beta-steps leading to the normal form, if any) for the shuffling calculus, an extension of Plotkin's call-by-value lambda-calculus. For this purpose, we use a linear logic based denotational model that can be seen as a non-idempotent intersection type system: relational semantics. Our investigation is inspired by similar ones for linear logic proof-nets and untyped call-by-name lambda-calculus. We first prove a qualitative result: a (possibly open) term is normalizable for weak reduction (which does not reduce under abstractions) if and only if its interpretation is not empty. We then show that the size of type derivations can be used to measure the execution time. Finally, we show that, differently from the case of linear logic and call-by-name lambda-calculus, the quantitative information enclosed in type derivations does not lift to types (i.e. to the interpretation of terms). To get a truly semantic measure of execution time in a call-by-value setting, we conjecture that a refinement of its syntax and operational semantics is needed.
Distributed Bio-inspired Humanoid Posture Control
Venue: arXiv cs.SY 2019
Year: 2019

This paper presents an innovative distributed bio-inspired posture control strategy for a humanoid, employing a balance control system DEC (Disturbance Estimation and Compensation). Its inherently modular structure could potentially lead to conflicts among modules, as already shown in literature. A distributed control strategy is presented here, whose underlying idea is to let only one module at a time perform balancing, whilst the other joints are controlled to be at a fixed position. Modules agree, in a distributed fashion, on which module to enable, by iterating a max-consensus protocol. Simulations performed with a triple inverted pendulum model show that this approach limits the conflicts among modules while achieving the desired posture and allows for saving energy while performing the task. This comes at the cost of a higher rise time.
Building a Nest by an Automaton
Venue: arXiv cs.DS 2019
Year: 2019

A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $\mathbb{Z} \times \mathbb{Z}$. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the field, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its span. The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a nest. That is, the robot has to move all bricks in such a way that the span of the resulting field be the smallest. Our main result is the design of a deterministic finite automaton that accomplishes this task and subsequently stops, for every initially connected field, in time $O(sz)$, where $s$ is the span of the initial field and $z$ is the number of bricks. We show that this complexity is optimal.
Optical machine learning with incoherent light and a single-pixel detector
Venue: arXiv cs.CV 2019
Year: 2019

An optical diffractive neural network (DNN) can be implemented with a cascaded phase mask architecture. Like an optical computer, the system can perform machine learning tasks such as number digit recognition in an all-optical manner. However, the system can only work under coherent light illumination and the precision requirement in practical experiments is quite high. This paper proposes an optical machine learning framework based on single-pixel imaging (MLSPI). The MLSPI system can perform the same linear pattern recognition task as DNN. Furthermore, it can work under incoherent lighting conditions, has lower experimental complexity and can be easily programmable.
Secure Communication in Dynamic Wireless Ad hoc Networks
Venue: arXiv cs.IT 2019
Year: 2019

We consider a wireless ad hoc network in the presence of eavesdroppers (EDs), where the nodes are distributed according to independent Poisson point processes (PPPs). The legitimate nodes follow the half-duplex mode of operation employing the slotted ALOHA protocol for transmission. For such a network, a novel communication scheme that induces a time-varying secure connectivity graph (SCG) is proposed, and the connectivity behavior of this induced SCG is studied. In particular, for a legitimate node in the network, we analyze (i) the average number of incoming edges and the average number of outgoing edges; (ii) the time to nearest-neighbor secure connectivity; and (iii) a condition on the EDs' density that allows information percolation, {\ie}, a condition for the existence of a `giant' component. The average time for secure connectivity among the nodes in this giant component is shown to scale linearly with the Euclidean distance. Further, we show that by splitting the packets into two sub-packets and routing each sub-packet along paths that are sufficiently far apart can (a) potentially improve secure connectivity and (b) reduce the overall delay incurred in exchanging packets between any two legitimate nodes in the giant component.
Fixed-Symbol Aided Random Access Scheme for Machine-to-Machine Communications
Venue: arXiv cs.IT 2019
Year: 2019

The massiveness of devices in crowded Machine-to-Machine (M2M) communications brings new challenges to existing random-access (RA) schemes, such as heavy signaling overhead and severe access collisions. In order to reduce the signaling overhead, we propose a fixed-symbol aided RA scheme where active devices access the network in a grant-free method, i.e., data packets are directly transmitted in randomly chosen slots. To further address the access collision which impedes the activity detection, one fixed symbol is inserted into each transmitted data packet in the proposed scheme. An iterative message passing based activity detection (MP-AD) algorithm is performed upon the received signal of this fixed symbol to detect the device activity in each slot. In addition, the deep neural network-aided MP-AD (DNN-MP-AD) algorithm is further designed to alleviate the correlation problem of the iterative message passing process. In the DNN-MP-AD algorithm, the iterative message passing process is transferred from a factor graph to a DNN. Weights are imposed on the messages in the DNN and further trained to improve the accuracy of the device activity detection. Finally, numerical simulations are provided for the throughput of the proposed RA scheme, the accuracy of the proposed MP-AD algorithm, as well as the improvement brought by the DNN-MP-AD algorithm.
Unification and combination of iterative insertion strategies with rudimentary traversals and failure
Venue: arXiv cs.LO 2019
Year: 2019

We introduce a new class of extensions of terms that consists in navigation strategies and insertion of contexts. We introduce an operation of combination on this class which is associative, admits a neutral element and so that each extension is idempotent. The class of extension is also shown to be closed by combination, with a constructive proof. This new framework is general and independent of any application semantics. However it has been introduced for the kernel of a software tool which aims at aiding derivation of multiscale partial differential equation models.
Setup of a Recurrent Neural Network as a Body Model for Solving Inverse and Forward Kinematics as well as Dynamics for a Redundant Manipulator
Venue: arXiv cs.RO 2019
Year: 2019

An internal model of the own body can be assumed a fundamental and evolutionary-early representation as it is present throughout the animal kingdom. Such functional models are, on the one hand, required in motor control, for example solving the inverse kinematic or dynamic task in goal-directed movements or a forward task in ballistic movements. On the other hand, such models are recruited in cognitive tasks as are planning ahead or observation of actions of a conspecific. Here, we present a functional internal body model that is based on the Mean of Multiple Computations principle. For the first time such a model is completely realized in a recurrent neural network as necessary normalization steps are integrated into the neural model itself. Secondly, a dynamic extension is applied to the model. It is shown how the neural network solves a series of inverse tasks. Furthermore, emerging representation in transformational layers are analyzed that show a form of prototypical population-coding as found in place or direction cells.
Generated Loss and Augmented Training of MNIST VAE
Venue: arXiv cs.LG 2019
Year: 2019

The variational autoencoder (VAE) framework is a popular option for training unsupervised generative models, featuring ease of training and latent representation of data. The objective function of VAE does not guarantee to achieve the latter, however, and failure to do so leads to a frequent failure mode called posterior collapse. Even in successful cases, VAEs often result in low-precision reconstructions and generated samples. The introduction of the KL-divergence weight $β$ can help steer the model clear of posterior collapse, but its tuning is often a trial-and-error process with no guiding metrics. Here we test the idea of using the total VAE loss of generated samples (generated loss) as the proxy metric for generation quality, the related hypothesis that VAE reconstruction from the mean latent vector tends to be a more typical example of its class than the original, and the idea of exploiting this property by augmenting training data with generated variants (augmented training). The results are mixed, but repeated encoding and decoding indeed result in qualitatively and quantitatively more typical examples from both convolutional and fully-connected MNIST VAEs, suggesting that it may be an inherent property of the VAE framework.
A Noise-aware Enhancement Method for Underexposed Images
Venue: arXiv cs.MM 2019
Year: 2019

A novel method of contrast enhancement is proposed for underexposed images, in which heavy noise is hidden. Under low light conditions, images taken by digital cameras have low contrast in dark or bright regions. This is due to a limited dynamic range that imaging sensors have. For these reasons, various contrast enhancement methods have been proposed so far. These methods, however, have two problems: (1) The loss of details in bright regions due to over-enhancement of contrast. (2) The noise is amplified in dark regions because conventional enhancement methods do not consider noise included in images. The proposed method aims to overcome these problems. In the proposed method, a shadow-up function is applied to adaptive gamma correction with weighting distribution, and a denoising filter is also used to avoid noise being amplified in dark regions. As a result, the proposed method allows us not only to enhance contrast of dark regions, but also to avoid amplifying noise, even under strong noise environments.
Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol
Venue: arXiv cs.DC 2019
Year: 2019

We study a process of \emph{averaging} in a distributed system with \emph{noisy communication}. Each of the agents in the system starts with some value and the goal of each agent is to compute the average of all the initial values. In each round, one pair of agents is drawn uniformly at random from the whole population, communicates with each other and each of these two agents updates their local value based on their own value and the received message. The communication is noisy and whenever an agent sends any value $v$, the receiving agent receives $v+N$, where $N$ is a zero-mean Gaussian random variable. The two quality measures of interest are (i) the total sum of squares $TSS(t)$, which measures the sum of square distances from the average load to the \emph{initial average} and (ii) $\barϕ(t)$, measures the sum of square distances from the average load to the \emph{running average} (average at time $t$). It is known that the simple averaging protocol---in which an agent sends its current value and sets its new value to the average of the received value and its current value---converges eventually to a state where $\barϕ(t)$ is small. It has been observed that $TSS(t)$, due to the noise, eventually diverges and previous research---mostly in control theory---has focused on showing eventual convergence w.r.t. the running average. We obtain the first probabilistic bounds on the convergence time of $\barϕ(t)$ and precise bounds on the drift of $TSS(t)$ that show that albeit $TSS(t)$ eventually diverges, for a wide and interesting range of parameters, $TSS(t)$ stays small for a number of rounds that is polynomial in the number of agents. Our results extend to the synchronous setting and settings where the agents are restricted to discrete values and perform rounding.
Generalized Modularity Embedding: a General Framework for Network Embedding
Venue: arXiv cs.SI 2019
Year: 2019

The network embedding problem aims to map nodes that are similar to each other to vectors in a Euclidean space that are close to each other. Like centrality analysis (ranking) and community detection, network embedding is in general considered as an ill-posed problem, and its solution may depend on a person's view on this problem. In this book chapter, we adopt the framework of sampled graphs that treat a person's view as a sampling method for a network. The modularity for a sampled graph, called the generalized modularity in the book chapter, is a similarity matrix that has a specific probabilistic interpretation. One of the main contributions of this book chapter is to propose using the generalized modularity matrix for network embedding and show that the network embedding problem can be treated as a trace maximization problem like the community detection problem. Our generalized modularity embedding approach is very general and flexible. In particular, we show that the Laplacian eigenmaps is a special case of our generalized modularity embedding approach. Also, we show that dimensionality reduction can be done by using a particular sampled graph. Various experiments are conducted on real datasets to illustrate the effectiveness of our approach.
How much do you perceive this? An analysis on perceptions of geometric features, personalities and emotions in virtual humans (Extended Version)
Venue: arXiv cs.GR 2019
Year: 2019

This work aims to evaluate people's perception regarding geometric features, personalities and emotions characteristics in virtual humans. For this, we use as a basis, a dataset containing the tracking files of pedestrians captured from spontaneous videos and visualized them as identical virtual humans. The goal is to focus on their behavior and not being distracted by other features. In addition to tracking files containing their positions, the dataset also contains pedestrian emotions and personalities detected using Computer Vision and Pattern Recognition techniques. We proceed with our analysis in order to answer the question if subjects can perceive geometric features as distances/speeds as well as emotions and personalities in video sequences when pedestrians are represented by virtual humans. Regarding the participants, an amount of 73 people volunteered for the experiment. The analysis was divided in two parts: i) evaluation on perception of geometric characteristics, such as density, angular variation, distances and speeds, and ii) evaluation on personality and emotion perceptions. Results indicate that, even without explaining to the participants the concepts of each personality or emotion and how they were calculated (considering geometric characteristics), in most of the cases, participants perceived the personality and emotion expressed by the virtual agents, in accordance with the available ground truth.
Dynamic Walking with Compliance on a Cassie Bipedal Robot
Venue: arXiv cs.RO 2019
Year: 2019

The control of bipedal robotic walking remains a challenging problem in the domains of computation and experiment, due to the multi-body dynamics and various sources of uncertainty. In recent years, there has been a rising trend towards model reduction and the design of intuitive controllers to overcome the gap between assumed model and reality. Despite its viability in practical implementation, this local representation of true dynamics naturally indicate limited scalibility towards more dynamical behaviors. With the goal of moving towards increasingly dynamic behaviors, we leverage the detailed full body dynamics to generate controllers for the robotic system which utilizes compliant elements in the passive dynamics. In this process, we present a feasible computation method that yields walking trajectories for a highly complex robotic system. Direct implementation of these results on physical hardware is also performed with minimal tuning and heuristics. We validate the suggested method by applying a consistent control scheme across simulation, optimization and experiment, the result is that the bipedal robot Cassie walks over a variety of indoor and outdoor terrains reliably.
Skin Cancer Segmentation and Classification with NABLA-N and Inception Recurrent Residual Convolutional Networks
Venue: arXiv cs.CV 2019
Year: 2019

In the last few years, Deep Learning (DL) has been showing superior performance in different modalities of biomedical image analysis. Several DL architectures have been proposed for classification, segmentation, and detection tasks in medical imaging and computational pathology. In this paper, we propose a new DL architecture, the NABLA-N network, with better feature fusion techniques in decoding units for dermoscopic image segmentation tasks. The NABLA-N network has several advances for segmentation tasks. First, this model ensures better feature representation for semantic segmentation with a combination of low to high-level feature maps. Second, this network shows better quantitative and qualitative results with the same or fewer network parameters compared to other methods. In addition, the Inception Recurrent Residual Convolutional Neural Network (IRRCNN) model is used for skin cancer classification. The proposed NABLA-N network and IRRCNN models are evaluated for skin cancer segmentation and classification on the benchmark datasets from the International Skin Imaging Collaboration 2018 (ISIC-2018). The experimental results show superior performance on segmentation tasks compared to the Recurrent Residual U-Net (R2U-Net). The classification model shows around 87% testing accuracy for dermoscopic skin cancer classification on ISIC2018 dataset.
Adaptive Collaborative Similarity Learning for Unsupervised Multi-view Feature Selection
Venue: arXiv cs.IR 2019
Year: 2019

In this paper, we investigate the research problem of unsupervised multi-view feature selection. Conventional solutions first simply combine multiple pre-constructed view-specific similarity structures into a collaborative similarity structure, and then perform the subsequent feature selection. These two processes are separate and independent. The collaborative similarity structure remains fixed during feature selection. Further, the simple undirected view combination may adversely reduce the reliability of the ultimate similarity structure for feature selection, as the view-specific similarity structures generally involve noises and outlying entries. To alleviate these problems, we propose an adaptive collaborative similarity learning (ACSL) for multi-view feature selection. We propose to dynamically learn the collaborative similarity structure, and further integrate it with the ultimate feature selection into a unified framework. Moreover, a reasonable rank constraint is devised to adaptively learn an ideal collaborative similarity structure with proper similarity combination weights and desirable neighbor assignment, both of which could positively facilitate the feature selection. An effective solution guaranteed with the proved convergence is derived to iteratively tackle the formulated optimization problem. Experiments demonstrate the superiority of the proposed approach.
Finding Hexahedrizations for Small Quadrangulations of the Sphere
Venue: arXiv cs.CG 2019
Year: 2019

This paper tackles the challenging problem of constrained hexahedral meshing. An algorithm is introduced to build combinatorial hexahedral meshes whose boundary facets exactly match a given quadrangulation of the topological sphere. This algorithm is the first practical solution to the problem. It is able to compute small hexahedral meshes of quadrangulations for which the previously known best solutions could only be built by hand or contained thousands of hexahedra. These challenging quadrangulations include the boundaries of transition templates that are critical for the success of general hexahedral meshing algorithms. The algorithm proposed in this paper is dedicated to building combinatorial hexahedral meshes of small quadrangulations and ignores the geometrical problem. The key idea of the method is to exploit the equivalence between quad flips in the boundary and the insertion of hexahedra glued to this boundary. The tree of all sequences of flipping operations is explored, searching for a path that transforms the input quadrangulation Q into a new quadrangulation for which a hexahedral mesh is known. When a small hexahedral mesh exists, a sequence transforming Q into the boundary of a cube is found; otherwise, a set of pre-computed hexahedral meshes is used. A novel approach to deal with the large number of problem symmetries is proposed. Combined with an efficient backtracking search, it allows small shellable hexahedral meshes to be found for all even quadrangulations with up to 20 quadrangles. All 54,943 such quadrangulations were meshed using no more than 72 hexahedra. This algorithm is also used to find a construction to fill arbitrary domains, thereby proving that any ball-shaped domain bounded by n quadrangles can be meshed with no more than 78 n hexahedra. This very significantly lowers the previous upper bound of 5396 n.
On adaptive algorithms for maximum matching
Venue: arXiv cs.DS 2019
Year: 2019

In the fundamental Maximum Matching problem the task is to find a maximum cardinality set of pairwise disjoint edges in a given undirected graph. The fastest algorithm for this problem, due to Micali and Vazirani, runs in time $\mathcal{O}(\sqrt{n}m)$ and stands unbeaten since 1980. It is complemented by faster, often linear-time, algorithms for various special graph classes. Moreover, there are fast parameterized algorithms, e.g., time $\mathcal{O}(km\log n)$ relative to tree-width $k$, which outperform $\mathcal{O}(\sqrt{n}m)$ when the parameter is sufficiently small. We show that the Micali-Vazirani algorithm, and in fact any algorithm following the phase framework of Hopcroft and Karp, is adaptive to beneficial input structure. We exhibit several graph classes for which such algorithms run in linear time $\mathcal{O}(n+m)$. More strongly, we show that they run in time $\mathcal{O}(\sqrt{k}m)$ for graphs that are $k$ vertex deletions away from any of several such classes, without explicitly computing an optimal or approximate deletion set; before, most such bounds were at least $Ω(km)$. Thus, any phase-based matching algorithm with linear-time phases obliviously interpolates between linear time for $k=\mathcal{O}(1)$ and the worst case of $\mathcal{O}(\sqrt{n}m)$ when $k=Θ(n)$. We complement our findings by proving that the phase framework by itself still allows $Ω(\sqrt{n})$ phases, and hence time $Ω(\sqrt{n}m)$, even on paths, cographs, and bipartite chain graphs.