OpenRaiser/Intern-Atlas huggingface dataset:
On Measuring the Impact of Human Actions in the Machine Learning of a Board Game's Playing Policies
Venue: arXiv cs.AI 2006
Year: 2006

We investigate systematically the impact of human intervention in the training of computer players in a strategy board game. In that game, computer players utilise reinforcement learning with neural networks for evolving their playing strategies and demonstrate a slow learning speed. Human intervention can significantly enhance learning performance, but carry-ing it out systematically seems to be more of a problem of an integrated game development environment as opposed to automatic evolutionary learning.
Player co-modelling in a strategy board game: discovering how to play fast
Venue: arXiv cs.AI 2006
Year: 2006

In this paper we experiment with a 2-player strategy board game where playing models are evolved using reinforcement learning and neural networks. The models are evolved to speed up automatic game development based on human involvement at varying levels of sophistication and density when compared to fully autonomous playing. The experimental results suggest a clear and measurable association between the ability to win games and the ability to do that fast, while at the same time demonstrating that there is a minimum level of human involvement beyond which no learning really occurs.
Polynomial Time Symmetry and Isomorphism Testing for Connected Graphs
Venue: arXiv cs.DM 2006
Year: 2006

We use the concept of a Kirchhoff resistor network (alternatively random walk on a network) to probe connected graphs and produce symmetry revealing canonical labelings of the graph(s) nodes and edges.
Viterbi Algorithm Generalized for n-Tape Best-Path Search
Venue: arXiv cs.CL 2006
Year: 2006

We present a generalization of the Viterbi algorithm for identifying the path with minimal (resp. maximal) weight in a n-tape weighted finite-state machine (n-WFSM), that accepts a given n-tuple of input strings (s_1,... s_n). It also allows us to compile the best transduction of a given input n-tuple by a weighted (n+m)-WFSM (transducer) with n input and m output tapes. Our algorithm has a worst-case time complexity of O(|s|^n |E| log (|s|^n |Q|)), where n and |s| are the number and average length of the strings in the n-tuple, and |Q| and |E| the number of states and transitions in the n-WFSM, respectively. A straight forward alternative, consisting in intersection followed by classical shortest-distance search, operates in O(|s|^n (|E|+|Q|) log (|s|^n |Q|)) time.
The Relay-Eavesdropper Channel: Cooperation for Secrecy
Venue: arXiv cs.IT 2006
Year: 2006

This paper establishes the utility of user cooperation in facilitating secure wireless communications. In particular, the four-terminal relay-eavesdropper channel is introduced and an outer-bound on the optimal rate-equivocation region is derived. Several cooperation strategies are then devised and the corresponding achievable rate-equivocation region are characterized. Of particular interest is the novel Noise-Forwarding (NF) strategy, where the relay node sends codewords independent of the source message to confuse the eavesdropper. This strategy is used to illustrate the deaf helper phenomenon, where the relay is able to facilitate secure communications while being totally ignorant of the transmitted messages. Furthermore, NF is shown to increase the secrecy capacity in the reversely degraded scenario, where the relay node fails to offer performance gains in the classical setting. The gain offered by the proposed cooperation strategies is then proved theoretically and validated numerically in the additive White Gaussian Noise (AWGN) channel.
Linear Probing with Constant Independence
Venue: arXiv cs.DS 2006
Year: 2006

Hashing with linear probing dates back to the 1950s, and is among the most studied algorithms. In recent years it has become one of the most important hash table organizations since it uses the cache of modern computers very well. Unfortunately, previous analysis rely either on complicated and space consuming hash functions, or on the unrealistic assumption of free access to a truly random hash function. Already Carter and Wegman, in their seminal paper on universal hashing, raised the question of extending their analysis to linear probing. However, we show in this paper that linear probing using a pairwise independent family may have expected {\em logarithmic} cost per operation. On the positive side, we show that 5-wise independence is enough to ensure constant expected time per operation. This resolves the question of finding a space and time efficient hash function that provably ensures good performance for linear probing.
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting
Venue: arXiv cs.DS 2006
Year: 2006

We present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our work is to approximating the partition function $Z$ of a discrete system, such as the Ising model, matchings or colorings of a graph. The typical approach to estimating the partition function $Z(β^*)$ at some desired inverse temperature $β^*$ is to define a sequence, which we call a {\em cooling schedule}, $β_0=0<β_1<...<β_\ell=β^*$ where Z(0) is trivial to compute and the ratios $Z(β_{i+1})/Z(β_i)$ are easy to estimate by sampling from the distribution corresponding to $Z(β_i)$. Previous approaches required a cooling schedule of length $O^*(\ln{A})$ where $A=Z(0)$, thereby ensuring that each ratio $Z(β_{i+1})/Z(β_i)$ is bounded. We present a cooling schedule of length $\ell=O^*(\sqrt{\ln{A}})$. For well-studied problems such as estimating the partition function of the Ising model, or approximating the number of colorings or matchings of a graph, our cooling schedule is of length $O^*(\sqrt{n})$, which implies an overall savings of $O^*(n)$ in the running time of the approximate counting algorithm (since roughly $\ell$ samples are needed to estimate each ratio).
The Common Prefix Problem On Trees
Venue: arXiv cs.DS 2006
Year: 2006

We present a theoretical study of a problem arising in database query optimization, which we call as The Common Prefix Problem. We present a $(1-o(1))$ factor approximation algorithm for this problem, when the underlying graph is a binary tree. We then use a result of Feige and Kogan to show that even on stars, the problem is hard to approximate.
A Review of Papers that have a bearing on an Analysis of User Interactions in A Collaborative On-line Laboratory
Venue: arXiv cs.HC 2006
Year: 2006

A number of papers have been reviewed in the areas of HCI, CSCW, CSCL. These have been analyzed with a view to extract the ideas relevant to a consideration of user interactions in a collaborative on line laboratory which is being under development for use in the ITO BSc course at Southampton University. The construction of new theoretical models is to be based upon principles of collaborative HCI design and constructivist and situational educational theory. An investigation of the review papers it is hoped will lead towards a methodology/framework that can be used as guidance for collaborative learning systems and these will need to be developed alongside the requirements as they change during the development cycles. The primary outcome will be the analysis and re-design of the online e-learning laboratory together with a measure of its efficacy in the learning process.
The Boundary Between Privacy and Utility in Data Anonymization
Venue: arXiv cs.DB 2006
Year: 2006

We consider the privacy problem in data publishing: given a relation I containing sensitive information 'anonymize' it to obtain a view V such that, on one hand attackers cannot learn any sensitive information from V, and on the other hand legitimate users can use V to compute useful statistics on I. These are conflicting goals. We use a definition of privacy that is derived from existing ones in the literature, which relates the a priori probability of a given tuple t, Pr(t), with the a posteriori probability, Pr(t | V), and propose a novel and quite practical definition for utility. Our main result is the following. Denoting n the size of I and m the size of the domain from which I was drawn (i.e. n < m) then: when the a priori probability is Pr(t) = Omega(n/sqrt(m)) for some t, there exists no useful anonymization algorithm, while when Pr(t) = O(n/m) for all tuples t, then we give a concrete anonymization algorithm that is both private and useful. Our algorithm is quite different from the k-anonymization algorithm studied intensively in the literature, and is based on random deletions and insertions to I.
Towards Parallel Computing on the Internet: Applications, Architectures, Models and Programming Tools
Venue: arXiv cs.DC 2006
Year: 2006

The development of Internet wide resources for general purpose parallel computing poses the challenging task of matching computation and communication complexity. A number of parallel computing models exist that address this for traditional parallel architectures, and there are a number of emerging models that attempt to do this for large scale Internet-based systems like computational grids. In this survey we cover the three fundamental aspects -- application, architecture and model, and we show how they have been developed over the last decade. We also cover programming tools that are currently being used for parallel programming in computational grids. The trend in conventional computational models are to put emphasis on efficient communication between participating nodes by adapting different types of communication to network conditions. Effects of dynamism and uncertainties that arise in large scale systems are evidently important to understand and yet there is currently little work that addresses this from a parallel computing perspective.
Highly robust error correction by convex programming
Venue: arXiv cs.IT 2006
Year: 2006

This paper discusses a stylized communications problem where one wishes to transmit a real-valued signal x in R^n (a block of n pieces of information) to a remote receiver. We ask whether it is possible to transmit this information reliably when a fraction of the transmitted codeword is corrupted by arbitrary gross errors, and when in addition, all the entries of the codeword are contaminated by smaller errors (e.g. quantization errors). We show that if one encodes the information as Ax where A is a suitable m by n coding matrix (m >= n), there are two decoding schemes that allow the recovery of the block of n pieces of information x with nearly the same accuracy as if no gross errors occur upon transmission (or equivalently as if one has an oracle supplying perfect information about the sites and amplitudes of the gross errors). Moreover, both decoding strategies are very concrete and only involve solving simple convex optimization programs, either a linear program or a second-order cone program. We complement our study with numerical simulations showing that the encoder/decoder pair performs remarkably well.
Stratification in P2P Networks - Application to BitTorrent
Venue: arXiv cs.NI 2006
Year: 2006

We introduce a model for decentralized networks with collaborating peers. The model is based on the stable matching theory which is applied to systems with a global ranking utility function. We consider the dynamics of peers searching for efficient collaborators and we prove that a unique stable solution exists. We prove that the system converges towards the stable solution and analyze its speed of convergence. We also study the stratification properties of the model, both when all collaborations are possible and for random possible collaborations. We present the corresponding fluid limit on the choice of collaborators in the random case. As a practical example, we study the BitTorrent Tit-for-Tat policy. For this system, our model provides an interesting insight on peer download rates and a possible way to optimize peer strategy.
Many-to-One Throughput Capacity of IEEE 802.11 Multi-hop Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

This paper investigates the many-to-one throughput capacity (and by symmetry, one-to-many throughput capacity) of IEEE 802.11 multi-hop networks. It has generally been assumed in prior studies that the many-to-one throughput capacity is upper-bounded by the link capacity L. Throughput capacity L is not achievable under 802.11. This paper introduces the notion of "canonical networks", which is a class of regularly-structured networks whose capacities can be analyzed more easily than unstructured networks. We show that the throughput capacity of canonical networks under 802.11 has an analytical upper bound of 3L/4 when the source nodes are two or more hops away from the sink; and simulated throughputs of 0.690L (0.740L) when the source nodes are many hops away. We conjecture that 3L/4 is also the upper bound for general networks. When all links have equal length, 2L/3 can be shown to be the upper bound for general networks. Our simulations show that 802.11 networks with random topologies operated with AODV routing can only achieve throughputs far below the upper bounds. Fortunately, by properly selecting routes near the gateway (or by properly positioning the relay nodes leading to the gateway) to fashion after the structure of canonical networks, the throughput can be improved significantly by more than 150%. Indeed, in a dense network, it is worthwhile to deactivate some of the relay nodes near the sink judiciously.
On packet lengths and overhead for random linear coding over the erasure channel
Venue: arXiv cs.IT 2007
Year: 2007

We assess the practicality of random network coding by illuminating the issue of overhead and considering it in conjunction with increasingly long packets sent over the erasure channel. We show that the transmission of increasingly long packets, consisting of either of an increasing number of symbols per packet or an increasing symbol alphabet size, results in a data rate approaching zero over the erasure channel. This result is due to an erasure probability that increases with packet length. Numerical results for a particular modulation scheme demonstrate a data rate of approximately zero for a large, but finite-length packet. Our results suggest a reduction in the performance gains offered by random network coding.
Universal Source Coding for Monotonic and Fast Decaying Monotonic Distributions
Venue: arXiv cs.IT 2007
Year: 2007

We study universal compression of sequences generated by monotonic distributions. We show that for a monotonic distribution over an alphabet of size $k$, each probability parameter costs essentially $0.5 \log (n/k^3)$ bits, where $n$ is the coded sequence length, as long as $k = o(n^{1/3})$. Otherwise, for $k = O(n)$, the total average sequence redundancy is $O(n^{1/3+ε})$ bits overall. We then show that there exists a sub-class of monotonic distributions over infinite alphabets for which redundancy of $O(n^{1/3+ε})$ bits overall is still achievable. This class contains fast decaying distributions, including many distributions over the integers and geometric distributions. For some slower decays, including other distributions over the integers, redundancy of $o(n)$ bits overall is achievable, where a method to compute specific redundancy rates for such distributions is derived. The results are specifically true for finite entropy monotonic distributions. Finally, we study individual sequence redundancy behavior assuming a sequence is governed by a monotonic distribution. We show that for sequences whose empirical distributions are monotonic, individual redundancy bounds similar to those in the average case can be obtained. However, even if the monotonicity in the empirical distribution is violated, diminishing per symbol individual sequence redundancies with respect to the monotonic maximum likelihood description length may still be achievable.
Calculating Valid Domains for BDD-Based Interactive Configuration
Venue: arXiv cs.AI 2007
Year: 2007

In these notes we formally describe the functionality of Calculating Valid Domains from the BDD representing the solution space of valid configurations. The formalization is largely based on the CLab configuration framework.
A Better Good-Turing Estimator for Sequence Probabilities
Venue: arXiv cs.IT 2007
Year: 2007

We consider the problem of estimating the probability of an observed string drawn i.i.d. from an unknown distribution. The key feature of our study is that the length of the observed string is assumed to be of the same order as the size of the underlying alphabet. In this setting, many letters are unseen and the empirical distribution tends to overestimate the probability of the observed letters. To overcome this problem, the traditional approach to probability estimation is to use the classical Good-Turing estimator. We introduce a natural scaling model and use it to show that the Good-Turing sequence probability estimator is not consistent. We then introduce a novel sequence probability estimator that is indeed consistent under the natural scaling model.
Exploiting Social Annotation for Automatic Resource Discovery
Venue: arXiv cs.AI 2007
Year: 2007

Information integration applications, such as mediators or mashups, that require access to information resources currently rely on users manually discovering and integrating them in the application. Manual resource discovery is a slow process, requiring the user to sift through results obtained via keyword-based search. Although search methods have advanced to include evidence from document contents, its metadata and the contents and link structure of the referring pages, they still do not adequately cover information sources -- often called ``the hidden Web''-- that dynamically generate documents in response to a query. The recently popular social bookmarking sites, which allow users to annotate and share metadata about various information sources, provide rich evidence for resource discovery. In this paper, we describe a probabilistic model of the user annotation process in a social bookmarking system del.icio.us. We then use the model to automatically find resources relevant to a particular information domain. Our experimental results on data obtained from \emph{del.icio.us} show this approach as a promising method for helping automate the resource discovery task.
The Invar Tensor Package
Venue: arXiv cs.SC 2007
Year: 2007

The Invar package is introduced, a fast manipulator of generic scalar polynomial expressions formed from the Riemann tensor of a four-dimensional metric-compatible connection. The package can maximally simplify any polynomial containing tensor products of up to seven Riemann tensors within seconds. It has been implemented both in Mathematica and Maple algebraic systems.
A Nice Labelling for Tree-Like Event Structures of Degree 3
Venue: arXiv cs.DC 2007
Year: 2007

We address the problem of ﬁnding nice labellings for event structures of degree 3. We develop a minimum theory by which we prove that the labelling number of an event structure of degree 3 is bounded by a linear function of the height. The main theorem we present in this paper states that event structures of degree 3 whose causality order is a tree have a nice labelling with 3 colors. Finally, we exemplify how to use this theorem to construct upper bounds for the labelling number of other event structures of degree 3.
Optimum Linear LLR Calculation for Iterative Decoding on Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

On a fading channel with no channel state information at the receiver, calculating true log-likelihood ratios (LLR) is complicated. Existing work assume that the power of the additive noise is known and use the expected value of the fading gain in a linear function of the channel output to find approximate LLRs. In this work, we first assume that the power of the additive noise is known and we find the optimum linear approximation of LLRs in the sense of maximum achievable transmission rate on the channel. The maximum achievable rate under this linear LLR calculation is almost equal to the maximum achievable rate under true LLR calculation. We also observe that this method appears to be the optimum in the sense of bit error rate performance too. These results are then extended to the case that the noise power is unknown at the receiver and a performance almost identical to the case that the noise power is perfectly known is obtained.
Physical Layer Network Coding
Venue: arXiv cs.IT 2007
Year: 2007

A main distinguishing feature of a wireless network compared with a wired network is its broadcast nature, in which the signal transmitted by a node may reach several other nodes, and a node may receive signals from several other nodes simultaneously. Rather than a blessing, this feature is treated more as an interference-inducing nuisance in most wireless networks today (e.g., IEEE 802.11). This paper shows that the concept of network coding can be applied at the physical layer to turn the broadcast property into a capacity-boosting advantage in wireless ad hoc networks. Specifically, we propose a physical-layer network coding (PNC) scheme to coordinate transmissions among nodes. In contrast to straightforward network coding which performs coding arithmetic on digital bit streams after they have been received, PNC makes use of the additive nature of simultaneously arriving electromagnetic (EM) waves for equivalent coding operation. And in doing so, PNC can potentially achieve 100% and 50% throughput increases compared with traditional transmission and straightforward network coding, respectively, in multi-hop networks. More specifically, the information-theoretic capacity of PNC is almost double that of traditional transmission in the SNR region of practical interest (higher than 0dB). We believe this is a first paper that ventures into EM-wave-based network coding at the physical layer and demonstrates its potential for boosting network capacity.
Exploiting Heavy Tails in Training Times of Multilayer Perceptrons: A Case Study with the UCI Thyroid Disease Database
Venue: arXiv cs.NE 2007
Year: 2007

The random initialization of weights of a multilayer perceptron makes it possible to model its training process as a Las Vegas algorithm, i.e. a randomized algorithm which stops when some required training error is obtained, and whose execution time is a random variable. This modeling is used to perform a case study on a well-known pattern recognition benchmark: the UCI Thyroid Disease Database. Empirical evidence is presented of the training time probability distribution exhibiting a heavy tail behavior, meaning a big probability mass of long executions. This fact is exploited to reduce the training time cost by applying two simple restart strategies. The first assumes full knowledge of the distribution yielding a 40% cut down in expected time with respect to the training without restarts. The second, assumes null knowledge, yielding a reduction ranging from 9% to 23%.
Arbitrary Rate Permutation Modulation for the Gaussian Channel
Venue: arXiv cs.IT 2007
Year: 2007

In this paper non-group permutation modulated sequences for the Gaussian channel are considered. Without the restriction to group codes rather than subsets of group codes, arbitrary rates are achievable. The code construction utilizes the known optimal group constellations to ensure at least the same performance but exploit the Gray code ordering structure of multiset permutations as a selection criterion at the decoder. The decoder achieves near maximum likelihood performance at low computational cost and low additional memory requirements at the receiver.