OpenRaiser/Intern-Atlas huggingface dataset:
The WDAqua ITN: Answering Questions using Web Data
Venue: arXiv cs.IR 2015
Year: 2015

WDAqua is a Marie Curie Innovative Training Network (ITN) and is funded under EU grant number 642795 and runs from January 2015 to December 2018. WDAqua aims at advancing the state of the art by intertwining training, research and innovation efforts, centered around one service: data-driven question answering. Question answering is immediately useful to a wide audience of end users, and we will demonstrate this in settings including e-commerce, public sector information, publishing and smart cities. Question answering also covers web science and data science broadly, leading to transferrable research results and to transferrable skills of the researchers who have finished our training programme. To ensure that our research improves question answering overall, every individual research project connects at least two of these steps. Intersectional secondments (within a consortium covering academia, research institutes and industrial research as well as network-wide workshops, R and D challenges and innovation projects further balance ground-breaking research and the needs of society and industry. Training-wise these offers equip early stage researchers with the expertise and transferable technical and non-technical skills that will allow them to pursue a successful career as an academic, decision maker, practitioner or entrepreneur.
A Generalization of Montucla's Rectangle-to-Rectangle Dissection to Higher Dimensions
Venue: arXiv cs.IT 2015
Year: 2015

Dissections of polytopes are a well-studied subject by geometers as well as recreational mathematicians. A recent application in coding theory arises from the problem of parameterizing binary vectors of constant Hamming weight which has been shown previously to be equivalent to the problem of dissecting a tetrahedron to a brick. Applications of dissections also arise in problems related to the construction of analog codes. Here we consider the rectangle-to-rectangle dissection due to Montucla. Montucla's dissection is first reinterpreted in terms of the Two Tile Theorem. Based on this, a cube-to-brick dissection is developed in $\mathbb{R}^n$. We present a linear time algorithm (in $n$) that computes the dissection, i.e. determines a point in the cube given a point in a specific realization of the brick. An application of this algorithm to a previously reported analog coding scheme is also discussed.
Deep Structured Models For Group Activity Recognition
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a deep neural-network-based hierarchical graphical model for individual and group activity recognition in surveillance scenes. Deep networks are used to recognize the actions of individual people in a scene. Next, a neural-network-based hierarchical graphical model refines the predicted labels for each class by considering dependencies between the classes. This refinement step mimics a message-passing step similar to inference in a probabilistic graphical model. We show that this approach can be effective in group activity recognition, with the deep graphical model improving recognition rates over baseline methods.
A Publicly Available Cross-Platform Lemmatizer for Bulgarian
Venue: arXiv cs.CL 2015
Year: 2015

Our dictionary-based lemmatizer for the Bulgarian language presented here is distributed as free software, publicly available to download and use under the GPL v3 license. The presented software is written entirely in Java and is distributed as a GATE plugin. To our best knowledge, at the time of writing this article, there are not any other free lemmatization tools specifically targeting the Bulgarian language. The presented lemmatizer is a work in progress and currently yields an accuracy of about 95% in comparison to the manually annotated corpus BulTreeBank-Morph, which contains 273933 tokens.
Contamination Estimation via Convex Relaxations
Venue: arXiv cs.IT 2015
Year: 2015

Identifying anomalies and contamination in datasets is important in a wide variety of settings. In this paper, we describe a new technique for estimating contamination in large, discrete valued datasets. Our approach considers the normal condition of the data to be specified by a model consisting of a set of distributions. Our key contribution is in our approach to contamination estimation. Specifically, we develop a technique that identifies the minimum number of data points that must be discarded (i.e., the level of contamination) from an empirical data set in order to match the model to within a specified goodness-of-fit, controlled by a p-value. Appealing to results from large deviations theory, we show a lower bound on the level of contamination is obtained by solving a series of convex programs. Theoretical results guarantee the bound converges at a rate of $O(\sqrt{\log(p)/p})$, where p is the size of the empirical data set.
One Breaker is Enough: Hidden Topology Attacks on Power Grids
Venue: arXiv cs.CR 2015
Year: 2015

A coordinated cyber-attack on grid meter readings and breaker statuses can lead to incorrect state estimation that can subsequently destabilize the grid. This paper studies cyber-attacks by an adversary that changes breaker statuses on transmission lines to affect the estimation of the grid topology. The adversary, however, is incapable of changing the value of any meter data and can only block recorded measurements on certain lines from being transmitted to the control center. The proposed framework, with limited resource requirements as compared to standard data attacks, thus extends the scope of cyber-attacks to grids secure from meter corruption. We discuss necessary and sufficient conditions for feasible attacks using a novel graph-coloring based analysis and show that an optimal attack requires breaker status change at only ONE transmission line. The potency of our attack regime is demonstrated through simulations on IEEE test cases.
Towards Scalable Visual Exploration of Very Large RDF Graphs
Venue: arXiv cs.HC 2015
Year: 2015

In this paper, we outline our work on developing a disk-based infrastructure for efficient visualization and graph exploration operations over very large graphs. The proposed platform, called graphVizdb, is based on a novel technique for indexing and storing the graph. Particularly, the graph layout is indexed with a spatial data structure, i.e., an R-tree, and stored in a database. In runtime, user operations are translated into efficient spatial operations (i.e., window queries) in the backend.
Deep Secure Encoding: An Application to Face Recognition
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we present Deep Secure Encoding: a framework for secure classification using deep neural networks, and apply it to the task of biometric template protection for faces. Using deep convolutional neural networks (CNNs), we learn a robust mapping of face classes to high entropy secure codes. These secure codes are then hashed using standard hash functions like SHA-256 to generate secure face templates. The efficacy of the approach is shown on two face databases, namely, CMU-PIE and Extended Yale B, where we achieve state of the art matching performance, along with cancelability and high security with no unrealistic assumptions. Furthermore, the scheme can work in both identification and verification modes.
Densest Subgraph in Dynamic Graph Streams
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we consider the problem of approximating the densest subgraph in the dynamic graph stream model. In this model of computation, the input graph is defined by an arbitrary sequence of edge insertions and deletions and the goal is to analyze properties of the resulting graph given memory that is sub-linear in the size of the stream. We present a single-pass algorithm that returns a $(1+ε)$ approximation of the maximum density with high probability; the algorithm uses $O(ε^{-2} n \polylog n)$ space, processes each stream update in $\polylog (n)$ time, and uses $\poly(n)$ post-processing time where $n$ is the number of nodes. The space used by our algorithm matches the lower bound of Bahmani et al.~(PVLDB 2012) up to a poly-logarithmic factor for constant $ε$. The best existing results for this problem were established recently by Bhattacharya et al.~(STOC 2015). They presented a $(2+ε)$ approximation algorithm using similar space and another algorithm that both processed each update and maintained a $(4+ε)$ approximation of the current maximum density in $\polylog (n)$ time per-update.
Graph drawings with one bend and few slopes
Venue: arXiv cs.CG 2015
Year: 2015

We consider drawings of graphs in the plane in which edges are represented by polygonal paths with at most one bend and the number of different slopes used by all segments of these paths is small. We prove that $\lceil\fracΔ{2}\rceil$ edge slopes suffice for outerplanar drawings of outerplanar graphs with maximum degree $Δ\geq 3$. This matches the obvious lower bound. We also show that $\lceil\fracΔ{2}\rceil+1$ edge slopes suffice for drawings of general graphs, improving on the previous bound of $Δ+1$. Furthermore, we improve previous upper bounds on the number of slopes needed for planar drawings of planar and bipartite planar graphs.
Self-Healing Protocols for Connectivity Maintenance in Unstructured Overlays
Venue: arXiv cs.DC 2015
Year: 2015

In this paper, we discuss on the use of self-organizing protocols to improve the reliability of dynamic Peer-to-Peer (P2P) overlay networks. Two similar approaches are studied, which are based on local knowledge of the nodes' 2nd neighborhood. The first scheme is a simple protocol requiring interactions among nodes and their direct neighbors. The second scheme adds a check on the Edge Clustering Coefficient (ECC), a local measure that allows determining edges connecting different clusters in the network. The performed simulation assessment evaluates these protocols over uniform networks, clustered networks and scale-free networks. Different failure modes are considered. Results demonstrate the effectiveness of the proposal.
Convex Risk Minimization and Conditional Probability Estimation
Venue: arXiv cs.LG 2015
Year: 2015

This paper proves, in very general settings, that convex risk minimization is a procedure to select a unique conditional probability model determined by the classification problem. Unlike most previous work, we give results that are general enough to include cases in which no minimum exists, as occurs typically, for instance, with standard boosting algorithms. Concretely, we first show that any sequence of predictors minimizing convex risk over the source distribution will converge to this unique model when the class of predictors is linear (but potentially of infinite dimension). Secondly, we show the same result holds for \emph{empirical} risk minimization whenever this class of predictors is finite dimensional, where the essential technical contribution is a norm-free generalization bound.
Linear Algorithm for Conservative Degenerate Pattern Matching
Venue: arXiv cs.DS 2015
Year: 2015

A degenerate symbol x* over an alphabet A is a non-empty subset of A, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of non-solid symbols is upper-bounded by a fixed positive constant k. We consider here the matching problem of conservative degenerate strings and present the first linear-time algorithm that can find, for given degenerate strings P* and T* of total length n containing k non-solid symbols in total, the occurrences of P* in T* in O(nk) time.
Asynchronous Communication over a Fading Channel and Additive Noise
Venue: arXiv cs.IT 2015
Year: 2015

In \cite{Chandar2008}, Chandar et al studied a problem of sequential frame synchronization for a frame transmitted randomly and uniformly among $A$ slots. For a discrete memory-less channel (DMC), they showed that the frame length $N$ must scale as $e^{α(Q)N}>A$ for the frame detection error to go to zero asymptotically with $A$. $α(Q)$ is the synchronization threshold and $Q$ is channel transition probability. We study the sequential frame synchronisation problem for a fading channel and additive noise and seek to characterise the effect of fading. For a discrete ON-OFF fading channel (with ON probability $p$) and additive noise (with channel transition probabilities $Q_n$), we characterise the synchronisation threshold of the composite channel $α(Q)$ and show that $α(Q)\leq p\,α(Q_n)$. We then characterize the synchronization threshold for Rayleigh fading and AWGN channel as a function of channel parameters. The asynchronous framework permits a trade-off between sync frame length, $N$, and channel, $Q$, to support asynchronism. This allows us to characterize the synchronization threshold with sync frame energy instead of sync frame length.
A Non-stationary Service Curve Model for Performance Analysis of Transient Phases
Venue: arXiv cs.NI 2015
Year: 2015

Steady-state solutions for a variety of relevant queueing systems are known today, e.g., from queueing theory, effective bandwidths, and network calculus. The behavior during transient phases, on the other hand, is understood to a much lesser extent as its analysis poses significant challenges. Considering the majority of short-lived flows, transient effects that have diverse causes, such as TCP slow start, sleep scheduling in wireless networks, or signalling in cellular networks, are, however, predominant. This paper contributes a general model of regenerative service processes to characterize the transient behavior of systems. The model leads to a notion of non-stationary service curves that can be conveniently integrated into the framework of the stochastic network calculus. We derive respective models of sleep scheduling and show the significant impact of transient phases on backlogs and delays. We also consider measurement methods that estimate the service of an unknown system from observations of selected probe traffic. We find that the prevailing rate scanning method does not recover the service during transient phases well. This limitation is fundamental as it is explained by the non-convexity of non-stationary service curves. A second key difficulty is proven to be due to the super-additivity of network service processes. We devise a novel two-phase probing technique that first determines a minimal pattern of probe traffic. This probe is used to obtain an accurate estimate of the unknown transient service.
Bounded Degree Approximations of Stochastic Networks
Venue: arXiv cs.IT 2015
Year: 2015

We propose algorithms to approximate directed information graphs. Directed information graphs are probabilistic graphical models that depict causal dependencies between stochastic processes in a network. The proposed algorithms identify optimal and near-optimal approximations in terms of Kullback-Leibler divergence. The user-chosen sparsity trades off the quality of the approximation against visual conciseness and computational tractability. One class of approximations contains graphs with specified in-degrees. Another class additionally requires that the graph is connected. For both classes, we propose algorithms to identify the optimal approximations and also near-optimal approximations, using a novel relaxation of submodularity. We also propose algorithms to identify the r-best approximations among these classes, enabling robust decision making.
Towards a unified query language for provenance and versioning
Venue: arXiv cs.DB 2015
Year: 2015

Organizations and teams collect and acquire data from various sources, such as social interactions, financial transactions, sensor data, and genome sequencers. Different teams in an organization as well as different data scientists within a team are interested in extracting a variety of insights which require combining and collaboratively analyzing datasets in diverse ways. DataHub is a system that aims to provide robust version control and provenance management for such a scenario. To be truly useful for collaborative data science, one also needs the ability to specify queries and analysis tasks over the versioning and the provenance information in a unified manner. In this paper, we present an initial design of our query language, called VQuel, that aims to support such unified querying over both types of information, as well as the intermediate and final results of analyses. We also discuss some of the key language design and implementation challenges moving forward.
Tree-structured composition in neural networks without tree-structured architectures
Venue: arXiv cs.CL 2015
Year: 2015

Tree-structured neural networks encode a particular tree geometry for a sentence in the network design. However, these models have at best only slightly outperformed simpler sequence-based models. We hypothesize that neural sequence models like LSTMs are in fact able to discover and implicitly use recursive compositional structure, at least for tasks with clear cues to that structure in the data. We demonstrate this possibility using an artificial data task for which recursive compositional structure is crucial, and find an LSTM-based sequence model can indeed learn to exploit the underlying tree structure. However, its performance consistently lags behind that of tree models, even on large training sets, suggesting that tree-structured models are more effective at exploiting recursive structure.
Resource Allocation for Mixed RF and Hybrid RF/FSO Relaying
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider a mixed RF and hybrid RF/FSO system where several mobile users transmit their data over an RF link to a relay node (e.g. a small cell base station) and the relay forwards the information to a destination (e.g. a macro cell base station) over a hybrid RF/FSO backhaul link. The relay and the destination employ multiple antennas for transmission and reception over the RF links while each mobile user has a single antenna. The RF links are full-duplex with respect to the FSO link and half-duplex with respect to each other, i.e., either the user-relay RF link or the relay-destination RF link is active. For this communication setup, we derive the optimal resource allocation policy for sharing the RF bandwidth resource between the RF links. Our numerical results show the effectiveness of the proposed communication architecture and resource allocation policy, and their superiority compared to existing schemes which employ only one type of backhaul link.
ASPMT(QS): Non-Monotonic Spatial Reasoning with Answer Set Programming Modulo Theories
Venue: arXiv cs.AI 2015
Year: 2015

The systematic modelling of \emph{dynamic spatial systems} [9] is a key requirement in a wide range of application areas such as comonsense cognitive robotics, computer-aided architecture design, dynamic geographic information systems. We present ASPMT(QS), a novel approach and fully-implemented prototype for non-monotonic spatial reasoning ---a crucial requirement within dynamic spatial systems-- based on Answer Set Programming Modulo Theories (ASPMT). ASPMT(QS) consists of a (qualitative) spatial representation module (QS) and a method for turning tight ASPMT instances into Sat Modulo Theories (SMT) instances in order to compute stable models by means of SMT solvers. We formalise and implement concepts of default spatial reasoning and spatial frame axioms using choice formulas. Spatial reasoning is performed by encoding spatial relations as systems of polynomial constraints, and solving via SMT with the theory of real nonlinear arithmetic. We empirically evaluate ASPMT(QS) in comparison with other prominent contemporary spatial reasoning systems. Our results show that ASPMT(QS) is the only existing system that is capable of reasoning about indirect spatial effects (i.e. addressing the ramification problem), and integrating geometric and qualitative spatial information within a non-monotonic spatial reasoning context.
Entropy Based Detection And Behavioral Analysis Of Hybrid Covert Channeling Secured Communication
Venue: arXiv cs.CR 2015
Year: 2015

Covert channels is a vital setup in the analysing the strength of security in a network.Covert Channel is illegitimate channelling over the secured channel and establishes a malicious conversation.The trapdoor set in such channels proliferates making covert channel sophisticated to detect their presence in network firewall.This is due to the intricate covert scheme that enables to build robust covert channel over the network.From an attacker's perspective this will ameliorate by placing multiple such trapdoors in different protocols in the rudimentary protocol stack. This leads to a unique scenario of Hybrid Covert Channel, where different covert channel trapdoors exist at the same instance of time in same layer of protocol stack. For detection agents to detect such event is complicated due to lack of knowledge over the different covert schemes. To improve the knowledge of the detection engine to detect the hybrid covert channel scenario it is required to explore all possible clandestine mediums used in the formation of such channels. This can be explored by different schemes available and their entropy impact on hybrid covert channel. The environment can be composed of resources and subject under at-tack and subject which have initiated the attack (attacker). The paper sets itself an objective to understand the different covert schemes and the attack scenario (modelling) and possibilities of covert mediums along with metric for detection.
Post-Reconstruction Deconvolution of PET Images by Total Generalized Variation Regularization
Venue: arXiv cs.CV 2015
Year: 2015

Improving the quality of positron emission tomography (PET) images, affected by low resolution and high level of noise, is a challenging task in nuclear medicine and radiotherapy. This work proposes a restoration method, achieved after tomographic reconstruction of the images and targeting clinical situations where raw data are often not accessible. Based on inverse problem methods, our contribution introduces the recently developed total generalized variation (TGV) norm to regularize PET image deconvolution. Moreover, we stabilize this procedure with additional image constraints such as positivity and photometry invariance. A criterion for updating and adjusting automatically the regularization parameter in case of Poisson noise is also presented. Experiments are conducted on both synthetic data and real patient images.
Semi-simplicial Types in Logic-enriched Homotopy Type Theory
Venue: arXiv cs.LO 2015
Year: 2015

The problem of defining Semi-Simplicial Types (SSTs) in Homotopy Type Theory (HoTT) has been recognized as important during the Year of Univalent Foundations at the Institute of Advanced Study. According to the interpretation of HoTT in Quillen model categories, SSTs are type-theoretic versions of Reedy fibrant semi-simplicial objects in a model category and simplicial and semi-simplicial objects play a crucial role in many constructions in homotopy theory and higher category theory. Attempts to define SSTs in HoTT lead to some difficulties such as the need of infinitary assumptions which are beyond HoTT with only non-strict equality types. Voevodsky proposed a definition of SSTs in Homotopy Type System (HTS), an extension of HoTT with non-fibrant types, including an extensional strict equality type. However, HTS does not have the desirable computational properties such as decidability of type checking and strong normalization. In this paper, we study a logic-enriched homotopy type theory, an alternative extension of HoTT with equational logic based on the idea of logic-enriched type theories. In contrast to Voevodskys HTS, all types in our system are fibrant and it can be implemented in existing proof assistants. We show how SSTs can be defined in our system and outline an implementation in the proof assistant Plastic.