OpenRaiser/Intern-Atlas huggingface dataset:
Capacity Considerations for Secondary Networks in TV White Space
Venue: arXiv cs.NI 2013
Year: 2013

The so-called `TV white spaces' (TVWS) - representing unused TV channels in any given location as the result of the transition to digital broadcasting - designated by U.S. Federal Communications Commission (FCC) for unlicensed use presents significant new opportunities within the context of emerging 4G networks for developing new wireless access technologies that meet the goals of the US National Broadband Plan (notably true broadband access for an increasing fraction of the population). There are multiple challenges in realizing this goal; the most fundamental being the fact that the available WS capacity is currently not accurately known, since it depends on a multiplicity of factors - including system parameters of existing incumbents (broadcasters), propagation characteristics of local terrain as well as FCC rules. In this paper, we explore the capacity of white space networks by developing a detailed model that includes all the major variables, and is cognizant of FCC regulations that provide constraints on incumbent protection. Real terrain information and propagation models for the primary broadcaster and adjacent channel interference from TV transmitters are included to estimate their impact on achievable WS capacity. The model is later used to explore various trade-offs between network capacity and system parameters and suggest possible amendments to FCC's incumbent protection rules in the favor of furthering white space capacity.
Upgraded Approximation of Non-Binary Alphabets for Polar Code Construction
Venue: arXiv cs.IT 2013
Year: 2013

An algorithm is presented for approximating a single-user channel with a prime input alphabet size. The result is an upgraded version of the channel with a reduced output alphabet size. It is shown that this algorithm can be used to reduce the output alphabet size to the input alphabet size in most cases.
Multi-Resolution Video Streaming in Peer-to-peer Networks
Venue: arXiv cs.IT 2013
Year: 2013

We consider multi-resolution streaming in fully-connected peer-to-peer networks, where transmission rates are constrained by arbitrarily specified upload capacities of the source and peers. We fully characterize the capacity region of rate vectors achievable with arbitrary coding, where an achievable rate vector describes a vector of throughputs of the different resolutions that can be supported by the network. We then prove that all rate vectors in the capacity region can be achieved using pure routing strategies. This shows that coding has no capacity advantage over routing in this scenario.
Network Farthest-Point Diagrams
Venue: arXiv cs.CG 2013
Year: 2013

Consider the continuum of points along the edges of a network, i.e., an undirected graph with positive edge weights. We measure distance between these points in terms of the shortest path distance along the network, known as the network distance. Within this metric space, we study farthest points. We introduce network farthest-point diagrams, which capture how the farthest points---and the distance to them---change as we traverse the network. We preprocess a network G such that, when given a query point q on G, we can quickly determine the farthest point(s) from q in G as well as the farthest distance from q in G. Furthermore, we introduce a data structure supporting queries for the parts of the network that are farther away from q than some threshold R > 0, where R is part of the query. We also introduce the minimum eccentricity feed-link problem defined as follows. Given a network G with geometric edge weights and a point p that is not on G, connect p to a point q on G with a straight line segment pq, called a feed-link, such that the largest network distance from p to any point in the resulting network is minimized. We solve the minimum eccentricity feed-link problem using eccentricity diagrams. In addition, we provide a data structure for the query version, where the network G is fixed and a query consists of the point p.
Low Complexity MIMO Detection based on Belief Propagation over Pair-wise Graphs
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers belief propagation algorithm over pair-wise graphical models to develop low complexity, iterative multiple-input multiple-output (MIMO) detectors. The pair-wise graphical model is a bipartite graph where a pair of variable nodes are related by an observation node represented by the bivariate Gaussian function obtained by marginalizing the posterior joint probability density under the Gaussian input assumption. Specifically, we consider two types of pair-wise models, the fully connected and ring-type. The pair-wise graphs are sparse, compared to the conventional graphical model in [18], insofar as the number of edges connected to an observation node (edge degree) is only two. Consequently the computations are much easier than those of maximum likelihood (ML) detection, which are similar to the belief propagation (BP) that is run over the fully connected bipartite graph. The link level performance for non-Gaussian input is evaluated via simulations, and the results show the validity of the proposed algorithms. We also customize the algorithm with Gaussian input assumption to obtain the Gaussian BP run over the two pair-wise graphical models and, for the ring-type, we prove its convergence in mean to the linear minimum mean square error (MMSE) estimates. Since the maximum a posterior (MAP) estimator for Gaussian input is equivalent to the linear MMSE estimator, it shows the optimality, in mean, of the scheme for Gaussian input.
Facial transformations of ancient portraits: the face of Caesar
Venue: arXiv cs.CV 2013
Year: 2013

Some software solutions used to obtain the facial transformations can help investigating the artistic metamorphosis of the ancient portraits of the same person. An analysis with a freely available software of portraitures of Julius Caesar is proposed, showing his several "morphs". The software helps enhancing the mood the artist added to a portrait.
A Multi-Dimensional Block-Circulant Perfect Array Construction
Venue: arXiv cs.IT 2013
Year: 2013

We present a $N$-dimensional generalization of the two-dimensional block-circulant perfect array construction by \cite{Blake2013}. As in \cite{Blake2013}, the families of $N$-dimensional arrays possess pairwise \textit{good} zero correlation zone (ZCZ) cross-correlation. Both constructions use a perfect autocorrelation sequence with the array orthogonality property (AOP).
Simulation Analysis of Routing Protocols using Manhattan Grid Mobility Model in MANET
Venue: arXiv cs.NI 2013
Year: 2013

A Mobile Ad-hoc Network (MANET) is a self-configuring infrastructure less network of mobile devices connected by wireless links. In this network technology, simulative analysis is a significant method to understand the performance of routing protocols. In this paper three protocols AODV, DSDV and DSR were simulated using Manhattan Grid Mobility Model. The reactive (AODV, DSR) and proactive (DSDV) protocols internal mechanism leads to considerable performance difference. The performance differentials are analyzed using NS-2 which is the main network simulator, NAM (Network Animator), AWK (post processing script) and were compared in terms of Packet Delivery Fraction (PDF), Average end-to-end Delay and Throughput, in different environments specified by varying network load, mobility rate and number of nodes. Our results presented in this research work demonstrate the performance analysis of AODV, DSDV and DSR routing protocols. It has been observed that, under Manhattan Grid mobility model, AODV and DSR performs better than DSDV in terms of PDF and Throughput. However in term of Average end-to-end Delay, DSDV appears to be the best one.
Dynamic Amelioration of Resolution Mismatches for Local Feature Based Identity Inference
Venue: arXiv cs.CV 2013
Year: 2013

While existing face recognition systems based on local features are robust to issues such as misalignment, they can exhibit accuracy degradation when comparing images of differing resolutions. This is common in surveillance environments where a gallery of high resolution mugshots is compared to low resolution CCTV probe images, or where the size of a given image is not a reliable indicator of the underlying resolution (eg. poor optics). To alleviate this degradation, we propose a compensation framework which dynamically chooses the most appropriate face recognition system for a given pair of image resolutions. This framework applies a novel resolution detection method which does not rely on the size of the input images, but instead exploits the sensitivity of local features to resolution using a probabilistic multi-region histogram approach. Experiments on a resolution-modified version of the "Labeled Faces in the Wild" dataset show that the proposed resolution detector frontend obtains a 99% average accuracy in selecting the most appropriate face recognition system, resulting in higher overall face discrimination accuracy (across several resolutions) compared to the individual baseline face recognition systems.
Backward Path Growth for Efficient Mobile Sequential Recommendation
Venue: arXiv cs.DS 2013
Year: 2013

The problem of mobile sequential recommendation is presented to suggest a route connecting some pick-up points for a taxi driver so that he/she is more likely to get passengers with less travel cost. Essentially, a key challenge of this problem is its high computational complexity. In this paper, we propose a dynamical programming based method to solve this problem. Our method consists of two separate stages: an offline pre-processing stage and an online search stage. The offline stage pre-computes optimal potential sequence candidates from a set of pick-up points, and the online stage selects the optimal driving route based on the pre-computed sequences with the current position of an empty taxi. Specifically, for the offline pre-computation, a backward incremental sequence generation algorithm is proposed based on the iterative property of the cost function. Simultaneously, an incremental pruning policy is adopted in the process of sequence generation to reduce the search space of the potential sequences effectively. In addition, a batch pruning algorithm can also be applied to the generated potential sequences to remove the non-optimal ones of a certain length. Since the pruning effect continuously increases with the increase of the sequence length, our method can search the optimal driving route efficiently in the remaining potential sequence candidates. Experimental results on real and synthetic data sets show that the pruning percentage of our method is significantly improved compared to the state-of-the-art methods, which makes our method can be used to handle the problem of mobile sequential recommendation with more pick-up points and to search the optimal driving routes in arbitrary length ranges.
Modeling uncertain and vague knowledge in possibility and evidence theories
Venue: arXiv cs.AI 2013
Year: 2013

This paper advocates the usefulness of new theories of uncertainty for the purpose of modeling some facets of uncertain knowledge, especially vagueness, in AI. It can be viewed as a partial reply to Cheeseman's (among others) defense of probability.
A Representation of Uncertainty to Aid Insight into Decision Models
Venue: arXiv cs.AI 2013
Year: 2013

Many real world models can be characterized as weak, meaning that there is significant uncertainty in both the data input and inferences. This lack of determinism makes it especially difficult for users of computer decision aids to understand and have confidence in the models. This paper presents a representation for uncertainty and utilities that serves as a framework for graphical summary and computer-generated explanation of decision models. The application described that tests the methodology is a computer decision aid designed to enhance the clinician-patient consultation process for patients with angina (chest pain due to lack of blood flow to the heart muscle). The angina model is represented as a Bayesian decision network. Additionally, the probabilities and utilities are treated as random variables with probability distributions on their range of possible values. The initial distributions represent information on all patients with anginal symptoms, and the approach allows for rapid tailoring to more patientspecific distributions. This framework provides a metric for judging the importance of each variable in the model dynamically.
A Comparison of Decision Analysis and Expert Rules for Sequential Diagnosis
Venue: arXiv cs.AI 2013
Year: 2013

There has long been debate about the relative merits of decision theoretic methods and heuristic rule-based approaches for reasoning under uncertainty. We report an experimental comparison of the performance of the two approaches to troubleshooting, specifically to test selection for fault diagnosis. We use as experimental testbed the problem of diagnosing motorcycle engines. The first approach employs heuristic test selection rules obtained from expert mechanics. We compare it with the optimal decision analytic algorithm for test selection which employs estimated component failure probabilities and test costs. The decision analytic algorithm was found to reduce the expected cost (i.e. time) to arrive at a diagnosis by an average of 14% relative to the expert rules. Sensitivity analysis shows the results are quite robust to inaccuracy in the probability and cost estimates. This difference suggests some interesting implications for knowledge acquisition.
Updating Probabilities in Multiply-Connected Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

This paper focuses on probability updates in multiply-connected belief networks. Pearl has designed the method of conditioning, which enables us to apply his algorithm for belief updates in singly-connected networks to multiply-connected belief networks by selecting a loop-cutset for the network and instantiating these loop-cutset nodes. We discuss conditions that need to be satisfied by the selected nodes. We present a heuristic algorithm for finding a loop-cutset that satisfies these conditions.
MCE Reasoning in Recursive Causal Networks
Venue: arXiv cs.AI 2013
Year: 2013

A probabilistic method of reasoning under uncertainty is proposed based on the principle of Minimum Cross Entropy (MCE) and concept of Recursive Causal Model (RCM). The dependency and correlations among the variables are described in a special language BNDL (Belief Networks Description Language). Beliefs are propagated among the clauses of the BNDL programs representing the underlying probabilistic distributions. BNDL interpreters in both Prolog and C has been developed and the performance of the method is compared with those of the others.
Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice
Venue: arXiv cs.DS 2013
Year: 2013

Given two locations $s$ and $t$ in a road network, a distance query returns the minimum network distance from $s$ to $t$, while a shortest path query computes the actual route that achieves the minimum distance. These two types of queries find important applications in practice, and a plethora of solutions have been proposed in past few decades. The existing solutions, however, are optimized for either practical or asymptotic performance, but not both. In particular, the techniques with enhanced practical efficiency are mostly heuristic-based, and they offer unattractive worst-case guarantees in terms of space and time. On the other hand, the methods that are worst-case efficient often entail prohibitive preprocessing or space overheads, which render them inapplicable for the large road networks (with millions of nodes) commonly used in modern map applications. This paper presents {\em Arterial Hierarchy (AH)}, an index structure that narrows the gap between theory and practice in answering shortest path and distance queries on road networks. On the theoretical side, we show that, under a realistic assumption, AH answers any distance query in $\tilde{O}(\log \r)$ time, where $\r = d_{max}/d_{min}$, and $d_{max}$ (resp.\ $d_{min}$) is the largest (resp.\ smallest) $L_\infty$ distance between any two nodes in the road network. In addition, any shortest path query can be answered in $\tilde{O}(k + \log \r)$ time, where $k$ is the number of nodes on the shortest path. On the practical side, we experimentally evaluate AH on a large set of real road networks with up to twenty million nodes, and we demonstrate that (i) AH outperforms the state of the art in terms of query time, and (ii) its space and pre-computation overheads are moderate.
The Reachability Problem for Affine Functions on the Integers
Venue: arXiv cs.FL 2013
Year: 2013

We consider the problem of determining, given x, y in Z^k and a finite set F of affine functions on Z^k, whether y is reachable from x by applying the functions F. We also consider the analogous problem over N^k. These problems are known to be undecidable for k >= 2. We give 2-EXPTIME algorithms for both problems in the remaining case k = 1. The exact complexities remain open, although we show a simple NP lower bound.
A memetic algorithm for the minimum sum coloring problem
Venue: arXiv cs.DM 2013
Year: 2013

Given an undirected graph $G$, the Minimum Sum Coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of $G$ such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002-2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 17 instances. We also provide upper bounds for 18 additional instances for the first time.
Maps of Computer Science
Venue: arXiv cs.IR 2013
Year: 2013

We describe a practical approach for visual exploration of research papers. Specifically, we use the titles of papers from the DBLP database to create what we call maps of computer science (MoCS). Words and phrases from the paper titles are the cities in the map, and countries are created based on word and phrase similarity, calculated using co-occurrence. With the help of heatmaps, we can visualize the profile of a particular conference or journal over the base map. Similarly, heatmap profiles can be made of individual researchers or groups such as a department. The visualization system also makes it possible to change the data used to generate the base map. For example, a specific journal or conference can be used to generate the base map and then the heatmap overlays can be used to show the evolution of research topics in the field over the years. As before, individual researchers or research groups profiles can be visualized using heatmap overlays but this time over the journal or conference base map. Finally, research papers or abstracts easily generate visual abstracts giving a visual representation of the distribution of topics in the paper. We outline a modular and extensible system for term extraction using natural language processing techniques, and show the applicability of methods of information retrieval to calculation of term similarity and creation of a topic map. The system is available at mocs.cs.arizona.edu.
Tracking the Tracker from its Passive Sonar ML-PDA Estimates
Venue: arXiv cs.IT 2013
Year: 2013

Target motion analysis with wideband passive sonar has received much attention. Maximum likelihood probabilistic data-association (ML-PDA) represents an asymptotically efficient estimator for deterministic target motion, and is especially well-suited for low-observable targets; the results presented here apply to situations with higher signal to noise ratio as well, including of course the situation of a deterministic target observed via clean measurements without false alarms or missed detections. Here we study the inverse problem, namely, how to identify the observing platform (following a two-leg motion model) from the results of the target estimation process, i.e. the estimated target state and the Fisher information matrix, quantities we assume an eavesdropper might intercept. We tackle the problem and we present observability properties, with supporting simulation results.
Bayesian Prediction for Artificial Intelligence
Venue: arXiv cs.AI 2013
Year: 2013

This paper shows that the common method used for making predictions under uncertainty in A1 and science is in error. This method is to use currently available data to select the best model from a given class of models-this process is called abduction-and then to use this model to make predictions about future data. The correct method requires averaging over all the models to make a prediction-we call this method transduction. Using transduction, an AI system will not give misleading results when basing predictions on small amounts of data, when no model is clearly best. For common classes of models we show that the optimal solution can be given in closed form.
Bayesian Inference in Model-Based Machine Vision
Venue: arXiv cs.AI 2013
Year: 2013

This is a preliminary version of visual interpretation integrating multiple sensors in SUCCESSOR, an intelligent, model-based vision system. We pursue a thorough integration of hierarchical Bayesian inference with comprehensive physical representation of objects and their relations in a system for reasoning with geometry, surface materials and sensor models in machine vision. Bayesian inference provides a framework for accruing_ probabilities to rank order hypotheses.
Practical Issues in Constructing a Bayes' Belief Network
Venue: arXiv cs.AI 2013
Year: 2013

Bayes belief networks and influence diagrams are tools for constructing coherent probabilistic representations of uncertain knowledge. The process of constructing such a network to represent an expert's knowledge is used to illustrate a variety of techniques which can facilitate the process of structuring and quantifying uncertain relationships. These include some generalizations of the "noisy OR gate" concept. Sensitivity analysis of generic elements of Bayes' networks provides insight into when rough probability assessments are sufficient and when greater precision may be important.
The Automatic Training of Rule Bases that Use Numerical Uncertainty Representations
Venue: arXiv cs.AI 2013
Year: 2013

The use of numerical uncertainty representations allows better modeling of some aspects of human evidential reasoning. It also makes knowledge acquisition and system development, test, and modification more difficult. We propose that where possible, the assignment and/or refinement of rule weights should be performed automatically. We present one approach to performing this training - numerical optimization - and report on the results of some preliminary tests in training rule bases. We also show that truth maintenance can be used to make training more efficient and ask some epistemological questions raised by training rule weights.
The Role of Tuning Uncertain Inference Systems
Venue: arXiv cs.AI 2013
Year: 2013

This study examined the effects of "tuning" the parameters of the incremental function of MYCIN, the independent function of PROSPECTOR, a probability model that assumes independence, and a simple additive linear equation. me parameters of each of these models were optimized to provide solutions which most nearly approximated those from a full probability model for a large set of simple networks. Surprisingly, MYCIN, PROSPECTOR, and the linear equation performed equivalently; the independence model was clearly more accurate on the networks studied.