Statistics Technical Reports:Search | Browse by year

Term(s):1997
Results:26
Sorted by:
Page: 1 2  Next

Title:Prediction Games and Arcing Algorithms
Author(s):Breiman, Leo; 
Date issued:Dec 1997
Date modified:revised December 14, 1998
http://nma.berkeley.edu/ark:/28722/bk0000n3h3f (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3h40 (PostScript)
Abstract:The theory behind the success of adaptive reweighting and combining algorithms (arcing) such as Adaboost (Freund and Schapire [1995, 1996a]) and others in reducing generalization error has not been well understood. By formulating prediction as a game where one player makes a selection from instances in the training set and the other a convex linear combination of predictors from a finite set, existing arcing algorithms are shown to be algorithms for finding good game strategies. The minimax theorem is an essential ingredient of the convergence proofs. An arcing algorithm is described that converges to the optimal strategy. A bound on the generalization error for the combined predictors in terms of their maximum error is proven that is sharper than bounds to date. Schapire et al. [1997] offered an explanation of why Adaboost works in terms of its ability to produce generally high margins. The empirical comparison of Adaboost to the optimal arcing algorithm shows that their explanation is not complete.
Keyword note:Breiman__Leo
Report ID:504
Relevance:100

Title:The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest
Author(s):Pitman, Jim; 
Date issued:Dec 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3h0s (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3h1b (PostScript)
Abstract:Let $B$ be a standard one-dimensional Brownian motion started at 0. Let $L_(t,v)(|B|)$ be the occupation density of $|B|$ at level $v$ up to time $t$. The distribution of the process of local times $(L_(t,v)(|B|), v \ge 0 )$ conditionally given $B_t = 0$ and $L_(t,0) (|B|)= \ell$ is shown to be that of the unique strong solution $X$ of the \Ito\ SDE $$ dX_v = \left\( 4 - X_v^2 \left( t - \mbox($\int_0^v X_u du$) \right) ^(-1) \right\) \, dv + 2 \sqrt(X_v) d B_v$$ on the interval $[0,V_t (X))$,where $V_t(X):= \inf \( v: \int_0^v X_u du = t \)$and $X_v = 0$ for all $v \ge V_t(X)$. This conditioned form of the Ray-Knight description of Brownian local times arises from study of the asymptotic distribution as $n \te \infty$ and $ 2 k/\sqrt(n) \te \ell$ of the height profile of a uniform rooted random forest of $k$ trees labeled by a set of $n$ elements, as obtained by conditioning a uniform random mapping of the set to itself to have $k$ cyclic points. The SDE is the continuous analog of a simple description of a Galton-Watson branching process conditioned on its total progeny. A result is obtained regarding the weak convergence of normalizations of such conditioned Galton-Watson processes and height profiles of random forests to a solution of the SDE. For $\ell = 0$, corresponding to asymptotics of a uniform random tree, the SDE gives a new description of the process of local times of a Brownian excursion, implying Jeulin's description of these local times as a time change of twice a Brownian excursion. Another corollary is the Biane-Yor description of the local times of a reflecting Brownian bridge as a time changed reversal of twice a Brownian meander of the same length.
Pub info:Ann. Prob. 27, 261-283 (1999)
Keyword note:Pitman__Jim
Report ID:503
Relevance:100

Title:Random spanning trees of Cayley graphs and an associated compactification of semigroups
Author(s):Evans, S. N.; 
Date issued:Dec 1997
Date modified:revised March 1998
http://nma.berkeley.edu/ark:/28722/bk0000n3f5h (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3f62 (PostScript)
Abstract:A sequential construction of a random spanning tree for the Cayley graph of a finitely generated, countably infinite subsemigroup $V$ of a group $G$ is considered. At stage $n$, the spanning tree $T$ is approximated by a finite tree $T_n$ rooted at the identity. The approximation $T_(n+1)$ is obtained by connecting edges to the points of $V$ that are not already vertices of $T_n$ but can be obtained from vertices of $T_n$ via multiplication by a random walk step taking values in the generating set of $V$. This construction leads to a compactification of the semigroup $V$ in which a sequence of elements of $V$ that is not eventually constant is convergent if the random geodesic through the spanning tree $T$ that joins the identity to the $n^(\mathrm th)$ element of the sequence converges in distribution as $n \rightarrow \infty$. The compactification is identified in a number of examples. Also, it is shown that if $h(T_n)$ and $\#(T_n)$ denote, respectively, the height and size of the approximating tree $T_n$, then there are constants $0 < c_h \le 1$ and $0 \le c_\# \le \log 2$ such that $\lim_(n \rightarrow \infty) n^(-1) h(T_n) = c_h$ and $\lim_(n \rightarrow \infty) n^(-1) \log \#(T_n) = c_\#$ almost surely.
Keyword note:Evans__Steven_N
Report ID:502
Relevance:100

Title:On Markov Chains with Continuous State Space
Author(s):Diaconis, Persi; Freedman, David; 
Date issued:Dec 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3d6j (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3d73 (PostScript)
Abstract:In this expository paper, we prove the following theorem, which may be of some use in studying Markov Chain Monte Carlo methods like hit and run, the Metropolis algorithm, or the Gibbs sampler. Suppose a discrete-time Markov chain is aperiodic, irreducible, and there is a stationary probability distribution. Then from almost all starting points the distribution of the chain at time n converges in norm to the stationary distribution. This known theorem is a special case of more general results due to Doeblin, and the paper concludes with a brief review of the literature.
Keyword note:Diaconis__Persi Freedman__David
Report ID:501
Relevance:100

Title:On the Hit and Run Process
Author(s):Diaconis, Persi; Freedman, David; 
Date issued:Nov 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3c4x (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3c5g (PostScript)
Abstract:Given a density f on Euclidean k-space and a starting point x, choose a line L at random through x and move to a point on L chosen at random from f restricted to L. This procedure defines a Markov chain-- the "hit and run process." The given density f is stationary; for almost all starting points x, the distribution of the chain at time n converges to the stationary distribution as n gets large. This expository paper proves some of the convergence theorems, and gives examples.
Keyword note:Diaconis__Persi Freedman__David
Report ID:497
Relevance:100

Title:Transforming spatial point processes into Poisson processes
Author(s):Schoenberg, Frederic; 
Date issued:Nov 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3b06 (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3b1r (PostScript)
Abstract:In 1986, Merzbach and Nualart demonstrated a method of transforming a two-parameter point process into a planar Poisson process of unit rate, using random stopping sets. Merzbach and Nualart's theorem applies only to a special class of point processes, since it requires two restrictive conditions: the (F4) condition of conditional independence and the convexity of the 1-compensator. The (F4) condition was removed in 1990 by Nair, but the convexity condition remained. Here both the (F4) condition and the convexity condition are removed by making use of predictable sets rather than stopping sets. As with Nair's theorem, the result extends to point processes in higher dimensions.
Keyword note:Schoenberg__Frederic_R
Report ID:496
Relevance:100

Title:Coalescents with multiple collisions
Author(s):Pitman, Jim; 
Date issued:Nov 1997
http://nma.berkeley.edu/ark:/28722/bk0000n381q (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3828 (PostScript)
Abstract:For each finite measure $\Lambda$ on $[0,1]$, a coalescent Markov process, with state space the compact set of all partitions of the set $N$ of positive integers, is constructed so the restriction of the partition to each finite subset of $N$ is a Markov chain with the following transition rates: when the partition has $b$ blocks, each $k$-tuple of blocks is merging to form a single block at rate $\int_0^1 x^(k-2) (1 - x) ^(b-k) \Lambda(dx)$. Call this process a (\em $\Lambda$-coalescent). Discrete measure valued processes derived from the $\Lambda$-coalescent model a system of masses undergoing coalescent collisions. Kingman's coalescent, which has numerous applications in population genetics, is the $\delta_0$-coalescent for $\delta_0$ a unit mass at 0. The coalescent recently derived by Bolthausen and Sznitman from Ruelle's probability cascades, in the context of the Sherrington-Kirkpatrick spin glass model in mathematical physics, is the $U$-coalescent for $U$ uniform on $[0,1]$. For $\Lambda=U$, and whenever an infinite number of masses are present, each collision in a $\Lambda$-coalescent involves an infinite number of masses almost surely, and the proportion of masses involved exists almost surely and is distributed proportionally to $\Lambda$. The two-parameter Poisson-Dirichlet family of random discrete distributions derived from a stable subordinator, and corresponding exchangeable random partitions of $N$ governed by a generalization of the Ewens sampling formula, are applied to describe transition mechanisms for processes of coalescence and fragmentation, including the $U$-coalescent and its time reversal.
Keyword note:Pitman__Jim
Report ID:495
Relevance:100

Title:Geometrically Intrinsic Nonlinear Recursive Filters I: Algorithms
Author(s):Darling, R. W. R.; 
Date issued:Oct 1997
Date modified:revised March 1998
http://nma.berkeley.edu/ark:/28722/bk0000n3k7p (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3k87 (PostScript)
Abstract:The Geometrically Intrinsic Nonlinear Recursive Filter, or GI Filter, is designed to estimate an arbitrary continuous-time Markov diffusion process X subject to nonlinear discrete-time observations. The GI Filter is fundamentally different from the much-used Extended Kalman Filter, and its second-order variants, even in the simplest nonlinear case, in that: * It uses a quadratic function of a vector observation to update the state, instead of the linear function used by the EKF. * It is based on deeper geometric principles, which make the GI Filter coordinate-invariant. This implies, for example, that if a linear system were subjected to a nonlinear transformation f of the state-space and analyzed using the GI Filter, the resulting state estimates and conditional variances would be the push-forward under f of the Kalman Filter estimates for the untransformed system -- a property which is not shared by the EKF or its second-order variants. The noise covariance of X and the observation covariance themselves induce geometries on state space and observation space, respectively, and associated canonical connections. A sequel to this paper develops stochastic differential geometry results -- based on ``intrinsic location parameters,'' a notion derived from the heat flow of harmonic mappings -- from which we derive the coordinate-free filter update formula. The present article presents the algorithm with reference to a specific example -- the problem of tracking and intercepting a target, using sensors based on a moving missile.
Keyword note:Darling__R_W_R
Report ID:494
Relevance:100

Title:Intrinsic Location Parameter of a Diffusion Process
Author(s):Darling, R. W. R.; 
Date issued:Oct 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3c7k (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3c84 (PostScript)
Abstract:Suppose $X$ is a Markov diffusion process on $R^p$, or more generally on a manifold $N$. The diffusion variance of $X$ induces a semi-definite metric $\langle\cdot\mid\cdot\rangle$ on the cotangent bundle, a version of the Levi-Civita connection $\Gamma$ and a Laplace-Beltrami operator $\Delta$. We may treat $X$ as a diffusion on $N$ with generator $\xi + (1/2)\Delta$, where $\xi$ is a vector field. For sufficiently small $\delta > 0$, $X_\delta$ has an ``intrinsic location parameter'', defined to be the non-random initial value $V_0$ of a $\Gamma$-martingale $V$ terminating at $X_\delta$. It is obtained by solving a system of forward-backwards stochastic differential equations (FBSDE): a forward equation for $X$, and a backwards equation for $V$. This FBSDE is the stochastic equivalent of the heat equation (with drift $\xi$) for harmonic mappings, a well-known system of quasilinear PDE. Let $\(\phi_t: N \rightarrow N, t \geq 0\)$ be the flow of the vector field $\xi$, and let $x_t \equiv \phi_t(x_0) \in N$. Our main result is that $\exp^(-1)_(x_\delta)V_0$ can be intrinsically approximated to first order in $T_(x_\delta)N$ by $$ \nabla d\phi_\delta(x_0)(\Pi_\delta) - \int_(0)^(\delta)(\phi_(\delta - t))_(*)(\nabla d\phi_t(x_0))d\Pi_t $$ where $\Pi_t = \int_(0)^(t)(\phi_(-s))_(*)\langle\cdot\mid\cdot\rangle_(x_s)ds \in T_(x_0)N \otimes T_(x_0)N$. This is computed in local coordinates. More generally, we find an intrinsic location parameter for $\Psi(X_\delta)$, if $\Psi:N \rightarrow M$ is a $C^2$ map into a Riemannian manifold $M$. These formulas have immediate application, discussed in a separate article, to the construction of an intrinsic nonlinear analog to the Kalman Filter.
Keyword note:Darling__R_W_R
Report ID:493
Relevance:100

Title:Collision local times, historical stochastic calculus, and competing superprocesses
Author(s):Evans, S. N.; Perkins, E. A.; 
Date issued:Sep 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3f85 (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3f9q (PostScript)
Abstract:Branching measure--valued diffusion models are investigated that can be regarded as pairs of historical Brownian motions modified by a competitive interaction mechanism under which individuals from each population have their longevity or fertility adversely affected by collisions with individuals from the other population. For 3 or fewer spatial dimensions, such processes are constructed using a new fixed--point technique as the unique solution of a strong equation driven by another pair of more explicitly constructible measure--valued diffusions. This existence and uniqueness is used to establish well--posedness of the related martingale problem and hence the strong Markov property for solutions. Previous work of the authors has shown that in 4 or more dimensions models with the analogous definition do not exist. The definition of the model and its study require a thorough understanding of random measures called collision local times. These gauge the extent to which two measure--valued processes or an R^d--valued process and a measure--valued process ``collide'' as time evolves. This study and the substantial amount of related historical stochastic calculus that is developed are germane to several other problems beyond the scope of the paper. Moreover, new results are obtained on the branching particle systems imbedded in historical processes and on the existence and regularity of superprocesses with immigration, and these are also of independent interest.
Keyword note:Evans__Steven_N Perkins__E_A
Report ID:491
Relevance:100

Title:Random Brownian Scaling Identities and Splicing of Bessel Processes
Author(s):Pitman, Jim; Yor, Marc; 
Date issued:Sep 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3g74 (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3g8p (PostScript)
Abstract:An identity in distribution due to F. Knight for Brownian motion is extended in two different ways: firstly by replacing the supremum of a reflecting Brownian motion by the range of an unreflected Brownian motion, and secondly by replacing the reflecting Brownian motion by a recurrent Bessel process. Both extensions are explained in terms of random Brownian scaling transformations and Brownian excursions. The first extension is related to two different constructions of Ito's law of Brownian excursions, due to D. Williams and J.-M. Bismut, each involving back-to-back splicing of fragments of two independent three-dimensional Bessel processes. Generalizations of both splicing constructions are described which involve Bessel processes and Bessel bridges of arbitrary positive real dimension.
Pub info:Ann. Prob. 26, 1683-1702 (1998)
Keyword note:Pitman__Jim Yor__Marc
Report ID:490
Relevance:100

Title:The Standard Additive Coalescent
Author(s):Aldous, David; Pitman, Jim; 
Date issued:July 1997
Keyword note:Aldous__David_J Pitman__Jim
Report ID:489
Relevance:100

Title:Stationary Markov processes related to stable Ornstein--Uhlenbeck processes and the additive coalescent
Author(s):Evans, Steven N.; Pitman, Jim; 
Date issued:Jul 1997
Date modified:revised May 1998
http://nma.berkeley.edu/ark:/28722/bk0000n3r1z (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3r2h (PostScript)
Abstract:We consider some classes of stationary, counting--measure--valued Markov processes and their companions under time--reversal. Examples arise in the L\'evy--It\^o decomposition of stable Ornstein--Uhlenbeck processes, the large--time asymptotics of the standard additive coalescent, and extreme value theory. These processes share the common feature that points in the support of the evolving counting--measure are born or die randomly, but each point follows a deterministic flow during its life--time.
Keyword note:Evans__Steven_N Pitman__Jim
Report ID:488
Relevance:100

Title:Interactions among physical and biological variables during the upwelling period in Monterey Bay, CA.
Author(s):Service, S. K.; Rice, J. A.; Chavez, F. P.; 
Date issued:Jul 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3q89 (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3q9v (PostScript)
Abstract:We used data from moorings deployed in central California to examine the physical variables wind, PAR (photosynthetically available radiation) and temperature and the biological variable fluorescence during coastal upwelling. Variations of the multivariate techniques of principal components analysis and canonical correlation were used to extract the major modes of variability of these variables and to examine relationships among the variables. Data from both 1993 and 1994 indicate a consistent pattern of relationships among the physical variables, with NW winds and sunnier than average days leading lower than average temperatures at the mooring by 2-3 days. The relationship among the physical and biological variables was stronger in 1993 than in 1994. Higher than average fluorescence was found to lag lower than average temperatures, higher than average PAR and wind from the NW by 4, 6 and 7 days, respectively. The form of the relationship that produced maximal correlation between fluorescence and temperature was that several days of colder than average temperatures, followed by a trend to increased temperatures, was correlated with higher than average fluorescence. Higher than average fluorescence in 1993 showed maximal correlation with wind after several days of NW winds, followed by lighter winds from the SE. Relationships among physical variables and fluorescence are not as strong in 1994 as in 1993, and we hypothesize these differences to be related to differences in the strength and duration of upwelling in the two years.
Keyword note:Service__S_K Rice__John_Andrew Chavez__F_P
Report ID:487
Relevance:100

Title:Arcing the Edge
Author(s):Breiman, Leo; 
Date issued:Jun 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3b6h (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3b72 (PostScript)
Abstract:Recent work has shown that adaptively reweighting the training set, growing a classifier using the new weights, and combining the classifiers constructed to date can significantly decrease generalization error. Procedures of this type were called arcing by Breiman [1996]. The first successful arcing procedure was introduced by Freund and Schapire [1995,1996] and called Adaboost. In an effort to explain why Adaboost works, Schapire, et al [1997] derived a bound on the generalization error of a convex combination of classifiers in terms of the margin. We introduce a function called the edge, which differs from the margin only if there are more than two classes. A framework for understanding arcing algorithms is defined. In this framework, we see that the arcing algorithms currently in the literature are optimization algorithms which minimize some function of the edge. A relation is derived between the optimal reduction in the maximum value of the and the PAC concept of weak learner. Two algorithms are described which achieve the optimal reduction. Tests on both synthetic and real data case doubt on the Schapire, et al explanation.
Keyword note:Breiman__Leo
Report ID:486
Relevance:100

Title:Fast evaluation of the likelihood of an HMM: ion channel currents with filtering and colored noise
Author(s):Fredkin, Donald R.; Rice, John A.; 
Date issued:Jun 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3q5n (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3q66 (PostScript)
Abstract:Hidden Markov models have been used in the study of single-channel recordings of ion channel currents for restoration of idealized signals from noisy recordings and for estimation of kinetic parameters. A key to their effectiveness from a computational point of view is that the number of operations to evaluate the likelihood, posterior probabilities, and the most likely state sequence are proportional to the product of the square of the dimension of the state space and the length of the series. However, when the state space is quite large, computations can become infeasible. This can happen when the record has been low pass filtered and when the noise is colored. In this paper we present an approximate method that can provide very substantial reductions in computational cost at the expense of only a very small error. We describe the method and illustrate through examples the gains that can be made in evaluating the likelihood.
Keyword note:Fredkin__Donald_R Rice__John_Andrew
Report ID:485
Relevance:100

Title:Planning for the census in the year 2000: an update
Author(s):Eaton, Morris L.; Freedman, David A.; Klein, Stephen P.; Olshen, Richard A.; Wachter, Kenneth W.; Ylvisaker, Donald; 
Date issued:Jun 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3q20 (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3q3j (PostScript)
Abstract:This paper is a discussion of Census 2000, focusing on planned use of sampling techniques for non-response followup and adjustment.
Keyword note:Eaton__Morris_L Freedman__David Klein__Stephen_P Olshen__Richard_A Wachter__Kenneth Ylvisaker__Donald
Report ID:484
Relevance:100

Title:Exploring Quasi Monte Carlo for Marginal Density Approximation
Author(s):Ostland, Michael; Yu, Bin; 
Date issued:May 1997
Keyword note:Ostland__Michael_Anthony Yu__Bin
Report ID:483
Relevance:100

Title:Enumerations of trees and forests related to branching processes and random walks
Author(s):Pitman, Jim; 
Date issued:May 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3p6p (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3p77 (PostScript)
Abstract:In a Galton-Watson branching process with offspring distribution $(p_0, p_1, \ldots )$ started with $k$ individuals, the distribution of the total progeny is identical to the distribution of the first passage time to $-k$ for a random walk started at 0 which takes steps of size $j$ with probability $p_(j+1)$ for $j \ge -1$. The formula for this distribution is a probabilistic expression of the Lagrange inversion formula for the coefficients in the power series expansion of $f(z)^k$ in terms of those of $g(z)$ for $f(z)$ defined implicitly by $f(z) = z g(f(z))$. The Lagrange inversion formula is the analytic counterpart of various enumerations of trees and forests which generalize Cayley's formula $k n^(n-k-1)$ for the number of rooted forests labeled by a set of size $n$ whose set of roots is a particular subset of size $k$. These known results are derived by elementary combinatorial methods without appeal to the Lagrange formula, which is then obtained as a byproduct. This approach unifies and extends a number of known identities involving the distributions of various kinds of random trees and random forests.
Pub info:In Microsurveys in Discrete Probability edited by D. Aldous and J. Propp. DIMACS Ser. Discrete Math. Theoret. Comput. Sci..
Keyword note:Pitman__Jim
Report ID:482
Relevance:100

Title:Tree-valued Markov chains derived from Galton-Watson processes.
Author(s):Aldous, David; Pitman, Jim; 
Date issued:Feb 1997
http://nma.berkeley.edu/ark:/28722/bk0000n3p31 (PDF)
http://nma.berkeley.edu/ark:/28722/bk0000n3p4k (PostScript)
Abstract:Let $G$ be a Galton-Watson tree, i.e. the family tree of a Galton-Watson branching process. For $0 \leq u \leq 1$ let $G_u$ be the subtree of $G$ obtained by retaining each edge with probability $u$ and deleting other edges. We study the tree-valued Markov process $(G_u, 0 \leq u \leq 1)$ and an analogous process $(G^*_u, 0 \leq u \leq 1)$ in which $G^*_1$ is a critical or subcritical Galton-Watson tree conditioned to be infinite. Results simplify and are further developed in the special case of Poisson$(\mu)$ offspring distribution.
Pub info:Ann. Inst. Henri. Poincar\'e 34, 1998, 637-686
Keyword note:Aldous__David_J Pitman__Jim
Report ID:481
Relevance:100

Page: 1 2  Next