OpenRaiser/Intern-Atlas huggingface dataset:
Recognizing Semantic Features in Faces using Deep Learning
Venue: arXiv cs.LG 2016
Year: 2016

The human face constantly conveys information, both consciously and subconsciously. However, as basic as it is for humans to visually interpret this information, it is quite a big challenge for machines. Conventional semantic facial feature recognition and analysis techniques are already in use and are based on physiological heuristics, but they suffer from lack of robustness and high computation time. This thesis aims to explore ways for machines to learn to interpret semantic information available in faces in an automated manner without requiring manual design of feature detectors, using the approach of Deep Learning. This thesis provides a study of the effects of various factors and hyper-parameters of deep neural networks in the process of determining an optimal network configuration for the task of semantic facial feature recognition. This thesis explores the effectiveness of the system to recognize the various semantic features (like emotions, age, gender, ethnicity etc.) present in faces. Furthermore, the relation between the effect of high-level concepts on low level features is explored through an analysis of the similarities in low-level descriptors of different semantic features. This thesis also demonstrates a novel idea of using a deep network to generate 3-D Active Appearance Models of faces from real-world 2-D images. For a more detailed report on this work, please see [arXiv:1512.00743v1].
Trending Chic: Analyzing the Influence of Social Media on Fashion Brands
Venue: arXiv cs.SI 2016
Year: 2016

Social media platforms are popular venues for fashion brand marketing and advertising. With the introduction of native advertising, users don't have to endure banner ads that hold very little saliency and are unattractive. Using images and subtle text overlays, even in a world of ever-depreciating attention span, brands can retain their audience and have a capacious creative potential. While an assortment of marketing strategies are conjectured, the subtle distinctions between various types of marketing strategies remain under-explored. This paper presents a qualitative analysis on the influence of social media platforms on different behaviors of fashion brand marketing. We employ both linguistic and computer vision techniques while comparing and contrasting strategic idiosyncrasies. We also analyze brand audience retention and social engagement hence providing suggestions in adapting advertising and marketing strategies over Twitter and Instagram.
(Literally) above the clouds: virtualizing the network over multiple clouds
Venue: arXiv cs.NI 2016
Year: 2016

Recent SDN-based solutions give cloud providers the opportunity to extend their "as-a-service" model with the offer of complete network virtualization. They provide tenants with the freedom to specify the network topologies and addressing schemes of their choosing, while guaranteeing the required level of isolation among them. These platforms, however, have been targeting the datacenter of a single cloud provider with full control over the infrastructure. This paper extends this concept further by supporting the creation of virtual networks that span across several datacenters, which may belong to distinct cloud providers, while including private facilities owned by the tenant. In order to achieve this, we introduce a new network layer above the existing cloud hypervisors, affording the necessary level of control over the communications while hiding the heterogeneity of the clouds. The benefits of this approach are various, such as enabling finer decisions on where to place the virtual machines (e.g., to fulfill legal requirements), avoiding single points of failure, and potentially decreasing costs. Although our focus in the paper is on architecture design, we also present experimental results of a first prototype of the proposed solution.
Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences
Venue: arXiv cs.CG 2016
Year: 2016

We give the first subquadratic-time approximation schemes for dynamic time warping (DTW) and edit distance (ED) of several natural families of point sequences in $\mathbb{R}^d$, for any fixed $d \ge 1$. In particular, our algorithms compute $(1+\varepsilon)$-approximations of DTW and ED in time near-linear for point sequences drawn from k-packed or k-bounded curves, and subquadratic for backbone sequences. Roughly speaking, a curve is $κ$-packed if the length of its intersection with any ball of radius $r$ is at most $κ\cdot r$, and a curve is $κ$-bounded if the sub-curve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for $d=1$. Our algorithms work by constructing a small set of rectangular regions that cover the entries of the dynamic programming table commonly used for these distance measures. The weights of entries inside each rectangle are roughly the same, so we are able to use efficient procedures to approximately compute the cheapest paths through these rectangles.
Knowledge Sharing in Coalitions
Venue: arXiv cs.AI 2016
Year: 2016

The aim of this paper is to investigate the interplay between knowledge shared by a group of agents and its coalition ability. We investigate this relation in the standard context of imperfect information concurrent game. We assume that whenever a set of agents form a coalition to achieve a goal, they share their knowledge before acting. Based on this assumption, we propose a new semantics for alternating-time temporal logic with imperfect information and perfect recall. It turns out that this semantics is sufficient to preserve all the desirable properties of coalition ability in traditional coalitional logics. Meanwhile, we investigate how knowledge sharing within a group of agents contributes to its coalitional ability through the interplay of epistemic and coalition modalities. This work provides a partial answer to the question: which kind of group knowledge is required for a group to achieve their goals in the context of imperfect information.
Hierarchy of persistence with respect to the length of action's disability
Venue: arXiv cs.LO 2016
Year: 2016

The notion of persistence, based on the rule "no action can disable another one" is one of the classical notions in concurrency theory. It is also one of the issues discussed in the Petri net theory. We recall two ways of generalization of this notion: the first is "no action can kill another one" (called l/l-persistence) and the second "no action can kill another enabled one" (called the delayed persistence, or shortly e/l-persistence). Afterwards we introduce a more precise notion, called e/l-k-persistence, in which one action disables another one for no longer than a specified number k of single sequential steps. Then we consider an infinite hie\-rarchy of such e/l-k persistencies. We prove that if an action is disabled, and not killed, by another one, it can not be postponed indefinitely. Afterwards, we investigate the set of markings in which two actions are enabled simultaneously, and also the set of reachable markings with that feature. We show that the minimum of the latter is finite and effectively computable. Finally we deal with decision problems about e/l-k persistencies. We show that all the kinds of e/l-k persistencies are decidable with respect to steps, markings and nets.
Discovering the Skyline of Web Databases
Venue: arXiv cs.DB 2016
Year: 2016

Many web databases are "hidden" behind proprietary search interfaces that enforce the top-$k$ output constraint, i.e., each query returns at most $k$ of all matching tuples, preferentially selected and returned according to a proprietary ranking function. In this paper, we initiate research into the novel problem of skyline discovery over top-$k$ hidden web databases. Since skyline tuples provide critical insights into the database and include the top-ranked tuple for every possible ranking function following the monotonic order of attribute values, skyline discovery from a hidden web database can enable a wide variety of innovative third-party applications over one or multiple web databases. Our research in the paper shows that the critical factor affecting the cost of skyline discovery is the type of search interface controls provided by the website. As such, we develop efficient algorithms for three most popular types, i.e., one-ended range, free range and point predicates, and then combine them to support web databases that feature a mixture of these types. Rigorous theoretical analysis and extensive real-world online and offline experiments demonstrate the effectiveness of our proposed techniques and their superiority over baseline solutions.
Cloud Radio Access Networks with Coded Caching
Venue: arXiv cs.IT 2016
Year: 2016

A cloud radio access network (C-RAN) is considered as a candidate to meet the expectations of higher data rate de- mands in wireless networks. In C-RAN, low energy base stations (BSs) are deployed over a small geography and are allowed to connect to the cloud via finite capacity backhaul links where the information is processed. A conventional C-RAN, however, requires high capacity backhaul links, since the requested files need to be transferred first from the cloud to the BS before conveying them to the users. One approach to overcome the limitations of the backhaul links is to introduce local storage caches at the BSs, in which the popular files are stored locally in order to reduce the load of the backhaul links. Furthermore, we utilize coded caching with the goal to minimize the total network cost, i.e., the transmit power and the cost associated with the backhaul links. The initial formulation of the optimization problem for this model is non-convex. We first reformulate and then convexify the problem through some relaxation techniques. In comparison to the uncoded caching at the BSs, our results highlight the benefits associated with coded caching and show that it decreases the backhaul cost.
Nonuniformly weighted Schwarz smoothers for spectral element multigrid
Venue: arXiv cs.NA 2016
Year: 2016

A hybrid Schwarz/multigrid method for spectral element solvers to the Poisson equation in $\mathbb R^2$ is presented. It extends the additive Schwarz method studied by J. Lottes and P. Fischer (J. Sci. Comput. 24:45--78, 2005) by introducing nonuniform weight distributions based on the smoothed sign function. Using a V-cycle with only one pre-smoothing, the new method attains logarithmic convergence rates in the range from 1.2 to 1.9, which corresponds to residual reductions of almost two orders of magnitude. Compared to the original method, it reduces the iteration count by a factor of 1.5 to 3, leading to runtime savings of about 50 percent. In numerical experiments the method proved robust with respect to the mesh size and polynomial orders up to 32. Used as a preconditioner for the (inexact) CG method it is also suited for anisotropic meshes and easily extended to diffusion problems with variable coefficients.
Hankel Matrices for Weighted Visibly Pushdown Automata
Venue: arXiv cs.FL 2016
Year: 2016

Hankel matrices (aka connection matrices) of word functions and graph parameters have wide applications in automata theory, graph theory, and machine learning. We give a characterization of real-valued functions on nested words recognized by weighted visibly pushdown automata in terms of Hankel matrices on nested words. This complements C. Mathissen's characterization in terms of weighted monadic second order logic.
Impact of 4D channel distribution on the achievable rates in coherent optical communication experiments
Venue: arXiv cs.IT 2016
Year: 2016

We experimentally investigate mutual information and generalized mutual information for coherent optical transmission systems. The impact of the assumed channel distribution on the achievable rate is investigated for distributions in up to four dimensions. Single channel and wavelength division multiplexing (WDM) transmission over transmission links with and without inline dispersion compensation are studied. We show that for conventional WDM systems without inline dispersion compensation, a circularly symmetric complex Gaussian distribution is a good approximation of the channel. For other channels, such as with inline dispersion compensation, this is no longer true and gains in the achievable information rate are obtained by considering more sophisticated four-dimensional (4D) distributions. We also show that for nonlinear channels, gains in the achievable information rate can also be achieved by estimating the mean values of the received constellation in four dimensions. The highest gain for such channels is seen for a 4D correlated Gaussian distribution.
Maximum Scatter TSP in Doubling Metrics
Venue: arXiv cs.DS 2016
Year: 2016

We study the problem of finding a tour of $n$ points in which every edge is long. More precisely, we wish to find a tour that visits every point exactly once, maximizing the length of the shortest edge in the tour. The problem is known as Maximum Scatter TSP, and was introduced by Arkin et al. (SODA 1997), motivated by applications in manufacturing and medical imaging. Arkin et al. gave a $0.5$-approximation for the metric version of the problem and showed that this is the best possible ratio achievable in polynomial time (assuming $P \neq NP$). Arkin et al. raised the question of whether a better approximation ratio can be obtained in the Euclidean plane. We answer this question in the affirmative in a more general setting, by giving a $(1-ε)$-approximation algorithm for $d$-dimensional doubling metrics, with running time $\tilde{O}\big(n^3 + 2^{O(K \log K)}\big)$, where $K \leq \left( \frac{13}ε \right)^d$. As a corollary we obtain (i) an efficient polynomial-time approximation scheme (EPTAS) for all constant dimensions $d$, (ii) a polynomial-time approximation scheme (PTAS) for dimension $d = \log\log{n}/c$, for a sufficiently large constant $c$, and (iii) a PTAS for constant $d$ and $ε= Ω(1/\log\log{n})$. Furthermore, we show the dependence on $d$ in our approximation scheme to be essentially optimal, unless Satisfiability can be solved in subexponential time.
Comparing representations for function spaces in computable analysis
Venue: arXiv cs.LO 2016
Year: 2016

This paper compares different representations (in the sense of computable analysis) of a number of function spaces that are of interest in analysis. In particular subspace representations inherited from a larger function space are compared to more natural representations for these spaces. The formal framework for the comparisons is provided by Weihrauch reducibility. The centrepiece of the paper considers several representations of the analytic functions on the unit disk and their mutual translations. All translations that are not already computable are shown to be Weihrauch equivalent to closed choice on the natural numbers. Subsequently some similar considerations are carried out for representations of polynomials. In this case in addition to closed choice the Weihrauch degree LPO* shows up as the difficulty of finding the degree or the zeros. As a final example, the smooth functions are contrasted with functions with bounded support and Schwartz functions. Here closed choice on the natural numbers and the lim degree appear.
Graph Isomorphism in Quasipolynomial Time
Venue: arXiv cs.DS 2016
Year: 2016

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial ($\exp((\log n)^{O(1)})$) time. The best previous bound for GI was $\exp(O(\sqrt{n\log n}))$, where $n$ is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, $\exp(\tilde{O}(\sqrt{n}))$, where $n$ is the size of the permutation domain (Babai, 1983). The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic "local certificates" and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. Luks's barrier situation is characterized by a homomorphism ϕ that maps a given permutation group $G$ onto $S_k$ or $A_k$, the symmetric or alternating group of degree $k$, where $k$ is not too small. We say that an element $x$ in the permutation domain on which $G$ acts is affected by ϕ if the ϕ-image of the stabilizer of $x$ does not contain $A_k$. The affected/unaffected dichotomy underlies the core "local certificates" routine and is the central divide-and-conquer tool of the algorithm.
Learning the Correction for Multi-Path Deviations in Time-of-Flight Cameras
Venue: arXiv cs.CV 2016
Year: 2016

The Multipath effect in Time-of-Flight(ToF) cameras still remains to be a challenging problem that hinders further processing of 3D data information. Based on the evidence from previous literature, we explored the possibility of using machine learning techniques to correct this effect. Firstly, we created two new datasets of of ToF images rendered via ToF simulator of LuxRender. These two datasets contain corners in multiple orientations and with different material properties. We chose scenes with corners as multipath effects are most pronounced in corners. Secondly, we used this dataset to construct a learning model to predict real valued corrections to the ToF data using Random Forests. We found out that in our smaller dataset we were able to predict real valued correction and improve the quality of depth images significantly by removing multipath bias. With our algorithm, we improved relative per-pixel error from average value of 19% to 3%. Additionally, variance of the error was lowered by an order of magnitude.
Maximizing Influence in Social Networks: A Two-Stage Stochastic Programming Approach That Exploits Submodularity
Venue: arXiv cs.SI 2016
Year: 2016

We consider stochastic influence maximization problems arising in social networks. In contrast to existing studies that involve greedy approximation algorithms with a 63% performance guarantee, our work focuses on solving the problem optimally. To this end, we introduce a new class of problems that we refer to as two-stage stochastic submodular optimization models. We propose a delayed constraint generation algorithm to find the optimal solution to this class of problems with a finite number of samples. The influence maximization problems of interest are special cases of this general problem class. We show that the submodularity of the influence function can be exploited to develop strong optimality cuts that are more effective than the standard optimality cuts available in the literature. Finally, we report our computational experiments with large-scale real-world datasets for two fundamental influence maximization problems, independent cascade and linear threshold, and show that our proposed algorithm outperforms the greedy algorithm.
Bribeproof mechanisms for two-values domains
Venue: arXiv cs.GT 2016
Year: 2016

Schummer (Journal of Economic Theory 2000) introduced the concept of bribeproof mechanism which, in a context where monetary transfer between agents is possible, requires that manipulations through bribes are ruled out. Unfortunately, in many domains, the only bribeproof mechanisms are the trivial ones which return a fixed outcome. This work presents one of the few constructions of non-trivial bribeproof mechanisms for these quasi-linear environments. Though the suggested construction applies to rather restricted domains, the results obtained are tight: For several natural problems, the method yields the only possible bribeproof mechanism and no such mechanism is possible on more general domains.
Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
Venue: arXiv cs.ET 2016
Year: 2016

We introduce a class of digital machines we name Digital Memcomputing Machines (DMMs) able to solve a wide range of problems including Non-deterministic Polynomial (NP) ones with polynomial resources (in time, space and energy). An abstract DMM with this power must satisfy a set of compatible mathematical constraints underlying its practical realization. We initially prove this by introducing the complexity classes for these machines. We then make a connection with dynamical systems theory. This leads to the set of physical constraints for poly-resource resolvability. Once the mathematical requirements have been assessed, we propose a practical scheme to solve the above class of problems based on the novel concept of self-organizing logic gates and circuits (SOLCs). These are logic gates and circuits able to accept input signals from any terminal, without distinction between conventional input and output terminals. They can solve boolean problems by self-organizing into their solution. They can be fabricated either with circuit elements with memory (such as memristors) and/or standard MOS technology. Using tools of functional analysis, we prove mathematically the following constraints for the poly-resource resolvability: i) SOLCs possess a global attractor; ii) their only equilibrium points are the solutions of the problems to solve; iii) the system converges exponentially fast to the solutions; iv) the equilibrium convergence rate scales at most polynomially with input size. We finally provide arguments that periodic orbits and strange attractors cannot coexist with equilibria. As examples we show how to solve the prime factorization and the NP-hard version of the subset-sum problem. Since DMMs map integers into integers they are robust against noise, and hence scalable. We finally discuss the implications of the DMM realization through SOLCs to the NP=P question related to...
On Gaussian Channels with Feedback under Expected Power Constraints and with Non-Vanishing Error Probabilities
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider single- and multi-user Gaussian channels with feedback under expected power constraints and with non-vanishing error probabilities. In the first of two contributions, we study asymptotic expansions for the additive white Gaussian noise (AWGN) channel with feedback under the average error probability formalism. By drawing ideas from Gallager and Nakiboğlu's work for the direct part and the meta-converse for the converse part, we establish the $\varepsilon$-capacity and show that it depends on $\varepsilon$ in general and so the strong converse fails to hold. Furthermore, we provide bounds on the second-order term in the asymptotic expansion. We show that for any positive integer $L$, the second-order term is bounded between a term proportional to $-\ln_{(L)} n$ (where $\ln_{(L)}(\cdot)$ is the $L$-fold nested logarithm function) and a term proportional to $+\sqrt{n\ln n}$ where $n$ is the blocklength. The lower bound on the second-order term shows that feedback does provide an improvement in the maximal achievable rate over the case where no feedback is available. In our second contribution, we establish the $\varepsilon$-capacity region for the AWGN multiple access channel (MAC) with feedback under the expected power constraint by combining ideas from hypothesis testing, information spectrum analysis, Ozarow's coding scheme, and power control.