Sie sind hier:



Approximate aggregation of Markovian models using alternating least squares

Peter Buchholz, Jan Kriege

Performance Evaluation, Volume 73, 2014.



State based analysis of Markovian models is faced with the problem of state space explosion. To handle huge state spaces often compositional modeling and aggregation of components are used. Exact aggregation resulting in exact transient or stationary results is only possible in some cases, when the Markov process is lumpable. Therefore approximate aggregation is often applied to reduce the state space. Several approximate aggregation methods exist which are usually based on heuristics.
This paper presents a new aggregation approach for Markovian components which computes aggregates that minimize the difference according to some algebraically defined function which describes the difference between the component and the aggregate. If the difference becomes zero, aggregation is exact, which means that component and aggregate are indistinguishable in the sense that transient and stationary results in any environment are identical. For the computation of aggregates, an alternating least squares approach is presented which tries to minimize the norm-wise difference between the original component and the aggregate. Algorithms to compute aggregates are also introduced and the quality of the approximation is evaluated by means of several examples.


Compositional modeling; Aggregation; Markov models; Non-negative least squares; Matrix factorization


	 author = {Peter Buchholz and Jan Kriege}, 
	 title = {{Approximate aggregation of Markovian models using alternating least squares}}, 
	 journal = {Performance Evaluation}, 
	 note = {Special Issue on the 9th International Conference on Quantitative Evaluation of Systems}, 
	 volume = {73}, 
	 pages = {73 - 90}, 
	 year = {2014}, 
	 issn = {0166-5316}, 
	 doi = {10.1016/j.peva.2013.09.001}, 
	 url = {http://dx.doi.org/10.1016/j.peva.2013.09.001}