OpenRaiser/Intern-Atlas huggingface dataset:
Pairwise Constraint Propagation on Multi-View Data
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a graph-based learning approach to pairwise constraint propagation on multi-view data. Although pairwise constraint propagation has been studied extensively, pairwise constraints are usually defined over pairs of data points from a single view, i.e., only intra-view constraint propagation is considered for multi-view tasks. In fact, very little attention has been paid to inter-view constraint propagation, which is more challenging since pairwise constraints are now defined over pairs of data points from different views. In this paper, we propose to decompose the challenging inter-view constraint propagation problem into semi-supervised learning subproblems so that they can be efficiently solved based on graph-based label propagation. To the best of our knowledge, this is the first attempt to give an efficient solution to inter-view constraint propagation from a semi-supervised learning viewpoint. Moreover, since graph-based label propagation has been adopted for basic optimization, we develop two constrained graph construction methods for interview constraint propagation, which only differ in how the intra-view pairwise constraints are exploited. The experimental results in cross-view retrieval have shown the promising performance of our inter-view constraint propagation.
The cost of attack in competing networks
Venue: arXiv cs.SI 2015
Year: 2015

Real-world attacks can be interpreted as the result of competitive interactions between networks, ranging from predator-prey networks to networks of countries under economic sanctions. Although the purpose of an attack is to damage a target network, it also curtails the ability of the attacker, which must choose the duration and magnitude of an attack to avoid negative impacts on its own functioning. Nevertheless, despite the large number of studies on interconnected networks, the consequences of initiating an attack have never been studied. Here, we address this issue by introducing a model of network competition where a resilient network is willing to partially weaken its own resilience in order to more severely damage a less resilient competitor. The attacking network can take over the competitor nodes after their long inactivity. However, due to a feedback mechanism the takeovers weaken the resilience of the attacking network. We define a conservation law that relates the feedback mechanism to the resilience dynamics for two competing networks. Within this formalism, we determine the cost and optimal duration of an attack, allowing a network to evaluate the risk of initiating hostilities.
Bayesian Hypothesis Test using Nonparametric Belief Propagation for Noisy Sparse Recovery
Venue: arXiv cs.IT 2015
Year: 2015

This paper proposes a low-computational Bayesian algorithm for noisy sparse recovery (NSR), called BHT-BP. In this framework, we consider an LDPC-like measurement matrices which has a tree-structured property, and additive white Gaussian noise. BHT-BP has a joint detection-and-estimation structure consisting of a sparse support detector and a nonzero estimator. The support detector is designed under the criterion of the minimum detection error probability using a nonparametric belief propagation (nBP) and composite binary hypothesis tests. The nonzeros are estimated in the sense of linear MMSE, where the support detection result is utilized. BHT-BP has its strength in noise robust support detection, effectively removing quantization errors caused by the uniform sampling-based nBP. Therefore, in the NSR problems, BHT-BP has advantages over CS-BP which is an existing nBP algorithm, being comparable to other recent CS solvers, in several aspects. In addition, we examine impact of the minimum nonzero value of sparse signals via BHT-BP, on the basis of the results of the recent literature. Our empirical result shows that variation of x_min is reflected to recovery performance in the form of SNR shift.
Seeking Black Lining In Cloud
Venue: arXiv cs.CR 2015
Year: 2015

This work is focused on attacks on confidentiality that require time synchronization. This manuscript proposes a detection framework for covert channel perspective in cloud security. This problem is interpreted as a binary classification problem and the algorithm proposed is based on certain features that emerged after data analysis of Google cluster trace that forms base for analyzing attack free data. This approach can be generalized to study the flow of other systems and fault detection. The detection framework proposed does not make assumptions pertaining to data distribution as a whole making it suitable to meet cloud dynamism.
Robust Visual Tracking via Convolutional Networks
Venue: arXiv cs.CV 2015
Year: 2015

Deep networks have been successfully applied to visual tracking by learning a generic representation offline from numerous training images. However the offline training is time-consuming and the learned generic representation may be less discriminative for tracking specific objects. In this paper we present that, even without offline training with a large amount of auxiliary data, simple two-layer convolutional networks can be powerful enough to develop a robust representation for visual tracking. In the first frame, we employ the k-means algorithm to extract a set of normalized patches from the target region as fixed filters, which integrate a series of adaptive contextual filters surrounding the target to define a set of feature maps in the subsequent frames. These maps measure similarities between each filter and the useful local intensity patterns across the target, thereby encoding its local structural information. Furthermore, all the maps form together a global representation, which is built on mid-level features, thereby remaining close to image-level information, and hence the inner geometric layout of the target is also well preserved. A simple soft shrinkage method with an adaptive threshold is employed to de-noise the global representation, resulting in a robust sparse representation. The representation is updated via a simple and effective online strategy, allowing it to robustly adapt to target appearance variations. Our convolution networks have surprisingly lightweight structure, yet perform favorably against several state-of-the-art methods on the CVPR2013 tracking benchmark dataset with 50 challenging videos.
A Heuristic EDF Uplink Scheduler for Real Time Application in WiMAX Communication
Venue: arXiv cs.NI 2015
Year: 2015

WiMAX, Worldwide Interoperability for Microwave Access, is a developing wireless communication scheme that can provide broadband access to large-scale coverage. WiMAX belongs to the family of standards of IEEE-802.16. To satisfy user demands and support a new set of real time services and applications, a realistic and dynamic resource allocation algorithm is mandatory. One of the most efficient algorithm is EDF (earliest deadline first). But the problem is that when the difference between deadlines is large enough, then lower priority queues have to starve. So in this paper, we present a heuristic earliest deadline first (H-EDF) approach of the uplink scheduler of the WiMAX real time system. This H-EDF presents a way for efficient allocation of the bandwidth for uplink, so that bandwidth utilization is proper and appropriate fairness is provided to the system. We use Opnet simulator for implementing the WiMAX network, which uses this H-EDF scheduling algorithm. We will analysis the performance of the H-EDF algorithm in consideration with throughput as well as involvement of delay.
Stability of Influence Maximization
Venue: arXiv cs.SI 2015
Year: 2015

The present article serves as an erratum to our paper of the same title, which was presented and published in the KDD 2014 conference. In that article, we claimed falsely that the objective function defined in Section 1.4 is non-monotone submodular. We are deeply indebted to Debmalya Mandal, Jean Pouget-Abadie and Yaron Singer for bringing to our attention a counter-example to that claim. Subsequent to becoming aware of the counter-example, we have shown that the objective function is in fact NP-hard to approximate to within a factor of $O(n^{1-ε})$ for any $ε> 0$. In an attempt to fix the record, the present article combines the problem motivation, models, and experimental results sections from the original incorrect article with the new hardness result. We would like readers to only cite and use this version (which will remain an unpublished note) instead of the incorrect conference version.
Consid{é}rant la d{é}pendance dans la th{é}orie des fonctions de croyance
Venue: arXiv cs.AI 2015
Year: 2015

In this paper, we propose to learn sources independence in order to choose the appropriate type of combination rules when aggregating their beliefs. Some combination rules are used with the assumption of their sources independence whereas others combine beliefs of dependent sources. Therefore, the choice of the combination rule depends on the independence of sources involved in the combination. In this paper, we propose also a measure of independence, positive and negative dependence to integrate in mass functions before the combinaision with the independence assumption.
Belief Approach for Social Networks
Venue: arXiv cs.AI 2015
Year: 2015

Nowadays, social networks became essential in information exchange between individuals. Indeed, as users of these networks, we can send messages to other people according to the links connecting us. Moreover, given the large volume of exchanged messages, detecting the true nature of the received message becomes a challenge. For this purpose, it is interesting to consider this new tendency with reasoning under uncertainty by using the theory of belief functions. In this paper, we tried to model a social network as being a network of fusion of information and determine the true nature of the received message in a well-defined node by proposing a new model: the belief social network.
Big Data: How Geo-information Helped Shape the Future of Data Engineering
Venue: arXiv cs.DB 2015
Year: 2015

Very large data sets are the common rule in automated mapping, GIS, remote sensing, and what we can name geo-information. Indeed, in 1983 Landsat was already delivering gigabytes of data, and other sensors were in orbit or ready for launch, and a tantamount of cartographic data was being digitized. The retrospective paper revisits several issues that geo-information sciences had to face from the early stages on, including: structure ( to bring some structure to the data registered from a sampled signal, metadata); processing (huge amounts of data for big computers and fast algorithms); uncertainty (the kinds of errors, their quantification); consistency (when merging different sources of data is logically allowed, and meaningful); ontologies (clear and agreed shared definitions, if any kind of decision should be based upon them). All these issues are the background of Internet queries, and the underlying technology has been shaped during those years when geo-information engineering emerged.
Discrete Voronoi Games and $ε$-Nets, in Two and Three Dimensions
Venue: arXiv cs.CG 2015
Year: 2015

The one-round discrete Voronoi game, with respect to a $n$-point user set $U$, consists of two players Player 1 ($\mathcal{P}_1$) and Player 2 ($\mathcal{P}_2$). At first, $\mathcal{P}_1$ chooses a set of facilities $F_1$ following which $\mathcal{P}_2$ chooses another set of facilities $F_2$, disjoint from $F_1$. The payoff of $\mathcal{P}_2$ is defined as the cardinality of the set of points in $U$ which are closer to a facility in $F_2$ than to every facility in $F_1$, and the payoff of $\mathcal{P}_1$ is the difference between the number of users in $U$ and the payoff of $\mathcal{P}_2$. The objective of both the players in the game is to maximize their respective payoffs. In this paper we study the one-round discrete Voronoi game where $\mathcal{P}_1$ places $k$ facilities and $\mathcal{P}_2$ places one facility and we have denoted this game as $VG(k,1)$. Although the optimal solution of this game can be found in polynomial time, the polynomial has a very high degree. In this paper, we focus on achieving approximate solutions to $VG(k,1)$ with significantly better running times. We provide a constant-factor approximate solution to the optimal strategy of $\mathcal{P}_1$ in $VG(k,1)$ by establishing a connection between $VG(k,1)$ and weak $ε$-nets. To the best of our knowledge, this is the first time that Voronoi games are studied from the point of view of $ε$-nets.
AAPPeC: Agent-based Architecture for Privacy Payoff in eCommerce
Venue: arXiv cs.SE 2015
Year: 2015

With the rapid development of applications in open distributed environments such as eCommerce, privacy of information is becoming a critical issue. Today, many online companies are gathering information and have assembled sophisticated databases that know a great deal about many people, generally without the knowledge of those people. Such information changes hands or ownership as a normal part of eCommerce transactions, or through strategic decisions that often includes the sale of users' information to other firms. The key commercial value of users' personal information derives from the ability of firms to identify consumers and charge them personalized prices for goods and services they have previously used or may wish to use in the future. A look at present-day practices reveals that consumers' profile data is now considered as one of the most valuable assets owned by online businesses. In this thesis, we argue the following: if consumers' private data is such a valuable asset, should they not be entitled to commercially benefit from their asset as well? The scope of this thesis is on developing architecture for privacy payoff as a means of rewarding consumers for sharing their personal information with online businesses. The architecture is a multi-agent system in which several agents employ various requirements for personal information valuation and interaction capabilities that most users cannot do on their own. The agents in the system bear the responsibility of working on behalf of consumers to categorize their personal data objects, report to consumers on online businesses' trustworthiness and reputation, determine the value of their compensation using risk-based financial models, and, finally, negotiate for a payoff value in return for the dissemination of users' information.
Towards Gathering Robots with Limited View in Linear Time: The Closed Chain Case
Venue: arXiv cs.DC 2015
Year: 2015

In the gathering problem, n autonomous robots have to meet on a single point. We consider the gathering of a closed chain of point-shaped, anonymous robots on a grid. The robots only have local knowledge about a constant number of neighboring robots along the chain in both directions. Actions are performed in the fully synchronous time model FSYNC. Every robot has a limited memory that may contain one timestamp of the global clock, also visible to its direct neighbors. In this synchronous time model, there is no limited view gathering algorithm known to perform better than in quadratic runtime. The configurations that show the quadratic lower bound are closed chains. In this paper, we present the first sub-quadratic---in fact linear time---gathering algorithm for closed chains on a grid.
On Using Feedback in a Gaussian Channel
Venue: arXiv cs.IT 2015
Year: 2015

For information transmission a discrete time channel with independent additive Gaussian noise is used. There is also another channel with independent additive Gaussian noise (the feedback channel), and the transmitter observes without delay all outputs of the forward channel via that channel. Transmission of nonexponential number of messages is considered (i.e. transmission rate equals zero) and the achievable decoding error exponent for such a combination of channels is investigated. The transmission method strengthens the method used by authors earlier for BSC and Gaussian channels. In particular, for small feedback noise, it allows to gain 33.3\% (instead of 23.6\% earlier in the similar case of Gaussian channel).
A Categorical Semantics for Linear Logical Frameworks
Venue: arXiv cs.LO 2015
Year: 2015

A type theory is presented that combines (intuitionistic) linear types with type dependency, thus properly generalising both intuitionistic dependent type theory and full linear logic. A syntax and complete categorical semantics are developed, the latter in terms of (strict) indexed symmetric monoidal categories with comprehension. Various optional type formers are treated in a modular way. In particular, we will see that the historically much-debated multiplicative quantifiers and identity types arise naturally from categorical considerations. These new multiplicative connectives are further characterised by several identities relating them to the usual connectives from dependent type theory and linear logic. Finally, one important class of models, given by families with values in some symmetric monoidal category, is investigated in detail.
Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with $k$ blocks, for any $k$ fixed. Our algorithm works with graphs having constant edge density, under an optimal condition on the gap between the density inside a block and the density between the blocks. As a co-product, we settle an open question posed by Abbe et. al. concerning censor block models.
Better Answers to Real Questions
Venue: arXiv cs.SC 2015
Year: 2015

We consider existential problems over the reals. Extended quantifier elimination generalizes the concept of regular quantifier elimination by providing in addition answers, which are descriptions of possible assignments for the quantified variables. Implementations of extended quantifier elimination via virtual substitution have been successfully applied to various problems in science and engineering. So far, the answers produced by these implementations included infinitesimal and infinite numbers, which are hard to interpret in practice. We introduce here a post-processing procedure to convert, for fixed parameters, all answers into standard real numbers. The relevance of our procedure is demonstrated by application of our implementation to various examples from the literature, where it significantly improves the quality of the results.
An Isbell Duality Theorem for Type Refinement Systems
Venue: arXiv cs.LO 2015
Year: 2015

Any refinement system (= functor) has a fully faithful representation in the refinement system of presheaves, by interpreting types as relative slice categories, and refinement types as presheaves over those categories. Motivated by an analogy between side effects in programming and *context effects* in linear logic, we study logical aspects of this "positive" (covariant) representation, as well as of an associated "negative" (contravariant) representation. We establish several preservation properties for these representations, including a generalization of Day's embedding theorem for monoidal closed categories. Then we establish that the positive and negative representations satisfy an Isbell-style duality. As corollaries, we derive two different formulas for the positive representation of a pushforward (inspired by the classical negative translations of proof theory), which express it either as the dual of a pullback of a dual, or as the double dual of a pushforward. Besides explaining how these constructions on refinement systems generalize familiar category-theoretic ones (by viewing categories as special refinement systems), our main running examples involve representations of Hoare Logic and linear sequent calculus.
Artificial-Noise-Aided Secure Multi-Antenna Transmission with Limited Feedback
Venue: arXiv cs.IT 2015
Year: 2015

We present an optimized secure multi-antenna transmission approach based on artificial-noise-aided beamforming, with limited feedback from a desired single-antenna receiver. To deal with beamformer quantization errors as well as unknown eavesdropper channel characteristics, our approach is aimed at maximizing throughput under dual performance constraints - a connection outage constraint on the desired communication channel and a secrecy outage constraint to guard against eavesdropping. We propose an adaptive transmission strategy that judiciously selects the wiretap coding parameters, as well as the power allocation between the artificial noise and the information signal. This optimized solution reveals several important differences with respect to solutions designed previously under the assumption of perfect feedback. We also investigate the problem of how to most efficiently utilize the feedback bits. The simulation results indicate that a good design strategy is to use approximately 20% of these bits to quantize the channel gain information, with the remainder to quantize the channel direction, and this allocation is largely insensitive to the secrecy outage constraint imposed. In addition, we find that 8 feedback bits per transmit antenna is sufficient to achieve approximately 90% of the throughput attainable with perfect feedback.
QoE-Centric Localized Mobility Management for Future Mobile Networks
Venue: arXiv cs.NI 2015
Year: 2015

Mobility support in future networks will be predominately based on micro mobility protocols. Current proposed schemes such as Hierarchical Mobile IPv6 (HMIPv6) and more importantly Proxy Mobile IPv6 (PMIPv6) provide localized mobility support by electing a node within the network (topologically close to the Access Routers (AR)) to act as mobility anchor. Such schemes can significantly improve handover latency, as well as the end-to-end signalling overhead, but might entail scalability issues, which in some instances, do not fit adequately with the current explosion of mobile Internet traffic, and the evolutionary trend towards flat network architectures. The notion of using Distributed Mobility Management (DMM) allows for decentralization by anchoring nodes at their AR. The idea is that for sessions with duration less than the cell residence time efficient mobility can be supported. However, DMM might be highly suboptimal in instances where nodes perform multiple handovers during the session lifetime. Hence, one approach cannot be effective for all types of applications. In this paper a hybrid mobility management solution, integrated with a new routing scheme, is proposed. The scheme selects the most suitable mobility approach, centralized or distributed, by taking into account the flows' requirement, in terms of Quality of Experience (QoE), and new routing constraints. The results of optimization problem show that the proposed approach can achieve efficient resource utilisation, ease network congestion, and lead to a significant improvement in the QoE.
Foundational Extensible Corecursion
Venue: arXiv cs.PL 2015
Year: 2015

This paper presents a formalized framework for defining corecursive functions safely in a total setting, based on corecursion up-to and relational parametricity. The end product is a general corecursor that allows corecursive (and even recursive) calls under well-behaved operations, including constructors. Corecursive functions that are well behaved can be registered as such, thereby increasing the corecursor's expressiveness. The metatheory is formalized in the Isabelle proof assistant and forms the core of a prototype tool. The corecursor is derived from first principles, without requiring new axioms or extensions of the logic.