检索结果-内蒙古大学图书馆

IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Giambartolomei, Giordano Mallmann-Trenn, Frederik Saona, Raimundo King's College London United Kingdom Institute of Science and Technology Austria Austria

Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. This model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon's distribution. Alijani et al. (2020) designed a single-threshold algorithms achieving a ratio of 1/2 when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single-threshold, a ratio of 1/2 is actually achievable for several larger classes of horizon distributions, with the largest being known as the G class in reliability theory. Moreover, we extend this result to its dual, the G class (which includes the decreasing hazard rate class), and to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms. Copyright © 2024, The Authors. All rights reserved.

关键词： expectation maximization algorithm

Maximum principle for stochastic optimal control problem under convex expectation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Xiaojuan Hu, Mingshang Department of Mathematics Qilu Normal University Jinan250200 China Zhongtai Securities Institute for Financial Studies Shandong University Shandong Jinan250100 China

In this paper, we study a stochastic optimal control problem under a type of consistent convex expectation dominated by G-expectation. By the separation theorem for convex sets, we get the representation theorems for this convex expectation and conditional convex expectation. Based on these results, we obtain the variational equation for cost functional by weak convergence and discretization methods. Furthermore, we establish the maximum principle which is sufficient under usual convex assumptions. Finally, we study the linear quadratic control problem by using the obtained maximum *** Codes 93E20, 60H10, 35K15 Copyright © 2024, The Authors. All rights reserved.

关键词： expectation maximization algorithm

Jointly Modeling and Clustering Tensors in High Dimensions

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Cai, Biao Zhang, Jingfei Sun, Will Wei Department of Management Sciences City University of Hong Kong Hong Kong Goizueta Business School Emory University United States Daniels School of Business Purdue University United States

We consider the problem of jointly modeling and clustering populations of tensors by introducing a high-dimensional tensor mixture model with heterogeneous covariances. To effectively tackle the high dimensionality of tensor objects, we employ plausible dimension reduction assumptions that exploit the intrinsic structures of tensors such as low-rankness in the mean and separability in the covariance. In estimation, we develop an efficient high-dimensional expectation-conditional-maximization (HECM) algorithm that breaks the intractable optimization in the M-step into a sequence of much simpler conditional optimization problems, each of which is convex, admits regularization and has closed-form updating formulas. Our theoretical analysis is challenged by both the non-convexity in the EM-type estimation and having access to only the solutions of conditional maximizations in the M-step, leading to the notion of dual non-convexity. We demonstrate that the proposed HECM algorithm, with an appropriate initialization, converges geometrically to a neighborhood that is within statistical precision of the true parameter. The efficacy of our proposed method is demonstrated through comparative numerical experiments and an application to a medical study, where our proposal achieves an improved clustering accuracy over existing benchmarking methods. © 2021, CC BY.

关键词： expectation maximization algorithm

Causal Temporal Regime Structure Learning

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Rahmani, Abdellah Frossard, Pascal LTS4 EPFL Lausanne Switzerland

Understanding causal relationships in multivariate time series is essential for predicting and controlling dynamic systems in fields like economics, neuroscience, and climate science. However, existing causal discovery methods often assume stationarity, limiting their effectiveness when time series consist of sequential regimes, consecutive temporal segments with unknown boundaries and changing causal structures. In this work, we firstly introduce a framework to describe and model such time series. Then, we present CASTOR, a novel method that concurrently learns the Directed Acyclic Graph (DAG) for each regime while determining the number of regimes and their sequential arrangement. CASTOR optimizes the data log-likelihood using an expectation-maximization algorithm, alternating between assigning regime indices (expectation step) and inferring causal relationships in each regime (maximization step). We establish the identifiability of the regimes and DAGs within our framework. Extensive experiments show that CASTOR consistently outperforms existing causal discovery models in detecting different regimes and learning their DAGs across various settings, including linear and nonlinear causal relationships, on both synthetic and real world datasets. © 2023, CC BY.

关键词： expectation maximization algorithm

Achieving Margin maximization Exponentially Fast via Progressive Norm Rescaling

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Wang, Mingze Min, Zeping Wu, Lei School of Mathematical Sciences Peking University Beijing China Center for Machine Learning Research Peking University Beijing China

In this work, we investigate the margin-maximization bias exhibited by gradient-based algorithms in classifying linearly separable data. We present an in-depth analysis of the specific properties of the velocity field associated with (normalized) gradients, focusing on their role in margin maximization. Inspired by this analysis, we propose a novel algorithm called Progressive Rescaling Gradient Descent (PRGD) and show that PRGD can maximize the margin at an exponential rate. This stands in stark contrast to all existing algorithms, which maximize the margin at a slow polynomial rate. Specifically, we identify mild conditions on data distribution under which existing algorithms such as gradient descent (GD) and normalized gradient descent (NGD) provably fail in maximizing the margin efficiently. To validate our theoretical findings, we present both synthetic and real-world experiments. Notably, PRGD also shows promise in enhancing the generalization performance when applied to linearly non-separable datasets and deep neural networks. Copyright © 2023, The Authors. All rights reserved.

关键词： expectation maximization algorithm

Gibbs optimal design of experiments

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Overstall, Antony M. Holloway-Brown, Jacinta McGree, James M. School of Mathematical Sciences University of Southampton SouthamptonSO17 1BJ United Kingdom School of Computer and Mathematical Sciences University of Adelaide Adelaide5005 Australia School of Mathematical Sciences Queensland University of Technology Brisbane4001 Australia

Bayesian optimal design is a well-established approach to planning experiments. A distribution for the responses, i.e. a statistical model, is assumed which is dependent on unknown parameters. A utility function is then specified giving gain in information in estimating the true values of the parameters, using the Bayesian posterior distribution. A Bayesian optimal design is given by maximising expectation of the utility with respect to the distribution implied by statistical model and prior distribution for the true parameter values. The approach accounts for the experimental aim, via specification of the utility, and of assumed sources of uncertainty. However, it is predicated on the statistical model being correct. Recently, a new type of statistical inference, known as Gibbs inference, has been proposed. This is Bayesian-like, i.e. uncertainty for unknown quantities is represented by a posterior distribution, but does not necessarily require specification of a statistical model. The resulting inference is less sensitive to misspecification of the statistical model. This paper introduces Gibbs optimal design: a framework for optimal design of experiments under Gibbs inference. A computational approach to find designs in practice is outlined and the framework is demonstrated on exemplars including linear models, and experiments with count and time-to-event responses. © 2023, CC BY.

关键词： expectation maximization algorithm

Improved Parallel algorithm for Non-Monotone Submodular maximization under Knapsack Constraint

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Tran, Tan D. Pham, Canh V. Ha, Dung T.K. Pham, Phuong N.H. ORLab Faculty of Computer Science Phenikaa University Hanoi Viet Nam Faculty of Information Technology VNU University of Engineering and Technology Hanoi Viet Nam Faculty of Information Technology Ho Chi Minh City University of Industry and Trade Ho Chi Minh Viet Nam

This work proposes an efficient parallel algorithm for non-monotone submodular maximization under a knapsack constraint problem over the ground set of size n. Our algorithm improves the best approximation factor of the existing parallel one from 8 + ϵ to 7 + ϵ with O(log n) adaptive complexity. The key idea of our approach is to create a new alternate threshold algorithmic framework. This strategy alternately constructs two disjoint candidate solutions within a constant number of sequence rounds. Then, the algorithm boosts solution quality without sacrificing the adaptive complexity. Extensive experimental studies on three applications, Revenue maximization, Image Summarization, and Maximum Weighted Cut, show that our algorithm not only significantly increases solution quality but also requires comparative adaptivity to state-of-the-art algorithms. © 2024, CC BY.

关键词： expectation maximization algorithm

Non-stationary and Sparsely-correlated Multi-output Gaussian Process with Spike-and-Slab Prior

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wang, Xinming Li, Yongxiang Yue, Xiaowei Wu, Jianguo Department of Industrial Engineering and Management Peking University China Department of Industrial Engineering and Management Shanghai Jiaotong University China Department of Industrial Engineering Tsinghua University China

Multi-output Gaussian process (MGP) is commonly used as a transfer learning method to leverage information among multiple outputs. A key advantage of MGP is providing uncertainty quantification for prediction, which is highly important for subsequent decision-making tasks. However, traditional MGP may not be sufficiently flexible to handle multivariate data with dynamic characteristics, particularly when dealing with complex temporal correlations. Additionally, since some outputs may lack correlation, transferring information among them may lead to negative transfer. To address these issues, this study proposes a non-stationary MGP model that can capture both the dynamic and sparse correlation among outputs. Specifically, the covariance functions of MGP are constructed using convolutions of time-varying kernel functions. Then a dynamic spike-and-slab prior is placed on correlation parameters to automatically decide which sources are informative to the target output in the training process. An expectation-maximization (EM) algorithm is proposed for efficient model fitting. Both numerical studies and a real case demonstrate its efficacy in capturing dynamic and sparse correlation structure and mitigating negative transfer for high-dimensional time-series data. Finally, a mountain-car reinforcement learning case highlights its potential application in decision making problems. © 2024, CC BY.

关键词： expectation maximization algorithm

Robust Object Detection and Tracking Using a Space-Temporal Mutual Feedback Scheme

学校读者我要写书评

暂无评论

Robust Object Detection and Tracking Using a Space-Temporal ...

2008 IEEE International Symposium on Knowledge Acquisition and Modeling Workshop(KAM 2008)

作者： Xuchao Li College of Information Science and Media Jinggangshan University Ji’an,ChinaSuxuan Bian College of Nursing Jinggangshan University Ji’an,China

A statistical object detection and tracking mutual feedback scheme,combining Gaussian mixture model (GMM) based on principal component analysis (PCA) and expectation maximization (EM) Kalman filter algorithm,is proposed in this *** space object detection stage,PCA provides compact and decorrelated feature space,the tracked object feature is statistically represented as GMM in RGB color space,objects are detected by maximum a posteriori (MAP) *** temporal tracking stage,the tracked object is determined by the Bhattacharyya similarity measurement,the object position of consecutive frame is predicted by EM Kalman filter *** integration of object detection and tracking spatio-temporal mutual feedback scheme can decrease the accumulation *** have applied the proposed method to object detection and tracking under the partial occlusion and the changes of moving speed with encouraging results.

关键词： object detection and tracking Kalman filter expectation maximization algorithm feedback