OpenRaiser/Intern-Atlas huggingface dataset:
Let's get the student into the driver's seat
Venue: arXiv cs.CL 2007
Year: 2007

Speaking a language and achieving proficiency in another one is a highly complex process which requires the acquisition of various kinds of knowledge and skills, like the learning of words, rules and patterns and their connection to communicative goals (intentions), the usual starting point. To help the learner to acquire these skills we propose an enhanced, electronic version of an age old method: pattern drills (henceforth PDs). While being highly regarded in the fifties, PDs have become unpopular since then, partially because of their lack of grounding (natural context) and rigidity. Despite these shortcomings we do believe in the virtues of this approach, at least with regard to the acquisition of basic linguistic reflexes or skills (automatisms), necessary to survive in the new language. Of course, the method needs improvement, and we will show here how this can be achieved. Unlike tapes or books, computers are open media, allowing for dynamic changes, taking users' performances and preferences into account. Building an electronic version of PDs amounts to building an open resource, accomodatable to the users' ever changing needs.
On b-perfect chordal graphs
Venue: arXiv cs.DM 2007
Year: 2007

The b-chromatic number of a graph G is the largest integer k such that G has a coloring of the vertices in k color classes such that every color class contains a vertex that has a neighbour in all other color classes. We characterize the class of chordal graphs for which the b-chromatic number is equal to the chromatic number for every induced subgraph.
Report on "American Option Pricing and Hedging Strategies"
Venue: arXiv cs.CE 2007
Year: 2007

This paper mainly discusses the American option's hedging strategies via binomialmodel and the basic idea of pricing and hedging American option. Although the essential scheme of hedging is almost the same as European option, small differences may arise when simulating the process for American option holder has more rights, spelling that the option can be exercised at anytime before its maturity. Our method is dynamic-hedging method.
Covariance and PCA for Categorical Variables
Venue: arXiv cs.LG 2007
Year: 2007

Covariances from categorical variables are defined using a regular simplex expression for categories. The method follows the variance definition by Gini, and it gives the covariance as a solution of simultaneous equations. The calculated results give reasonable values for test data. A method of principal component analysis (RS-PCA) is also proposed using regular simplex expressions, which allows easy interpretation of the principal components. The proposed methods apply to variable selection problem of categorical data USCensus1990 data. The proposed methods give appropriate criterion for the variable selection problem of categorical
On Outage Behavior of Wideband Slow-Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

This paper investigates point-to-point information transmission over a wideband slow-fading channel, modeled as an (asymptotically) large number of independent identically distributed parallel channels, with the random channel fading realizations remaining constant over the entire coding block. On the one hand, in the wideband limit the minimum achievable energy per nat required for reliable transmission, as a random variable, converges in probability to certain deterministic quantity. On the other hand, the exponential decay rate of the outage probability, termed as the wideband outage exponent, characterizes how the number of parallel channels, {\it i.e.}, the ``bandwidth'', should asymptotically scale in order to achieve a target outage probability at a target energy per nat. We examine two scenarios: when the transmitter has no channel state information and adopts uniform transmit power allocation among parallel channels; and when the transmitter is endowed with an one-bit channel state feedback for each parallel channel and accordingly allocates its transmit power. For both scenarios, we evaluate the wideband minimum energy per nat and the wideband outage exponent, and discuss their implication for system performance.
A Note On Computing Set Overlap Classes
Venue: arXiv cs.DS 2007
Year: 2007

Let ${\cal V}$ be a finite set of $n$ elements and ${\cal F}=\{X_1,X_2, >..., X_m\}$ a family of $m$ subsets of ${\cal V}.$ Two sets $X_i$ and $X_j$ of ${\cal F}$ overlap if $X_i \cap X_j \neq \emptyset,$ $X_j \setminus X_i \neq \emptyset,$ and $X_i \setminus X_j \neq \emptyset.$ Two sets $X,Y\in {\cal F}$ are in the same overlap class if there is a series $X=X_1,X_2, ..., X_k=Y$ of sets of ${\cal F}$ in which each $X_iX_{i+1}$ overlaps. In this note, we focus on efficiently identifying all overlap classes in $O(n+\sum_{i=1}^m |X_i|)$ time. We thus revisit the clever algorithm of Dahlhaus of which we give a clear presentation and that we simplify to make it practical and implementable in its real worst case complexity. An useful variant of Dahlhaus's approach is also explained.
Approximation Algorithms for Orienteering with Time Windows
Venue: arXiv cs.DS 2007
Year: 2007

Orienteering is the following optimization problem: given an edge-weighted graph (directed or undirected), two nodes s,t and a time limit T, find an s-t walk of total length at most T that maximizes the number of distinct nodes visited by the walk. One obtains a generalization, namely orienteering with time-windows (also referred to as TSP with time-windows), if each node v has a specified time-window [R(v), D(v)] and a node v is counted as visited by the walk only if v is visited during its time-window. For the time-window problem, an O(\log \opt) approximation can be achieved even for directed graphs if the algorithm is allowed quasi-polynomial time. However, the best known polynomial time approximation ratios are O(\log^2 \opt) for undirected graphs and O(\log^4 \opt) in directed graphs. In this paper we make some progress towards closing this discrepancy, and in the process obtain improved approximation ratios in several natural settings. Let L(v) = D(v) - R(v) denote the length of the time-window for v and let \lmax = \max_v L(v) and \lmin = \min_v L(v). Our results are given below with αdenoting the known approximation ratio for orienteering (without time-windows). Currently α= (2+\eps) for undirected graphs and α= O(\log^2 \opt) in directed graphs. 1. An O(α\log \lmax) approximation when R(v) and D(v) are integer valued for each v. 2. An O(α\max{\log \opt, \log \frac{\lmax}{\lmin}}) approximation. 3. An O(α\log \frac{\lmax}{\lmin}) approximation when no start and end points are specified. In particular, if \frac{\lmax}{\lmin} is poly-bounded, we obtain an O(\log n) approximation for the time-window problem in undirected graphs.
On Precision - Redundancy Relation in the Design of Source Coding Algorithms
Venue: arXiv cs.IT 2007
Year: 2007

We study the effects of finite-precision representation of source's probabilities on the efficiency of classic source coding algorithms, such as Shannon, Gilbert-Moore, or arithmetic codes. In particular, we establish the following simple connection between the redundancy $R$ and the number of bits $W$ necessary for representation of source's probabilities in computer's memory ($R$ is assumed to be small): \begin{equation*} W \lesssim η\log_2 \frac{m}{R}, \end{equation*} where $m$ is the cardinality of the source's alphabet, and $η\leqslant 1$ is an implementation-specific constant. In case of binary alphabets ($m=2$) we show that there exist codes for which $η= 1/2$, and in $m$-ary case ($m > 2$) we show that there exist codes for which $η= m/(m+1)$. In general case, however (which includes designs relying on progressive updates of frequency counters), we show that $η= 1$. Usefulness of these results for practical designs of source coding algorithms is also discussed.
Redundancy Estimates for Word-Based Encoding of Sequences Produced by a Bernoulli Source
Venue: arXiv cs.IT 2007
Year: 2007

The efficiency of a code is estimated by its redundancy $R$, while the complexity of a code is estimated by its average delay $\bar N$. In this work we construct word-based codes, for which $R \lesssim \bar N^{-5/3}$. Therefore, word-based codes can attain the same redundancy as block-codes while being much less complex. We also consider uniform on the output codes, the benefit of which is the lack of a running synchronization error. For such codes $\bar N^{-1} \lesssim R \lesssim \bar N^{-1}$, except for a case when all input symbols are equiprobable, when $R \leqslant \bar N^{-2}$ for infinitely many $\bar N$.
On the Relationship between the Posterior and Optimal Similarity
Venue: arXiv cs.LG 2007
Year: 2007

For a classification problem described by the joint density $P(ω,x)$, models of $P(ω\eqω'|x,x')$ (the ``Bayesian similarity measure'') have been shown to be an optimal similarity measure for nearest neighbor classification. This paper analyzes demonstrates several additional properties of that conditional distribution. The paper first shows that we can reconstruct, up to class labels, the class posterior distribution $P(ω|x)$ given $P(ω\eqω'|x,x')$, gives a procedure for recovering the class labels, and gives an asymptotically Bayes-optimal classification procedure. It also shows, given such an optimal similarity measure, how to construct a classifier that outperforms the nearest neighbor classifier and achieves Bayes-optimal classification rates. The paper then analyzes Bayesian similarity in a framework where a classifier faces a number of related classification tasks (multitask learning) and illustrates that reconstruction of the class posterior distribution is not possible in general. Finally, the paper identifies a distinct class of classification problems using $P(ω\eqω'|x,x')$ and shows that using $P(ω\eqω'|x,x')$ to solve those problems is the Bayes optimal solution.
On Decidability Properties of Local Sentences
Venue: arXiv cs.LO 2007
Year: 2007

Local (first order) sentences, introduced by Ressayre, enjoy very nice decidability properties, following from some stretching theorems stating some remarkable links between the finite and the infinite model theory of these sentences. We prove here several additional results on local sentences. The first one is a new decidability result in the case of local sentences whose function symbols are at most unary: one can decide, for every regular cardinal k whether a local sentence phi has a model of order type k. Secondly we show that this result can not be extended to the general case. Assuming the consistency of an inaccessible cardinal we prove that the set of local sentences having a model of order type omega_2 is not determined by the axiomatic system ZFC + GCH, where GCH is the generalized continuum hypothesis
A Spectral Approach to Analyzing Belief Propagation for 3-Coloring
Venue: arXiv cs.CC 2007
Year: 2007

Contributing to the rigorous understanding of BP, in this paper we relate the convergence of BP to spectral properties of the graph. This encompasses a result for random graphs with a ``planted'' solution; thus, we obtain the first rigorous result on BP for graph coloring in the case of a complex graphical structure (as opposed to trees). In particular, the analysis shows how Belief Propagation breaks the symmetry between the $3!$ possible permutations of the color classes.
A Reactive Tabu Search Algorithm for Stimuli Generation in Psycholinguistics
Venue: arXiv cs.AI 2007
Year: 2007

The generation of meaningless "words" matching certain statistical and/or linguistic criteria is frequently needed for experimental purposes in Psycholinguistics. Such stimuli receive the name of pseudowords or nonwords in the Cognitive Neuroscience literatue. The process for building nonwords sometimes has to be based on linguistic units such as syllables or morphemes, resulting in a numerical explosion of combinations when the size of the nonwords is increased. In this paper, a reactive tabu search scheme is proposed to generate nonwords of variables size. The approach builds pseudowords by using a modified Metaheuristic algorithm based on a local search procedure enhanced by a feedback-based scheme. Experimental results show that the new algorithm is a practical and effective tool for nonword generation.
Spanners of Complete $k$-Partite Geometric Graphs
Venue: arXiv cs.CG 2007
Year: 2007

We address the following problem: Given a complete $k$-partite geometric graph $K$ whose vertex set is a set of $n$ points in $\mathbb{R}^d$, compute a spanner of $K$ that has a ``small'' stretch factor and ``few'' edges. We present two algorithms for this problem. The first algorithm computes a $(5+ε)$-spanner of $K$ with O(n) edges in $O(n \log n)$ time. The second algorithm computes a $(3+ε)$-spanner of $K$ with $O(n \log n)$ edges in $O(n \log n)$ time. The latter result is optimal: We show that for any $2 \leq k \leq n - Θ(\sqrt{n \log n})$, spanners with $O(n \log n)$ edges and stretch factor less than 3 do not exist for all complete $k$-partite geometric graphs.
Towards 3D ultrasound image based soft tissue tracking: a transrectal ultrasound prostate image alignment system
Venue: arXiv cs.OH 2007
Year: 2007

The emergence of real-time 3D ultrasound (US) makes it possible to consider image-based tracking of subcutaneous soft tissue targets for computer guided diagnosis and therapy. We propose a 3D transrectal US based tracking system for precise prostate biopsy sample localisation. The aim is to improve sample distribution, to enable targeting of unsampled regions for repeated biopsies, and to make post-interventional quality controls possible. Since the patient is not immobilized, since the prostate is mobile and due to the fact that probe movements are only constrained by the rectum during biopsy acquisition, the tracking system must be able to estimate rigid transformations that are beyond the capture range of common image similarity measures. We propose a fast and robust multi-resolution attribute-vector registration approach that combines global and local optimization methods to solve this problem. Global optimization is performed on a probe movement model that reduces the dimensionality of the search space and thus renders optimization efficient. The method was tested on 237 prostate volumes acquired from 14 different patients for 3D to 3D and 3D to orthogonal 2D slices registration. The 3D-3D version of the algorithm converged correctly in 96.7% of all cases in 6.5s with an accuracy of 1.41mm (r.m.s.) and 3.84mm (max). The 3D to slices method yielded a success rate of 88.9% in 2.3s with an accuracy of 1.37mm (r.m.s.) and 4.3mm (max).
Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs
Venue: arXiv cs.DM 2007
Year: 2007

For digraphs $G$ and $H$, a homomorphism of $G$ to $H$ is a mapping $f:\ V(G)\dom V(H)$ such that $uv\in A(G)$ implies $f(u)f(v)\in A(H)$. If, moreover, each vertex $u \in V(G)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of a homomorphism $f$ is $\sum_{u\in V(G)}c_{f(u)}(u)$. For each fixed digraph $H$, the minimum cost homomorphism problem for $H$, denoted MinHOM($H$), can be formulated as follows: Given an input digraph $G$, together with costs $c_i(u)$, $u\in V(G)$, $i\in V(H)$, decide whether there exists a homomorphism of $G$ to $H$ and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well studied optimization problems such as the minimum cost chromatic partition and repair analysis problems. We focus on the minimum cost homomorphism problem for locally semicomplete digraphs and quasi-transitive digraphs which are two well-known generalizations of tournaments. Using graph-theoretic characterization results for the two digraph classes, we obtain a full dichotomy classification of the complexity of minimum cost homomorphism problems for both classes.
A Common View on Strong, Uniform, and Other Notions of Equivalence in Answer-Set Programming
Venue: arXiv cs.AI 2007
Year: 2007

Logic programming under the answer-set semantics nowadays deals with numerous different notions of program equivalence. This is due to the fact that equivalence for substitution (known as strong equivalence) and ordinary equivalence are different concepts. The former holds, given programs P and Q, iff P can be faithfully replaced by Q within any context R, while the latter holds iff P and Q provide the same output, that is, they have the same answer sets. Notions in between strong and ordinary equivalence have been introduced as theoretical tools to compare incomplete programs and are defined by either restricting the syntactic structure of the considered context programs R or by bounding the set A of atoms allowed to occur in R (relativized equivalence).For the latter approach, different A yield properly different equivalence notions, in general. For the former approach, however, it turned out that any ``reasonable'' syntactic restriction to R coincides with either ordinary, strong, or uniform equivalence. In this paper, we propose a parameterization for equivalence notions which takes care of both such kinds of restrictions simultaneously by bounding, on the one hand, the atoms which are allowed to occur in the rule heads of the context and, on the other hand, the atoms which are allowed to occur in the rule bodies of the context. We introduce a general semantical characterization which includes known ones as SE-models (for strong equivalence) or UE-models (for uniform equivalence) as special cases. Moreover,we provide complexity bounds for the problem in question and sketch a possible implementation method. To appear in Theory and Practice of Logic Programming (TPLP).
Kleene, Rogers and Rice Theorems Revisited in C and in Bash
Venue: arXiv cs.LO 2007
Year: 2007

The recursion theorem in the weak form {e}(z)=x(e,z) (universal function not needed) and in Rogers form {n}(z)={{x}(n)}(z) and Rice theorem are proved a first time using programs in C, and a second time with scripts in Bash.
On the computational complexity of cut-reduction
Venue: arXiv cs.LO 2007
Year: 2007

Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations, and explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theories can be reobtained in a uniform way.
Link Scheduling in STDMA Wireless Networks: A Line Graph Approach
Venue: arXiv cs.NI 2007
Year: 2007

We consider point to point link scheduling in Spatial Time Division Multiple Access (STDMA) wireless networks under the physical interference model. We propose a novel link scheduling algorithm based on a line graph representation of the network, by embedding the interferences between pairs of nodes into the edge weights of the line graph. Our algorithm achieves lower schedule length and lower run time complexity than existing algorithms.
Critique du rapport signal à bruit en théorie de l'information -- A critical appraisal of the signal to noise ratio in information theory
Venue: arXiv cs.IT 2007
Year: 2007

The signal to noise ratio, which plays such an important role in information theory, is shown to become pointless in digital communications where - symbols are modulating carriers, which are solutions of linear differential equations with polynomial coefficients, - demodulations is achieved thanks to new algebraic estimation techniques. Operational calculus, differential algebra and nonstandard analysis are the main mathematical tools.
Hierarchy construction schemes within the Scale set framework
Venue: arXiv cs.CV 2007
Year: 2007

Segmentation algorithms based on an energy minimisation framework often depend on a scale parameter which balances a fit to data and a regularising term. Irregular pyramids are defined as a stack of graphs successively reduced. Within this framework, the scale is often defined implicitly as the height in the pyramid. However, each level of an irregular pyramid can not usually be readily associated to the global optimum of an energy or a global criterion on the base level graph. This last drawback is addressed by the scale set framework designed by Guigues. The methods designed by this author allow to build a hierarchy and to design cuts within this hierarchy which globally minimise an energy. This paper studies the influence of the construction scheme of the initial hierarchy on the resulting optimal cuts. We propose one sequential and one parallel method with two variations within both. Our sequential methods provide partitions near the global optima while parallel methods require less execution times than the sequential method of Guigues even on sequential machines.
Numerical Sensitivity and Efficiency in the Treatment of Epistemic and Aleatory Uncertainty
Venue: arXiv cs.AI 2007
Year: 2007

The treatment of both aleatory and epistemic uncertainty by recent methods often requires an high computational effort. In this abstract, we propose a numerical sampling method allowing to lighten the computational burden of treating the information by means of so-called fuzzy random variables.
Rethinking Information Theory for Mobile Ad Hoc Networks
Venue: arXiv cs.IT 2007
Year: 2007

The subject of this paper is the long-standing open problem of developing a general capacity theory for wireless networks, particularly a theory capable of describing the fundamental performance limits of mobile ad hoc networks (MANETs). A MANET is a peer-to-peer network with no pre-existing infrastructure. MANETs are the most general wireless networks, with single-hop, relay, interference, mesh, and star networks comprising special cases. The lack of a MANET capacity theory has stunted the development and commercialization of many types of wireless networks, including emergency, military, sensor, and community mesh networks. Information theory, which has been vital for links and centralized networks, has not been successfully applied to decentralized wireless networks. Even if this was accomplished, for such a theory to truly characterize the limits of deployed MANETs it must overcome three key roadblocks. First, most current capacity results rely on the allowance of unbounded delay and reliability. Second, spatial and timescale decompositions have not yet been developed for optimally modeling the spatial and temporal dynamics of wireless networks. Third, a useful network capacity theory must integrate rather than ignore the important role of overhead messaging and feedback. This paper describes some of the shifts in thinking that may be needed to overcome these roadblocks and develop a more general theory that we refer to as non-equilibrium information theory.
Directed Percolation in Wireless Networks with Interference and Noise
Venue: arXiv cs.IT 2007
Year: 2007

Previous studies of connectivity in wireless networks have focused on undirected geometric graphs. More sophisticated models such as Signal-to-Interference-and-Noise-Ratio (SINR) model, however, usually leads to directed graphs. In this paper, we study percolation processes in wireless networks modelled by directed SINR graphs. We first investigate interference-free networks, where we define four types of phase transitions and show that they take place at the same time. By coupling the directed SINR graph with two other undirected SINR graphs, we further obtain analytical upper and lower bounds on the critical density. Then, we show that with interference, percolation in directed SINR graphs depends not only on the density but also on the inverse system processing gain. We also provide bounds on the critical value of the inverse system processing gain.