論文

査読有り
2020年

Annealing by Increasing Resampling

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
  • Naoya Higuchi
  • ,
  • Yasunobu Imamura
  • ,
  • Takeshi Shinohara
  • ,
  • Kouichi Hirata
  • ,
  • Tetsuji Kuboyama

11996 LNCS
開始ページ
71
終了ページ
92
記述言語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1007/978-3-030-40014-9_4
出版者・発行元
Springer

Annealing by Increasing Resampling (AIR, for short) is a stochastic hill-climbing optimization algorithm that evaluates the objective function for resamplings with increasing size. At the beginning stages, AIR makes state transitions like a random walk, because it uses small resamplings for which evaluation has large error at high probability. At the ending stages, AIR behaves like a local search because it uses large resamplings very close to the entire sample. Thus AIR works similarly as the conventional Simulated Annealing (SA, for short). As a rationale for AIR approximating SA, we show that both AIR and SA can be regarded as a hill-climbing algorithm according to objective function evaluation with stochastic fluctuations. The fluctuation in AIR is explained by the probit, while in SA by the logit. We show experimentally that the logit can be replaced with the probit in MCMC, which is a basis of SA. We also show experimental comparison of SA and AIR for two optimization problems, sparse pivot selection for dimension reduction, and annealing-based clustering. Strictly speaking, AIR must use resampling independently performed at each transition trial. However, it has been demonstrated by experiments that reuse of resampling within a certain number of times can speed up optimization without losing the quality of optimization. In particular, the larger the samples used for evaluation, the more remarkable the superiority of AIR is in terms of speed with respect to SA.

リンク情報
DOI
https://doi.org/10.1007/978-3-030-40014-9_4
DBLP
https://dblp.uni-trier.de/rec/conf/icpram/HiguchiISHK19
Scopus
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85079553108&origin=inward
Scopus Citedby
https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85079553108&origin=inward
URL
https://dblp.uni-trier.de/conf/icpram/2019s
URL
https://dblp.uni-trier.de/db/conf/icpram/icpram2019s.html#HiguchiISHK19
ID情報
  • DOI : 10.1007/978-3-030-40014-9_4
  • ISSN : 0302-9743
  • eISSN : 1611-3349
  • DBLP ID : conf/icpram/HiguchiISHK19
  • SCOPUS ID : 85079553108

エクスポート
BibTeX RIS