We apply robust Bayesian decision theory to improve both generative and discriminative learners under bias in class proportions in labeled training data, when the true class proportions are unknown. For the generative case, we derive an entropy-based weighting that maximizes expected log likelihood under the worst-case true class proportions. For the discriminative case, we derive a multinomial logistic model that minimizes worst-case conditional log loss. We apply our theory to the modeling of species geographic distributions from presence data, an extreme case of label bias since there is no absence data. On a benchmark dataset, we find that entropy-based weighting offers an improvement over constant estimates of class proportions, consistently reducing log loss on unbiased test data.

We study the problem of maximum entropy density estimation in the presence of known sample selection bias. We propose three bias cor- rection approaches. The first one takes advantage of unbiased sufficient statistics which can be obtained from biased samples. The second one es- timates the biased distribution and then factors the bias out. The third one approximates the second by only using samples from the sampling distri- bution. We provide guarantees for the first two approaches and evaluate the performance of all three approaches in synthetic experiments and on real data from species habitat modeling, where maxent has been success- fully applied and where sample selection bias is a significant problem.

We study the problem of modeling species geographic distributions, a critical problem in conservation biology. We propose the use of maximum-entropy techniques for this problem, specifically, sequential-update algorithms that can handle a very large number of features. We describe experiments comparing maxent with a standard distribution-modeling tool, called GARP, on a dataset containing observation data for North American breeding birds. We also study how well maxent performs as a function of the number of training examples and training time, analyze the use of regularization to avoid overfitting when the number of examples is small, and explore the interpretability of models constructed using maxent.

We develop a telecommunications architecture based on IP routers and compare it empirically to the current TDM hierarchy. The study is based on two premises: first that data traffic will continue to grow much faster than voice traffic and will be mostly IP, and second, that IP routers and networks will soon achieve the scalability and dependability necessary to provide the service quality expected of telecommunications networks. The IP architecture exploits a number of mechanisms to improve network efficiency: mesh restoration requires less spare bandwidth than SONET rings; private line services are carried as virtual leased lines, enabling more fine-grained bandwidth offerings; a voice subnetwork uses OC-48 links rather than DS-1 trunk groups, so it requires less total bandwidth to achieve the same blocking probability; and the multiplying inefficiencies of layer-by-layer routing in the TDM hierarchy are avoided. We find that an all-IP architecture could offer much greater network efficiency and considerable capital savings. We examine how technology must evolve to support such an architecture.

This paper considers the problem of paging under the assumption that the sequence of pages accessed is generated by a Markov chain. We use this model to study the fault-rate of paging algorithms. We first draw on the theory of Markov decision processes to characterize the paging algorithm that achieves optimal fault-rate on any Markov chain. Next, we address the problem of devising a paging strategy with low fault-rate for a given Markov chain. We show that a number of intuitive approaches fail. Our main result is a polynomial-time procedure that, on any Markov chain, will give a paging algorithm with fault-rate at most a constant times optimal. Our techniques show also that some algorithms that do poorly in practice fail in the Markov setting, despite known (good) performance guarantees when the requests are generated independently from a probability distribution.

Computer speech recognition has been very successful in limited domains and for isolated word recognition. However, widespread use of large-vocabulary continuous-speech recognizers is limited by the speed of current recognizers, which cannot reach acceptable error rates while running in real time. This paper shows how to harness shared memory multiprocessors, which are becoming increasingly common, to increase the speed significantly, and therefore the accuracy or vocabulary size, of a speech recognizer. To cover the necessary background, we begin with a tutorial on speech recognition. We then describe the parallelization of an existing high-quality speech recognizer, achieving a speedup of a factor of 3, 5, and 6 on 4-, 8-, and 12-processors respectively for the benchmark North American business news (NAB) recognition task.

What is the best paging algorithm if one has partial information about the possible sequences of page requests? We give a partial answer to this question by presenting the analysis of strongly competitive paging algorithms in the access graph model. This model restricts page requests so that they conform to a notion of locality of reference given by an arbitrary access graph We first consider optimal algorithms for undirected access graphs. Borodin et al. [Proc. 23rd ACM Symposium on Theory of Computing, 1991, pp. 249–259] define an algorithm, called FAR, and prove that it is within a logarithmic factor of the optimal online algorithm. We prove that FAR is in fact strongly competitive, i.e, within a constant factor of the optimum. For directed access graphs, we present an algorithm that is strongly competitive on structured program graphs—graphs that model a subset of the request sequences of structured programs.

Paul Erdös asked how dense a sequence of integers, none of which is the sum of a consecutive subsequence, can be. In other words, let $(x_{1}, \ldots ,x_m )$ be an increasing sequence of integers in $[ 1,n ]$, such that there do not exist i, j, and k, with $0 < i < j < k \leq m$ and $x_i + x_{i + 1} + \cdots + x_j = x_k $. Erdös asked if $m > n/2 + 1$ is possible. A simple argument shows that $m > 2n/3 + O(\log n)$ is impossible. Freud recently constructed a sequence with $m = 19n/36$. This note constructs a sequence with $m = 13n/24 - O(1)$ and extends the simple upper bound to show that $m > (2/3 - \epsilon )n + (\log n)$ is impossible for $\epsilon = 1/512$.

Next generation wide area networks will be connection-oriented, with data-link layer connectivity being provided by asynchronous transfer mode (ATM). For the huge existing investment in current IP networks such as the Internet to remain useful, one must devise mechanisms to carry IP traffic over ATM networks. A fundamental issue is to devise holding policies for virtual circuits carrying datagrams. The authors consider two pricing schemes, the first is a likely pricing scheme of future ATM networks, while the second is based on characteristics of current networks. For each pricing scheme, the authors devise a simple holding policy that adapts to the characteristics of the IP traffic. The authors simulate their policies on actual network traffic and find that they perform significantly better than previous policies.

When carrying Internet protocol (IP) traffic over an asynchronous transfer mode (ATM) network, the ATM adaptation layer must determine how long to hold a virtual circuit opened to carry an IP datagram. We present a formal statement of the problem and carry out a detailed empirical examination of various holding time policies taking into account the issue of network pricing. We offer solutions for two natural pricing models, the first being a likely pricing model of future ATM networks, while the second is based on characteristics of current networks. For each pricing model, we study a variety of simple nonadaptive policies as well as easy to implement policies that adapt to the characteristics of the IP traffic. We simulate our policies on actual network traffic, and find that policies based on least recently used (LRU) perform well, although the best adaptive policies provide a significant improvement over LRU.>

Next generation wide area network are very likely to use connection-oriented protocols such as Asynchronous Transfer Mode (ATM). For the huge existing investment in current IP networks such as the Internet to remain useful, me must devise mechanisms to carry IP traffic over connection-oriented networks. A basic issue is to devise holding policies for virtual circuits carrying datagrams. In this paper we consider two variants of the paging problem that arise in the design of such holding policies. In the IP-paging problem the page inter-request times are chosen according to independent distributions. For this model we construct a very simple deterministic algorithm whose page fault rate is at most 5 times that of the best online algorithm (that knows the inter-request time distributions). We also show that some natural algorithms for this problem do not have constant competitive ratio. In distributional paging the inter-request time distributions may be dependent, and hence any probabilistic model of page request sequences can be represented. We construct a simple randomized algorithm whose page fault rate is at most 4 times that of the best online algorithm.>

In this paper we study two problems that can be viewed as on-line games on a dynamic bipartite graph. The first problem is on-line load balancing with preemption. A centralized scheduler must assign tasks to servers, processing online a sequence of task arrivals and departures. Each task is restricted to run on some subset of the servers. The scheduler attempts to keep the load well-balanced. If preemptive reassignments are dissallowed, Azar, Broder and Karlin [3] proved a lower bound of \\Omega\\Gamma p n) on the ratio between the maximum load achieved by an on-line algorithm and the optimum off-line maximum load. We show that this ratio can be greatly reduced by an efficient scheduler using only a small amount of rescheduling. We then apply these ideas to network flow. Cheriyan and Hagerup [6] introduced an on-line game on a bipartite graph as a fundamental step in improving algorithms for computing the maximum flow in networks. They described a randomized strategy to play the game. ...

The all-pairs shortest-paths problem in weighted graphs is investigated. An algorithm—the Hidden-Paths Algorithm—that finds these paths in time $O(m^ * n + n^2 \log n)$, where $m^ * $ is the number of edges participating in shortest paths, is presented. The algorithm is a practical substitute for Dijkstra’s algorithm. It is argued that $m^ * $ is likely to be small in practice since $m^ * = O(n\log n)$ with high probability for many probability distributions on edge weights. An $\Omega (mn)$ lower bound on the running time of any path-comparison-based algorithm for the all-pairs shortest-paths problem is also proved. Path-comparison-based algorithms form a natural class containing the Hidden-Paths Algorithm, as well as the algorithms of E. W. Dijkstra [Numer. Math., 1 (1959), pp. 269–271] and R. W. Floyd [Comm. ACM, 5 (1962), p. 345]. Lastly, generalized forms of the shortest-paths problem are considered, and it is shown that many of the standard shortest-paths algorithms are effective in this more general setting.

This paper considers the problem of paging under the assumption that the sequence of pages accessed is generated by a Markov chain. The authors use this model to study the fault-rate of paging algorithms, a quantity of interest to practitioners. They first draw on the theory of Markov decision processes to characterize the paging algorithm that achieves optimal fault-rate on any Markov chain. They address the problem of efficiently devising a paging strategy with low fault-rate for a given Markov chain. They show that a number of intuitively good approaches fail. Their main result is an efficient procedure that, on any Markov chain, will give a paging algorithm with fault-rate at most a constant times optimal. Their techniques also show that some algorithms that do poorly in practice fail in the Markov setting, despite known (good) performance guarantees when the requests are generated independently from a probability distribution.>

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, each step of the random walk a “controller” can, with a certain small probability, fix the next step, thus introducing a bias. We analyze the extent to which the bias can affect the limit behavior of the walk. The controller is assumed to associate a real, nonnegative, “benefit” with each state, and to strive to maximize the long-term expected benefit. We derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.

The all-pairs shortest paths problem in weighted graphs is investigated. An algorithm called the hidden paths algorithm, which finds these paths in time O(m*+n n/sup 2/ log n), where m* is the number of edges participating in shortest paths, is presented. It is argued that m* is likely to be small in practice, since m*=O(n log n) with high probability for many probability distributions on edge weights. An Omega (mn) lower bound on the running time of any path-comparison-based algorithm for the all-pairs shortest paths problem is proved.>