OpenRaiser/Intern-Atlas huggingface dataset:
Types from data: Making structured data first-class citizens in F#
Venue: arXiv cs.PL 2016
Year: 2016

Most modern applications interact with external services and access data in structured formats such as XML, JSON and CSV. Static type systems do not understand such formats, often making data access more cumbersome. Should we give up and leave the messy world of external data to dynamic typing and runtime checks? Of course, not! We present F# Data, a library that integrates external structured data into F#. As most real-world data does not come with an explicit schema, we develop a shape inference algorithm that infers a shape from representative sample documents. We then integrate the inferred shape into the F# type system using type providers. We formalize the process and prove a relative type soundness theorem. Our library significantly reduces the amount of data access code and it provides additional safety guarantees when contrasted with the widely used weakly typed techniques.
Approximation and Kernelization for Chordal Vertex Deletion
Venue: arXiv cs.DS 2016
Year: 2016

The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size, as well as poly(opt) approximation algorithm. The first result answers an open problem of Marx from 2006 [WG 2006, LNCS 4271, 37-48].
Consciousness is Pattern Recognition
Venue: arXiv cs.AI 2016
Year: 2016

This is a proof of the strong AI hypothesis, i.e. that machines can be conscious. It is a phenomenological proof that pattern-recognition and subjective consciousness are the same activity in different terms. Therefore, it proves that essential subjective processes of consciousness are computable, and identifies significant traits and requirements of a conscious system. Since Husserl, many philosophers have accepted that consciousness consists of memories of logical connections between an ego and external objects. These connections are called "intentions." Pattern recognition systems are achievable technical artifacts. The proof links this respected introspective philosophical theory of consciousness with technical art. The proof therefore endorses the strong AI hypothesis and may therefore also enable a theoretically-grounded form of artificial intelligence called a "synthetic intentionality," able to synthesize, generalize, select and repeat intentions. If the pattern recognition is reflexive, able to operate on the set of intentions, and flexible, with several methods of synthesizing intentions, an SI may be a particularly strong form of AI. Similarities and possible applications to several AI paradigms are discussed. The article then addresses some problems: The proof's limitations, reflexive cognition, Searles' Chinese room, and how an SI could "understand" "meanings" and "be creative."
Automatic 3D liver location and segmentation via convolutional neural networks and graph cut
Venue: arXiv cs.CV 2016
Year: 2016

Purpose Segmentation of the liver from abdominal computed tomography (CT) image is an essential step in some computer assisted clinical interventions, such as surgery planning for living donor liver transplant (LDLT), radiotherapy and volume measurement. In this work, we develop a deep learning algorithm with graph cut refinement to automatically segment liver in CT scans. Methods The proposed method consists of two main steps: (i) simultaneously liver detection and probabilistic segmentation using 3D convolutional neural networks (CNNs); (ii) accuracy refinement of initial segmentation with graph cut and the previously learned probability map. Results The proposed approach was validated on forty CT volumes taken from two public databases MICCAI-Sliver07 and 3Dircadb. For the MICCAI-Sliver07 test set, the calculated mean ratios of volumetric overlap error (VOE), relative volume difference (RVD), average symmetric surface distance (ASD), root mean square symmetric surface distance (RMSD) and maximum symmetric surface distance (MSD) are 5.9%, 2.7%, 0.91%, 1.88 mm, and 18.94 mm, respectively. In the case of 20 3Dircadb data, the calculated mean ratios of VOE, RVD, ASD, RMSD and MSD are 9.36%, 0.97%, 1.89%, 4.15 mm and 33.14 mm, respectively. Conclusion The proposed method is fully automatic without any user interaction. Quantitative results reveal that the proposed approach is efficient and accurate for hepatic volume estimation in a clinical setup. The high correlation between the automatic and manual references shows that the proposed method can be good enough to replace the time-consuming and non-reproducible manual segmentation method.
Tight Sum-of-Squares lower bounds for binary polynomial optimization problems
Venue: arXiv cs.CC 2016
Year: 2016

We give two results concerning the power of the Sum-of-Squares(SoS)/Lasserre hierarchy. For binary polynomial optimization problems of degree $2d$ and an odd number of variables $n$, we prove that $\frac{n+2d-1}{2}$ levels of the SoS/Lasserre hierarchy are necessary to provide the exact optimal value. This matches the recent upper bound result by Sakaue, Takeda, Kim and Ito. Additionally, we study a conjecture by Laurent, who considered the linear representation of a set with no integral points. She showed that the Sherali-Adams hierarchy requires $n$ levels to detect the empty integer hull, and conjectured that the SoS/Lasserre rank for the same problem is $n-1$. We disprove this conjecture and derive lower and upper bounds for the rank.
The Perspectives of Democratic Decision-Making in the Information Society
Venue: arXiv cs.CY 2016
Year: 2016

In order to structure the debate on the democratic potentials of digital information technology Hubertus Buchstein in 1996 created three ideal types, net optimism, net pessimism and net neutrality. In this study the viability of these positions is put under scrutiny from a current viewpoint.
Core congestion is inherent in hyperbolic networks
Venue: arXiv cs.DS 2016
Year: 2016

We investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network $G$ admits a core, thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by Narayan and Saniee, Physical Review E, 84 (2011) that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset $X$ of vertices of a $δ$-hyperbolic graph $G$ there exists a vertex $m$ of $G$ such that the disk $D(m,4 δ)$ of radius $4 δ$ centered at $m$ intercepts at least one half of the total flow between all pairs of vertices of $X$, where the flow between two vertices $x,y\in X$ is carried by geodesic (or quasi-geodesic) $(x,y)$-paths. A set $S$ intercepts the flow between two nodes $x$ and $y$ if $S$ intersect every shortest path between $x$ and $y$. Differently from what was conjectured by Jonckheere et al., we show that $m$ is not (and cannot be) the center of mass of $X$ but is a node close to the median of $X$ in the so-called injective hull of $X$. In case of non-uniform traffic between nodes of $X$ (in this case, the unit flow exists only between certain pairs of nodes of $X$ defined by a commodity graph $R$), we prove a primal-dual result showing that for any $ρ>5δ$ the size of a $ρ$-multi-core (i.e., the number of disks of radius $ρ$) intercepting all pairs of $R$ is upper bounded by the maximum number of pairwise $(ρ-3δ)$-apart pairs of $R$.
On Stability and Sojourn Time of Peer-to-Peer Queuing Systems
Venue: arXiv cs.PF 2016
Year: 2016

Recent development of peer-to-peer (P2P) services (e.g. streaming, file sharing, and storage) systems introduces a new type of queue systems that receive little attention before, where both job and server arrive and depart randomly. Current study on these models focuses on the stability condition, under exponential workload assumption. This paper extends existing result in two aspects. In the first part of the paper we relax the exponential workload assumption, and study the stability of systems with general workload distribution. The second part of the paper focuses on the job sojourn time. An upper bound and a lower bound for job sojourn time are investigated. We evaluate tightness of the bounds by numerical analysis.
A novel clustering algorithm for coverage a large scale in WSN
Venue: arXiv cs.NI 2016
Year: 2016

The applications require coverage of the whole monitored area for long periods of time. Clustering is a way to reduce communications, minimize energy consumption and organize messages among the cluster head and their members. The message exchange of communication and data transmission between the different sensor nodes must be minimized to keep and extended the lifetime of the network because of limited energy resources of the sensors. In this paper, we take into consideration the problem isolated nodes that are away from the cluster head (CH) and by consequence or CH is not within the reach from these nodes. To solve this problem, we propose O-LEACH (Orphan Low Energy Adaptive Clustering Hierarchy) a routing protocol that takes into account the orphan nodes. Indeed, a cluster member will be able to play the role of a gateway which allows the joining of orphan nodes. Our contribution is to election a cluster head that has enough energy for a better now to coordinate with these member nodes and maintain the full coverage for applications which requires of useful data for the entire area to be covered. The simulation results show that O-LEACH performs better than LEACH in terms of connectivity rate, energy, scalability and coverage.
Self-Modification of Policy and Utility Function in Rational Agents
Venue: arXiv cs.AI 2016
Year: 2016

Any agent that is part of the environment it interacts with and has versatile actuators (such as arms and fingers), will in principle have the ability to self-modify -- for example by changing its own source code. As we continue to create more and more intelligent agents, chances increase that they will learn about this ability. The question is: will they want to use it? For example, highly intelligent systems may find ways to change their goals to something more easily achievable, thereby `escaping' the control of their designers. In an important paper, Omohundro (2008) argued that goal preservation is a fundamental drive of any intelligent system, since a goal is more likely to be achieved if future versions of the agent strive towards the same goal. In this paper, we formalise this argument in general reinforcement learning, and explore situations where it fails. Our conclusion is that the self-modification possibility is harmless if and only if the value function of the agent anticipates the consequences of self-modifications and use the current utility function when evaluating the future.
A Hierarchical Emotion Regulated Sensorimotor Model: Case Studies
Venue: arXiv cs.RO 2016
Year: 2016

Inspired by the hierarchical cognitive architecture and the perception-action model (PAM), we propose that the internal status acts as a kind of common-coding representation which affects, mediates and even regulates the sensorimotor behaviours. These regulation can be depicted in the Bayesian framework, that is why cognitive agents are able to generate behaviours with subtle differences according to their emotion or recognize the emotion by perception. A novel recurrent neural network called recurrent neural network with parametric bias units (RNNPB) runs in three modes, constructing a two-level emotion regulated learning model, was further applied to testify this theory in two different cases.
Capacity of Three-Dimensional Erasure Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we introduce a large-scale three-dimensional (3D) erasure network, where $n$ wireless nodes are randomly distributed in a cuboid of $n^λ\times n^μ\times n^ν$ with $λ+μ+ν=1$ for $λ,μ,ν>0$, and completely characterize its capacity scaling laws. Two fundamental path-loss attenuation models (i.e., exponential and polynomial power-law models) are used to suitably model an erasure probability for packet transmission. Then, under the two erasure models, we introduce a routing protocol using percolation highway in 3D space, and then analyze its achievable throughput scaling laws. It is shown that, under the two erasure models, the aggregate throughput scaling $n^{\min\{1-λ,1-μ,1-ν\}}$ can be achieved in the 3D erasure network. This implies that the aggregate throughput scaling $n^{2/3}$ can be achieved in 3D cubic erasure networks while $\sqrt{n}$ can be achieved in two-dimensional (2D) square erasure networks. The gain comes from the fact that, compared to 2D space, more geographic diversity can be exploited via 3D space, which means that generating more simultaneous percolation highways is possible. In addition, cut-set upper bounds on the capacity scaling are derived to verify that the achievable scheme based on the 3D percolation highway is order-optimal within a polylogarithmic factor under certain practical operating regimes on the decay parameters.
Coordinated Initial Access in Millimetre Wave Standalone Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, a novel coordinated initial access (IA) scheme for clustered millimeter wave small cells (mmSCs) is proposed for the fifth generation mobile communication networks (5G). This solution is a method for efficient and fast initial access for ultra-dense millimeter wave standalone networks without presence of overlaid legacy networks operating on lower frequency. In contrast to the current full beam sweep scheme, where time consuming exhaustive searching is employed, the mmSCs within one cluster will perform the IA procedure in a coordinated manner based on the power delay profile (PDP) measurement reports shared with each other via the backhaul links and thereby avoiding the full beam sweep. The proposed scheme significantly reduces the initial access time, enhances the access robustness and reduces the cost and complexity of the mobile terminals.
Proposing A Symmetric Key Bit-Level Block Cipher
Venue: arXiv cs.CR 2016
Year: 2016

A novel bit level block cipher based symmetric key cryptographic technique using G.C.D is proposed in this research paper. Entire plain text file is read one character at a time and according to the binary representation of ASCII value of the characters, entire plain text file is divided into n number of 16 bit blocks. Then an agreed-upon symmetric key file is formed by dividing each 16 bit block into two 8 bit sub blocks and by using Greatest Common Divisor (G.C.D) operation among them. The key size is 40 times the number of 16 bit blocks present in the plain text file as each block produces a key of size 40 bits. The character corresponding to the G.C.D value for each block is stored in the cipher text file which is sent by the sender to the receiver along with the symmetric key file. From the symmetric key file and the cipher text file, the receiver by applying reverse procedure, gets back the original plain text file. This technique has several merits, some of them are formation of symmetric key file dynamically, achievement of 50% compression rate in the cipher text file, better security in terms of brute force attack and applicability of the technique for a large number of files of different size and type.
Learning Bounded Treewidth Bayesian Networks with Thousands of Variables
Venue: arXiv cs.AI 2016
Year: 2016

We present a method for learning treewidth-bounded Bayesian networks from data sets containing thousands of variables. Bounding the treewidth of a Bayesian greatly reduces the complexity of inferences. Yet, being a global property of the graph, it considerably increases the difficulty of the learning process. We propose a novel algorithm for this task, able to scale to large domains and large treewidths. Our novel approach consistently outperforms the state of the art on data sets with up to ten thousand variables.
On-the-fly Network Pruning for Object Detection
Venue: arXiv cs.CV 2016
Year: 2016

Object detection with deep neural networks is often performed by passing a few thousand candidate bounding boxes through a deep neural network for each image. These bounding boxes are highly correlated since they originate from the same image. In this paper we investigate how to exploit feature occurrence at the image scale to prune the neural network which is subsequently applied to all bounding boxes. We show that removing units which have near-zero activation in the image allows us to significantly reduce the number of parameters in the network. Results on the PASCAL 2007 Object Detection Challenge demonstrate that up to 40% of units in some fully-connected layers can be entirely eliminated with little change in the detection result.
An improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem
Venue: arXiv cs.CG 2016
Year: 2016

Given a set $S$ of $n$ disjoint line segments in $\mathbb{R}^{2}$, the visibility counting problem (VCP) is to preprocess $S$ such that the number of segments in $S$ visible from any query point $p$ can be computed quickly. This problem can trivially be solved in logarithmic query time using $O(n^{4})$ preprocessing time and space. Gudmundsson and Morin proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. They answer any query in $O_ε(n^{1-α})$ with $O_ε(n^{2+2α})$ of preprocessing time and space, where $α$ is a constant $0\leq α\leq 1$, $ε> 0$ is another constant that can be made arbitrarily small, and $O_ε(f(n))=O(f(n)n^ε)$. In this paper, we propose a randomized approximation algorithm for VCP with a tradeoff between the space and the query time. We will show that for an arbitrary constants $0\leq β\leq \frac{2}{3}$ and $0<δ<1$, the expected preprocessing time, the expected space, and the query time of our algorithm are $O(n^{4-3β}\log n)$, $O(n^{4-3β})$, and $O(\frac{1}{δ^3}n^β\log n)$, respectively. The algorithm computes the number of visible segments from $p$, or $m_p$, exactly if $m_p\leq \frac{1}{δ^3}n^β\log n$. Otherwise, it computes a $(1+δ)$-approximation $m'_p$ with the probability of at least $1-\frac{1}{\log n}$, where $m_p\leq m'_p\leq (1+δ)m_p$.
On the Lattice Distortion Problem
Venue: arXiv cs.DS 2016
Year: 2016

We introduce and study the \emph{Lattice Distortion Problem} (LDP). LDP asks how "similar" two lattices are. I.e., what is the minimal distortion of a linear bijection between the two lattices? LDP generalizes the Lattice Isomorphism Problem (the lattice analogue of Graph Isomorphism), which simply asks whether the minimal distortion is one. As our first contribution, we show that the distortion between any two lattices is approximated up to a $n^{O(\log n)}$ factor by a simple function of their successive minima. Our methods are constructive, allowing us to compute low-distortion mappings that are within a $2^{O(n \log \log n/\log n)}$ factor of optimal in polynomial time and within a $n^{O(\log n)}$ factor of optimal in singly exponential time. Our algorithms rely on a notion of basis reduction introduced by Seysen (Combinatorica 1993), which we show is intimately related to lattice distortion. Lastly, we show that LDP is NP-hard to approximate to within any constant factor (under randomized reductions), by a reduction from the Shortest Vector Problem.
Likelihood Analysis of Power Spectra and Generalized Moment Problems
Venue: arXiv cs.SY 2016
Year: 2016

We develop an approach to spectral estimation that has been advocated by Ferrante, Masiero and Pavon and, in the context of the scalar-valued covariance extension problem, by Enqvist and Karlsson. The aim is to determine the power spectrum that is consistent with given moments and minimizes the relative entropy between the probability law of the underlying Gaussian stochastic process to that of a prior. The approach is analogous to the framework of earlier work by Byrnes, Georgiou and Lindquist and can also be viewed as a generalization of the classical work by Burg and Jaynes on the maximum entropy method. In the present paper we present a new fast algorithm in the general case (i.e., for general Gaussian priors) and show that for priors with a specific structure the solution can be given in closed form.
Movie Description
Venue: arXiv cs.CV 2016
Year: 2016

Audio Description (AD) provides linguistic descriptions of movies and allows visually impaired people to follow a movie along with their peers. Such descriptions are by design mainly visual and thus naturally form an interesting data source for computer vision and computational linguistics. In this work we propose a novel dataset which contains transcribed ADs, which are temporally aligned to full length movies. In addition we also collected and aligned movie scripts used in prior work and compare the two sources of descriptions. In total the Large Scale Movie Description Challenge (LSMDC) contains a parallel corpus of 118,114 sentences and video clips from 202 movies. First we characterize the dataset by benchmarking different approaches for generating video descriptions. Comparing ADs to scripts, we find that ADs are indeed more visual and describe precisely what is shown rather than what should happen according to the scripts created prior to movie production. Furthermore, we present and compare the results of several teams who participated in a challenge organized in the context of the workshop "Describing and Understanding Video & The Large Scale Movie Description Challenge (LSMDC)", at ICCV 2015.
Mobility-Aware Caching for Content-Centric Wireless Networks: Modeling and Methodology
Venue: arXiv cs.IT 2016
Year: 2016

As mobile services are shifting from "connection-centric" communications to "content-centric" communications, content-centric wireless networking emerges as a promising paradigm to evolve the current network architecture. Caching popular content at the wireless edge, including base stations (BSs) and user terminals (UTs), provides an effective approach to alleviate the heavy burden on backhaul links, as well as lowering delays and deployment costs. In contrast to wired networks, a unique characteristic of content-centric wireless networks (CCWNs) is the mobility of mobile users. While it has rarely been considered by existing works in caching design, user mobility contains various helpful side information that can be exploited to improve caching efficiency at both BSs and UTs. In this paper, we present a general framework on mobility-aware caching in CCWNs. Key properties of user mobility patterns that are useful for content caching will be firstly identified, and then different design methodologies for mobility-aware caching will be proposed. Moreover, two design examples will be provided to illustrate the proposed framework in details, and interesting future research directions will be identified.
Kernel-based system identification from noisy and incomplete input-output data
Venue: arXiv cs.SY 2016
Year: 2016

In this contribution, we propose a kernel-based method for the identification of linear systems from noisy and incomplete input-output datasets. We model the impulse response of the system as a Gaussian process whose covariance matrix is given by the recently introduced stable spline kernel. We adopt an empirical Bayes approach to estimate the posterior distribution of the impulse response given the data. The noiseless and missing data samples, together with the kernel hyperparameters, are estimated maximizing the joint marginal likelihood of the input and output measurements. To compute the marginal-likelihood maximizer, we build a solution scheme based on the Expectation-Maximization method. Simulations on a benchmark dataset show the effectiveness of the method.