Boarding or holding in the Emergency Department (ED) reduces capacity of the ED and delays patients from receiving specialized care. Estimating accurately the number of admissions from the ED can help determine approp...
详细信息
ISBN:
(纸本)9780769549132;9781467346511
Boarding or holding in the Emergency Department (ED) reduces capacity of the ED and delays patients from receiving specialized care. Estimating accurately the number of admissions from the ED can help determine appropriate level of staffing to reduce holding. We propose a randomized non-linear regression algorithm, RT-KGERS, to estimate the number of admissions a week in advance. We also devise features based on cyclical patterns found with a Fast Fourier Transform analysis on the hospital admission data. We evaluate the accuracy and efficiency of RT-KGERS and three existing algorithms in a dataset provided by a local hospital. We then compare our features with related features. Initial experimental results from RT-KGERS encouraged the hospital and us to conduct a live trial study which yielded similar levels of accuracy using RT-KGERS and the six features we devised.
A trend in machine learning is the application of existing algorithms to ever-larger datasets. Support Vector Machines (SVM) have been shown to be very effective, but have been difficult to scale to large-data problem...
详细信息
ISBN:
(纸本)9780769549132;9781467346511
A trend in machine learning is the application of existing algorithms to ever-larger datasets. Support Vector Machines (SVM) have been shown to be very effective, but have been difficult to scale to large-data problems. Some approaches have sought to scale SVM training by approximating and parallelizing the underlying quadratic optimization problem. This paper pursues a different approach. Our algorithm, which we call Sampled SVM, uses an existing SVM training algorithm to create a new SVM training algorithm. It uses randomized data sampling to better extend SVMs to large data applications. Experiments on several datasets show that our method is faster than and comparably accurate to both the original SVM algorithm it is based on and the Cascade SVM, the leading data organization approach for SVMs in the literature. Further, we show that our approach is more amenable to parallelization than Cascade SVM.
In this letter, fractional calculus is used to propose the fractional entropy (FE) and the fractional mutual information (FMI) as the new forms of the information measure in a generalized Euclidean metric space. Being...
详细信息
In this letter, fractional calculus is used to propose the fractional entropy (FE) and the fractional mutual information (FMI) as the new forms of the information measure in a generalized Euclidean metric space. Being position-related and causal, FE and FMI are natural extensions and more generalized forms of Shannon entropy and mutual information, respectively. (C) 2012 Elsevier B.V. All rights reserved.
When a matrix A with n columns is known to be well-approximated by a linear combination of basis matrices B-1, ... , B-p, we can apply A to a random vector and solve a linear system to recover this linear combination....
详细信息
When a matrix A with n columns is known to be well-approximated by a linear combination of basis matrices B-1, ... , B-p, we can apply A to a random vector and solve a linear system to recover this linear combination. The same technique can be used to obtain an approximation to A(-1). A basic question is whether this linear system is well-conditioned. This is important for two reasons: a well-conditioned system means (1) we can invert it and (2) the error in the reconstruction can be controlled. In this paper, we show that if the Gram matrix of the B-j's is sufficiently well-conditioned and each B-j has a high numerical rank, then n alpha p log(2) n will ensure that the linear system is well-conditioned with high probability. Our main application is probing linear operators with smooth pseudodifferential symbols such as the wave equation Hessian in seismic imaging [L. Demanet et al., Appl. Comput. Harmonic Anal., 32 (2012), pp. 155-168]. We also demonstrate numerically that matrix probing can produce good preconditioners for inverting elliptic operators in variable media.
In this paper, we study the important problems of message routing, sorting, and selection in a radio network. A radio network consists of stations where each station is a hand-held device. We consider a single-hop rad...
详细信息
In this paper, we study the important problems of message routing, sorting, and selection in a radio network. A radio network consists of stations where each station is a hand-held device. We consider a single-hop radio network where it is assumed that each station is within the transmission range of every other station. Let RN(p, k) stand for a single-hop network that has p stations and k communication channels. The best known prior algorithm for sorting takes 4n/k + o (n/k) broadcast rounds on a RN(p, k). In this paper, we present a randomized algorithm that takes only 3n/k + o (n/k) broadcast rounds with high probability. For the selection problem, we present a randomized selection algorithm that takes O (p/k) rounds on a RN(p, k) with high probability. The best known prior algorithms for the n/p-relations routing problem take nearly 2n/k time slots (i.e., broadcast rounds). An important open question has been if there exist algorithms that take only close to n/k time slots. Note that a trivial lower bound for routing is n/k. The existence of such algorithms will be highly relevant, especially in emergencies and time-critical situations. In this paper, we answer this question by presenting a randomized algorithm that takes nearly n/k rounds on the average. We also present a deterministic algorithm that takes nearly n/k rounds. These routing algorithms are also shown to be energy efficient. (C) 2012 Elsevier Inc. All rights reserved.
We study an abstract setting, where the basic information units (called "superpackets") do not fit into a single packet, and are therefore spread over multiple packets. We assume that a superpacket is useful...
详细信息
We study an abstract setting, where the basic information units (called "superpackets") do not fit into a single packet, and are therefore spread over multiple packets. We assume that a superpacket is useful only if the number of its delivered packets is above a certain threshold. Our focus of attention is communication link ingresses, where large arrival bursts result in dropped packets. The algorithmic question we address is which packets to drop so as to maximize goodput. Specifically, suppose that each superpacket consists of k packets, and that a superpacket can be reconstructed if at most beta . k of its packets are lost, for some given parameter 0 <= beta < 1. We present a simple online distributed randomized algorithm in this model, and prove that in any scenario, its expected goodput is Omega(OPT/(k root(1 - beta)sigma)), where OPT denotes the best possible goodput by any algorithm, and sigma denotes the size of the largest burst (the bound can be improved as a function of burst-size variability). We also analyze the effect of buffers on goodput under the assumption of fixed burst size, and show that in this case, when the buffer is not too small, our algorithm can attain, with high probability, (1 - epsilon) goodput utilization for any epsilon > 0. Finally, we present some simulation results that demonstrate that the behavior of our algorithm in practice is far better than our worst-case analytical bounds. (C) 2012 Elsevier B.V. All rights reserved.
Model predictive (MP) control as a novel active queue management (AQM) algorithm in dynamic computer networks is proposed. According to the predicted future queue length in the data buffer, early packets at the router...
详细信息
Model predictive (MP) control as a novel active queue management (AQM) algorithm in dynamic computer networks is proposed. According to the predicted future queue length in the data buffer, early packets at the router are dropped reasonably by the MPAQM controller so that the queue length reaches the desired value with minimal tracking error. The drop probability is obtained by optimizing the network performance. Further, randomized algorithms are applied to analyze the robustness of MPAQM successfully, and also to provide the stability domain of systems with uncertain network parameters. The performances of MPAQM are evaluated through a series of simulations in NS2. The simulation results show that the MPAQM algorithm outperforms RED, PI, and REM algorithms in terms of stability, disturbance rejection, and robustness. (C) 2011 ISA. Published by Elsevier Ltd. All rights reserved.
In this note we introduce a new randomized algorithm for counting triangles in graphs. We show that under mild conditions, the estimate of our algorithm is strongly concentrated around the true number of triangles. Sp...
详细信息
In this note we introduce a new randomized algorithm for counting triangles in graphs. We show that under mild conditions, the estimate of our algorithm is strongly concentrated around the true number of triangles. Specifically, let G be a graph with it vertices, triangles and let Delta be the maximum number of triangles an edge of G is contained in. Our randomized algorithm colors the vertices of G with N = 1/p colors uniformly at random, counts monochromatic triangles, i.e., triangles whose vertices have the same color, and scales that count appropriately. We show that if p >= max(Delta logn/t . root log n/t) then for any constant epsilon > 0 our unbiased estimate T is concentrated around its expectation, i.e., Pr{[T - E vertical bar T vertical bar] >= epsilon E vertical bar T vertical bar} = o(1). Finally, our algorithm is amenable to being parallelized. We present a simple MAPREDUCE implementation of our algorithm. (C) 2011 Elsevier B.V. All rights reserved.
The paper describes a simple and fast randomized test for equality of grammar-compressed strings. The thorough running time analysis is done by applying a logarithmic cost measure. (C) 2012 Elsevier B.V. All rights re...
详细信息
The paper describes a simple and fast randomized test for equality of grammar-compressed strings. The thorough running time analysis is done by applying a logarithmic cost measure. (C) 2012 Elsevier B.V. All rights reserved.
We show that the threshold c(r,k) (in terms of the average degree of the graph) for appearance of a k-core in a random r-partite r-uniform hypergraph G(r,n,m) is the same as for a random r-uniform hypergraph with cn/r...
详细信息
We show that the threshold c(r,k) (in terms of the average degree of the graph) for appearance of a k-core in a random r-partite r-uniform hypergraph G(r,n,m) is the same as for a random r-uniform hypergraph with cn/r edges without the r-partite restriction, where r, k >= 2. In both cases, the average degree is c. The case r, k = 2 was analyzed in Botelho et al. (2007) [4] but the general case r >= 3, k >= 2 is still open. Besides the proof for the general case, we have also provided a simpler proof for the case r, k = 2. This problem was provided without a proof (but with strong experimental evidence) in the analysis of the algorithm presented in Botelho et al. (2007) pi. This algorithm constructs a family of minimal perfect hash functions based on random r-partite r-uniform hypergraphs with an empty k-core subgraph, for k >= 2. For an input key set S with m keys, the family of minimal perfect hash functions generated by the algorithm can be stored in O(m) bits, where the hidden constant is within a factor of two from the information theoretical lower bound. (C) 2011 Published by Elsevier B.V.
暂无评论