Vis enkel innførsel

dc.contributor.authorYazidi, Anis
dc.contributor.authorGranmo, Ole-Christoffer
dc.contributor.authorOommen, John
dc.contributor.authorGoodwin, Morten
dc.date.accessioned2015-02-18T10:29:32Z
dc.date.accessioned2017-03-03T11:41:08Z
dc.date.available2015-02-18T10:29:32Z
dc.date.available2017-03-03T11:41:08Z
dc.date.issued2014
dc.identifier.citationIEEE Transactions on Cybernetics 2014, 44(11):2202-2220language
dc.identifier.issn2168-2267
dc.identifier.urihttps://hdl.handle.net/10642/4092
dc.description.abstractStochastic point location (SPL) deals with the problem of a learning mechanism (LM) determining the optimal point on the line when the only input it receives are stochastic signals about the direction in which it should move. One can differentiate the SPL from the traditional class of optimization problems by the fact that the former considers the case where the directional information, for example, as inferred from an Oracle (which possibly computes the derivatives), suffices to achieve the optimization—without actually explicitly computing any derivatives. The SPL can be described in terms of a LM (algorithm) attempting to locate a point on a line. The LM interacts with a random environment which essentially informs it, possibly erroneously, if the unknown parameter is on the left or the right of a given point. Given a current estimate of the optimal solution, all the reported solutions to this problem effectively move along the line to yield updated estimates which are in the neighborhood of the current solution.1 This paper proposes a dramatically distinct strategy, namely, that of partitioning the line in a hierarchical tree-like manner, and of moving to relatively distant points, as characterized by those along the path of the tree. We are thus attempting to merge the rich fields of stochastic optimization and data structures. Indeed, as in the original discretized solution to the SPL, in one sense, our solution utilizes the concept of discretization and operates a uni-dimensional controlled random walk (RW) in the discretized space, to locate the unknown parameter. However, by moving to nonneighbor points in the space, our newly proposed hierarchical stochastic searching on the line (HSSL) solution performs such a controlled RW on the discretized space structured on a superimposed binary tree. We demonstrate that the HSSL solution is orders of magnitude faster than the original SPL solution proposed by - ommen. By a rigorous analysis, the HSSL is shown to be optimal if the effectiveness (or credibility) of the environment, given by $p$ , is greater than the golden ratio conjugate. The solution has been both analytically solved and simulated, and the results obtained are extremely fascinating, as this is the first reported use of time reversibility in the analysis of stochastic learning. The learning automata extensions of the scheme are currently being investigated.language
dc.language.isoenlanguage
dc.publisherIEEElanguage
dc.relation.urihttp://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6742611
dc.subjectControlled random walklanguage
dc.subjectDiscretized learninglanguage
dc.subjectLearning automatalanguage
dc.subjectStochastic-point problemlanguage
dc.subjectTime reversibilitylanguage
dc.titleA novel strategy for solving the stochastic point location problem using a hierarchical searching schemelanguage
dc.typeJournal article
dc.typePeer reviewedlanguage
dc.date.updated2015-02-18T10:29:32Z
dc.description.versionpublishedVersionlanguage
dc.identifier.doihttp://dx.doi.org/10.1109/TCYB.2014.2303712
dc.identifier.cristin1166754


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel