Active Learning for Level Set Estimation Using Randomized Straddle Algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915038586994688 |
|---|---|
| author | Inatsu, Yu Takeno, Shion Kutsukake, Kentaro Takeuchi, Ichiro |
| author_facet | Inatsu, Yu Takeno, Shion Kutsukake, Kentaro Takeuchi, Ichiro |
| contents | Level set estimation (LSE), the problem of identifying the set of input points where a function takes value above (or below) a given threshold, is important in practical applications. When the function is expensive-to-evaluate and black-box, the \textit{straddle} algorithm, which is a representative heuristic for LSE based on Gaussian process models, and its extensions having theoretical guarantees have been developed. However, many of existing methods include a confidence parameter $β^{1/2}_t$ that must be specified by the user, and methods that choose $β^{1/2}_t$ heuristically do not provide theoretical guarantees. In contrast, theoretically guaranteed values of $β^{1/2}_t$ need to be increased depending on the number of iterations and candidate points, and are conservative and not good for practical performance. In this study, we propose a novel method, the \textit{randomized straddle} algorithm, in which $β_t$ in the straddle algorithm is replaced by a random sample from the chi-squared distribution with two degrees of freedom. The confidence parameter in the proposed method has the advantages of not needing adjustment, not depending on the number of iterations and candidate points, and not being conservative. Furthermore, we show that the proposed method has theoretical guarantees that depend on the sample complexity and the number of iterations. Finally, we confirm the usefulness of the proposed method through numerical experiments using synthetic and real data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_03144 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Active Learning for Level Set Estimation Using Randomized Straddle Algorithms Inatsu, Yu Takeno, Shion Kutsukake, Kentaro Takeuchi, Ichiro Machine Learning Level set estimation (LSE), the problem of identifying the set of input points where a function takes value above (or below) a given threshold, is important in practical applications. When the function is expensive-to-evaluate and black-box, the \textit{straddle} algorithm, which is a representative heuristic for LSE based on Gaussian process models, and its extensions having theoretical guarantees have been developed. However, many of existing methods include a confidence parameter $β^{1/2}_t$ that must be specified by the user, and methods that choose $β^{1/2}_t$ heuristically do not provide theoretical guarantees. In contrast, theoretically guaranteed values of $β^{1/2}_t$ need to be increased depending on the number of iterations and candidate points, and are conservative and not good for practical performance. In this study, we propose a novel method, the \textit{randomized straddle} algorithm, in which $β_t$ in the straddle algorithm is replaced by a random sample from the chi-squared distribution with two degrees of freedom. The confidence parameter in the proposed method has the advantages of not needing adjustment, not depending on the number of iterations and candidate points, and not being conservative. Furthermore, we show that the proposed method has theoretical guarantees that depend on the sample complexity and the number of iterations. Finally, we confirm the usefulness of the proposed method through numerical experiments using synthetic and real data. |
| title | Active Learning for Level Set Estimation Using Randomized Straddle Algorithms |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2408.03144 |