OpenRaiser/Intern-Atlas huggingface dataset:
Weight-based Fish School Search algorithm for Many-Objective Optimization
Venue: arXiv cs.NE 2019
Year: 2019

Optimization problems with more than one objective consist in a very attractive topic for researchers due to its applicability in real-world situations. Over the years, the research effort in the Computational Intelligence field resulted in algorithms able to achieve good results by solving problems with more than one conflicting objective. However, these techniques do not exhibit the same performance as the number of objectives increases and become greater than 3. This paper proposes an adaptation of the metaheuristic Fish School Search to solve optimization problems with many objectives. This adaptation is based on the division of the candidate solutions in clusters that are specialized in solving a single-objective problem generated by the decomposition of the original problem. For this, we used concepts and ideas often employed by state-of-the-art algorithms, namely: (i) reference points and lines in the objectives space; (ii) clustering process; and (iii) the decomposition technique Penalty-based Boundary Intersection. The proposed algorithm was compared with two state-of-the-art bio-inspired algorithms. Moreover, a version of the proposed technique tailored to solve multi-modal problems was also presented. The experiments executed have shown that the performance obtained by both versions is competitive with state-of-the-art results.
Light in Power: A General and Parameter-free Algorithm for Caustic Design
Venue: arXiv cs.GR 2019
Year: 2019

We present in this paper a generic and parameter-free algorithm to efficiently build a wide variety of optical components, such as mirrors or lenses, that satisfy some light energy constraints. In all of our problems, one is given a collimated or point light source and a desired illumination after reflection or refraction and the goal is to design the geometry of a mirror or lens which transports exactly the light emitted by the source onto the target. We first propose a general framework and show that eight different optical component design problems amount to solving a light energy conservation equation that involves the computation of visibility diagrams. We then show that these diagrams all have the same structure and can be obtained by intersecting a 3D Power diagram with a planar or spherical domain. This allows us to propose an efficient and fully generic algorithm capable to solve these eight optical component design problems. The support of the prescribed target illumination can be a set of directions or a set of points located at a finite distance. Our solutions satisfy design constraints such as convexity or concavity. We show the effectiveness of our algorithm on simulated and fabricated examples.
Non-crossing paths with geographic constraints
Venue: arXiv cs.CG 2019
Year: 2019

A geographic network is a graph whose vertices are restricted to lie in a prescribed region in the plane. In this paper we begin to study the following fundamental problem for geographic networks: can a given geographic network be drawn without crossings? We focus on the seemingly simple setting where each region is a vertical segment, and one wants to connect pairs of segments with a path that lies inside the convex hull of the two segments. We prove that when paths must be drawn as straight line segments, it is NP-complete to determine if a crossing-free solution exists, even if all vertical segments have unit length. In contrast, we show that when paths must be monotone curves, the question can be answered in polynomial time. In the more general case of paths that can have any shape, we show that the problem is polynomial under certain assumptions.
Designing for Pragmatists and Fundamentalists: Privacy Concerns and Attitudes on the Internet of Things
Venue: arXiv cs.HC 2019
Year: 2019

Internet of Things (IoT) systems have aroused enthusiasm and concerns. Enthusiasm comes from their utilities in people daily life, and concerns may be associated with privacy issues. By using two IoT systems as case-studies, we examine users' privacy beliefs, concerns and attitudes. We focus on four major dimensions: the collection of personal data, the inference of new information, the exchange of information to third parties, and the risk-utility trade-off posed by the features of the system. Altogether, 113 Brazilian individuals answered a survey about such dimensions. Although their perceptions seem to be dependent on the context, there are recurrent patterns. Our results suggest that IoT users can be classified into unconcerned, fundamentalists and pragmatists. Most of them exhibit a pragmatist profile and believe in privacy as a right guaranteed by law. One of the most privacy concerning aspect is the exchange of personal information to third parties. Individuals' perceived risk is negatively correlated with their perceived utility in the features of the system. We discuss practical implications of these results and suggest heuristics to cope with privacy concerns when designing IoT systems.
Boltzmann machines for time-series
Venue: arXiv cs.NE 2019
Year: 2019

We review Boltzmann machines extended for time-series. These models often have recurrent structure, and back propagration through time (BPTT) is used to learn their parameters. The per-step computational complexity of BPTT in online learning, however, grows linearly with respect to the length of preceding time-series (i.e., learning rule is not local in time), which limits the applicability of BPTT in online learning. We then review dynamic Boltzmann machines (DyBMs), whose learning rule is local in time. DyBM's learning rule relates to spike-timing dependent plasticity (STDP), which has been postulated and experimentally confirmed for biological neural networks.
A Human-Checkable Four-Color Theorem Proof
Venue: arXiv cs.DM 2019
Year: 2019

This paper presents a short and simple proof of the Four-Color Theorem that can be utterly checkable by human mathematicians, without computer assistance. The new key idea that has allowed it and the global structure of the proof are presented in the Introduction.
Characterizing Distances of Networks on the Tensor Manifold
Venue: arXiv cs.SY 2019
Year: 2019

At the core of understanding dynamical systems is the ability to maintain and control the systems behavior that includes notions of robustness, heterogeneity, or regime-shift detection. Recently, to explore such functional properties, a convenient representation has been to model such dynamical systems as a weighted graph consisting of a finite, but very large number of interacting agents. This said, there exists very limited relevant statistical theory that is able cope with real-life data, i.e., how does perform analysis and/or statistics over a family of networks as opposed to a specific network or network-to-network variation. Here, we are interested in the analysis of network families whereby each network represents a point on an underlying statistical manifold. To do so, we explore the Riemannian structure of the tensor manifold developed by Pennec previously applied to Diffusion Tensor Imaging (DTI) towards the problem of network analysis. In particular, while this note focuses on Pennec definition of geodesics amongst a family of networks, we show how it lays the foundation for future work for developing measures of network robustness for regime-shift detection. We conclude with experiments highlighting the proposed distance on synthetic networks and an application towards biological (stem-cell) systems.
Plausibility and probability in deductive reasoning
Venue: arXiv cs.AI 2019
Year: 2019

We consider the problem of rational uncertainty about unproven mathematical statements, remarked on by Gödel and others. Using Bayesian-inspired arguments we build a normative model of fair bets under deductive uncertainty which draws from both probability and the theory of algorithms. We comment on connections to Zeilberger's notion of "semi-rigorous proofs", particularly that inherent subjectivity would be present. We also discuss a financial view with models of arbitrage where traders have limited computational resources.
NodeTrix Planarity Testing with Small Clusters
Venue: arXiv cs.DS 2019
Year: 2019

We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant $k$. We consider both the case when the sides of the matrices to which the edges are incident are fixed and the case when they can be chosen arbitrarily. We show that NodeTrix planarity testing with fixed sides can be solved in $O(k^{3k+\frac{3}{2}} \cdot n)$ time for every flat clustered graph that can be reduced to a partial 2-tree by collapsing its clusters into single vertices. In the general case, NodeTrix planarity testing with fixed sides can be solved in $O(n)$ time for $k = 2$, but it is NP-complete for any $k > 2$. NodeTrix planarity testing remains NP-complete also in the free sides model when $k > 4$.
Lombardi Drawings of Knots and Links
Venue: arXiv cs.CG 2019
Year: 2019

Knot and link diagrams are projections of one or more 3-dimensional simple closed curves into $R^2$, such that no more than two points project to the same point in $R^2$. These diagrams are drawings of 4-regular plane multigraphs. Knots are typically smooth curves in $R^3$, so their projections should be smooth curves in $R^2$ with good continuity and large crossing angles: exactly the properties of Lombardi graph drawings (defined by circular-arc edges and perfect angular resolution). We show that several knots do not allow plane Lombardi drawings. On the other hand, we identify a large class of 4-regular plane multigraphs that do have Lombardi drawings. We then study two relaxations of Lombardi drawings and show that every knot admits a plane 2-Lombardi drawing (where edges are composed of two circular arcs). Further, every knot is near-Lombardi, that is, it can be drawn as Lombardi drawing when relaxing the angular resolution requirement by an arbitrary small angular offset $\varepsilon$, while maintaining a $180^\circ$ angle between opposite edges.
Code Constructions for Physical Unclonable Functions and Biometric Secrecy Systems
Venue: arXiv cs.IT 2019
Year: 2019

The two-terminal key agreement problem with biometric or physical identifiers is considered. Two linear code constructions based on Wyner-Ziv coding are developed. The first construction uses random linear codes and achieves all points of the key-leakage-storage regions of the generated-secret and chosen-secret models. The second construction uses nested polar codes for vector quantization during enrollment and for error correction during reconstruction. Simulations show that the nested polar codes achieve privacy-leakage and storage rates that improve on existing code designs. One proposed code achieves a rate tuple that cannot be achieved by existing methods.
When Labels Fall Short: Property Graph Simulation via Blending of Network Structure and Vertex Attributes
Venue: arXiv cs.SI 2019
Year: 2019

Property graphs can be used to represent heterogeneous networks with labeled (attributed) vertices and edges. Given a property graph, simulating another graph with same or greater size with the same statistical properties with respect to the labels and connectivity is critical for privacy preservation and benchmarking purposes. In this work we tackle the problem of capturing the statistical dependence of the edge connectivity on the vertex labels and using the same distribution to regenerate property graphs of the same or expanded size in a scalable manner. However, accurate simulation becomes a challenge when the attributes do not completely explain the network structure. We propose the Property Graph Model (PGM) approach that uses a label augmentation strategy to mitigate the problem and preserve the vertex label and the edge connectivity distributions as well as their correlation, while also replicating the degree distribution. Our proposed algorithm is scalable with a linear complexity in the number of edges in the target graph. We illustrate the efficacy of the PGM approach in regenerating and expanding the datasets by leveraging two distinct illustrations. Our open-source implementation is available on GitHub.
Obstructions to a small hyperbolicity in Helly graphs
Venue: arXiv cs.DS 2019
Year: 2019

It is known that for every graph $G$ there exists the smallest Helly graph $\cal H(G)$ into which $G$ isometrically embeds ($\cal H(G)$ is called the injective hull of $G$) such that the hyperbolicity of $\cal H(G)$ is equal to the hyperbolicity of $G$. Motivated by this, we investigate structural properties of Helly graphs that govern their hyperbolicity and identify three isometric subgraphs of the King-grid as structural obstructions to a small hyperbolicity in Helly graphs.
On Low-Risk Heavy Hitters and Sparse Recovery Schemes
Venue: arXiv cs.DS 2019
Year: 2019

We study the heavy hitters and related sparse recovery problems in the low-failure probability regime. This regime is not well-understood, and has only been studied for non-adaptive schemes. The main previous work is one on sparse recovery by Gilbert et al.(ICALP'13). We recognize an error in their analysis, improve their results, and contribute new non-adaptive and adaptive sparse recovery algorithms, as well as provide upper and lower bounds for the heavy hitters problem with low failure probability.
Linear Precoding with Low-Resolution DACs for Massive MU-MIMO-OFDM Downlink
Venue: arXiv cs.IT 2019
Year: 2019

We consider the downlink of a massive multiuser (MU) multiple-input multiple-output (MIMO) system in which the base station (BS) is equipped with low-resolution digital-to-analog converters (DACs). In contrast to most existing results, we assume that the system operates over a frequency-selective wideband channel and uses orthogonal frequency division multiplexing (OFDM) to simplify equalization at the user equipments (UEs). Furthermore, we consider the practically relevant case of oversampling DACs. We theoretically analyze the uncoded bit error rate (BER) performance with linear precoders (e.g., zero forcing) and quadrature phase-shift keying using Bussgang's theorem. We also develop a lower bound on the information-theoretic sum-rate throughput achievable with Gaussian inputs, which can be evaluated in closed form for the case of 1-bit DACs. For the case of multi-bit DACs, we derive approximate, yet accurate, expressions for the distortion caused by low-precision DACs, which can be used to establish lower bounds on the corresponding sum-rate throughput. Our results demonstrate that, for a massive MU-MIMO-OFDM system with a 128-antenna BS serving 16 UEs, only 3--4 DAC bits are required to achieve an uncoded BER of 10^-4 with a negligible performance loss compared to the infinite-resolution case at the cost of additional out-of-band emissions. Furthermore, our results highlight the importance of taking into account the inherent spatial and temporal correlations caused by low-precision DACs.
Multi-Label Zero-Shot Human Action Recognition via Joint Latent Ranking Embedding
Venue: arXiv cs.CV 2019
Year: 2019

Human action recognition refers to automatic recognizing human actions from a video clip. In reality, there often exist multiple human actions in a video stream. Such a video stream is often weakly-annotated with a set of relevant human action labels at a global level rather than assigning each label to a specific video episode corresponding to a single action, which leads to a multi-label learning problem. Furthermore, there are many meaningful human actions in reality but it would be extremely difficult to collect/annotate video clips regarding all of various human actions, which leads to a zero-shot learning scenario. To the best of our knowledge, there is no work that has addressed all the above issues together in human action recognition. In this paper, we formulate a real-world human action recognition task as a multi-label zero-shot learning problem and propose a framework to tackle this problem in a holistic way. Our framework holistically tackles the issue of unknown temporal boundaries between different actions for multi-label learning and exploits the side information regarding the semantic relationship between different human actions for knowledge transfer. Consequently, our framework leads to a joint latent ranking embedding for multi-label zero-shot human action recognition. A novel neural architecture of two component models and an alternate learning algorithm are proposed to carry out the joint latent ranking embedding learning. Thus, multi-label zero-shot recognition is done by measuring relatedness scores of action labels to a test video clip in the joint latent visual and semantic embedding spaces. We evaluate our framework with different settings, including a novel data split scheme designed especially for evaluating multi-label zero-shot learning, on two datasets: Breakfast and Charades. The experimental results demonstrate the effectiveness of our framework.
Canonical Models and the Complexity of Modal Team Logic
Venue: arXiv cs.LO 2019
Year: 2019

We study modal team logic MTL, the team-semantical extension of modal logic ML closed under Boolean negation. Its fragments, such as modal dependence, independence, and inclusion logic, are well-understood. However, due to the unrestricted Boolean negation, the satisfiability problem of full MTL has been notoriously resistant to a complexity theoretical classification. In our approach, we introduce the notion of canonical models into the team-semantical setting. By construction of such a model, we reduce the satisfiability problem of MTL to simple model checking. Afterwards, we show that this approach is optimal in the sense that MTL-formulas can efficiently enforce canonicity. Furthermore, to capture these results in terms of complexity, we introduce a non-elementary complexity class, TOWER(poly), and prove that it contains satisfiability and validity of MTL as complete problems. We also prove that the fragments of MTL with bounded modal depth are complete for the levels of the elementary hierarchy (with polynomially many alternations). The respective hardness results hold for both strict or lax semantics of the modal operators and the splitting disjunction, and also over the class of reflexive and transitive frames.
Learning Sampling Distributions for Robot Motion Planning
Venue: arXiv cs.RO 2019
Year: 2019

A defining feature of sampling-based motion planning is the reliance on an implicit representation of the state space, which is enabled by a set of probing samples. Traditionally, these samples are drawn either probabilistically or deterministically to uniformly cover the state space. Yet, the motion of many robotic systems is often restricted to "small" regions of the state space, due to, for example, differential constraints or collision-avoidance constraints. To accelerate the planning process, it is thus desirable to devise non-uniform sampling strategies that favor sampling in those regions where an optimal solution might lie. This paper proposes a methodology for non-uniform sampling, whereby a sampling distribution is learned from demonstrations, and then used to bias sampling. The sampling distribution is computed through a conditional variational autoencoder, allowing sample generation from the latent space conditioned on the specific planning problem. This methodology is general, can be used in combination with any sampling-based planner, and can effectively exploit the underlying structure of a planning problem while maintaining the theoretical guarantees of sampling-based approaches. Specifically, on several planning problems, the proposed methodology is shown to effectively learn representations for the relevant regions of the state space, resulting in an order of magnitude improvement in terms of success rate and convergence to the optimal cost.
Deep Reinforcement Learning that Matters
Venue: arXiv cs.LG 2019
Year: 2019

In recent years, significant progress has been made in solving challenging problems across various domains using deep reinforcement learning (RL). Reproducing existing work and accurately judging the improvements offered by novel methods is vital to sustaining this progress. Unfortunately, reproducing results for state-of-the-art deep RL methods is seldom straightforward. In particular, non-determinism in standard benchmark environments, combined with variance intrinsic to the methods, can make reported results tough to interpret. Without significance metrics and tighter standardization of experimental reporting, it is difficult to determine whether improvements over the prior state-of-the-art are meaningful. In this paper, we investigate challenges posed by reproducibility, proper experimental techniques, and reporting procedures. We illustrate the variability in reported metrics and results when comparing against common baselines and suggest guidelines to make future results in deep RL more reproducible. We aim to spur discussion about how to ensure continued progress in the field by minimizing wasted effort stemming from results that are non-reproducible and easily misinterpreted.
Max-Min Fair Resource Allocation in Millimetre-Wave Backhauls
Venue: arXiv cs.NI 2019
Year: 2019

5G mobile networks are expected to provide pervasive high speed wireless connectivity, to support increasingly resource intensive user applications. Network hyper-densification therefore becomes necessary, though connecting to the Internet tens of thousands of base stations is non-trivial, especially in urban scenarios where optical fibre is difficult and costly to deploy. The millimetre wave (mm-wave) spectrum is a promising candidate for inexpensive multi-Gbps wireless backhauling, but exploiting this band for effective multi-hop data communications is challenging. In particular, resource allocation and scheduling of very narrow transmission/ reception beams requires to overcome terminal deafness and link blockage problems, while managing fairness issues that arise when flows encounter dissimilar competition and traverse different numbers of links with heterogeneous quality. In this paper, we propose WiHaul, an airtime allocation and scheduling mechanism that overcomes these challenges specific to multi-hop mm-wave networks, guarantees max-min fairness among traffic flows, and ensures the overall available backhaul resources are fully utilised. We evaluate the proposed WiHaul scheme over a broad range of practical network conditions, and demonstrate up to 5 times individual throughput gains and a fivefold improvement in terms of measurable fairness, over recent mm-wave scheduling solutions.
SCube: A Tool for Segregation Discovery
Venue: arXiv cs.SI 2019
Year: 2019

Segregation is the separation of social groups in the physical or in the online world. Segregation discovery consists of finding contexts of segregation. In the modern digital society, discovering segregation is challenging, due to the large amount and the variety of social data. We present a tool in support of segregation discovery from relational and graph data. The SCube system builds on attributed graph clustering and frequent itemset mining. It offers to the analyst a multi-dimensional segregation data cube for exploratory data analysis. The demonstration first guides the audience through the relevant social science concepts. Then, it focuses on scenarios around case studies of gender occupational segregation. Two real and large datasets about the boards of directors of Italian and Estonian companies will be explored in search of segregation contexts. The architecture of the SCube system and its computational efficiency challenges and solutions are discussed.
An efficient clustering algorithm from the measure of local Gaussian distribution
Venue: arXiv cs.DB 2019
Year: 2019

In this paper, I will introduce a fast and novel clustering algorithm based on Gaussian distribution and it can guarantee the separation of each cluster centroid as a given parameter, $d_s$. The worst run time complexity of this algorithm is approximately $\sim$O$(T\times N \times \log(N))$ where $T$ is the iteration steps and $N$ is the number of features.