{"id":31,"date":"2015-08-17T09:30:10","date_gmt":"2015-08-17T09:30:10","guid":{"rendered":"http:\/\/grupo.us.es\/gapsc\/?page_id=31"},"modified":"2020-03-04T13:10:33","modified_gmt":"2020-03-04T13:10:33","slug":"graphical-models","status":"publish","type":"page","link":"https:\/\/grupo.us.es\/gapsc\/graphical-models\/","title":{"rendered":"Graphical Models and Expectation Propagation"},"content":{"rendered":"

Overview<\/h2>\n

Graphical models (GM) are an exiting way of studying and solving problems. In a nutshell, they allow for a visual and systematic representation of variables, that encode some information, and the relation between them. This relation can be represented by an edge between variables (undirected graphs), meaning that they are related, or with a directed edge (directed graphs), meaning which variables influence other ones, or by new\u00a0elements in the GM denoted as factors, that encode the relation between variables connected to them (factor graphs). GM are specially useful when variables are random and the relation are statistical ones. The structure of the resulting graph can be quite exploited to reduce the computational complexity in, e.g. computing the marginal value for a variable. A wide family of the algorithms for statistical GM work using a message interchange between variables and factors in the graph until convergente. The belief propagation (BP) algorithm is a well known one, that yields the exact solution when no loops are present in the graph.<\/p>\n

Factor graphs (FG) are usually applied to digital communications, since it is easy to incorporate the knowledge on the system through factors. Two particular cases are the graph for channel decoding and the channel equalization problems. In channel coding every parity check is represented by a factor. In low-density parity-check (LDPC) codes, as the length of the transmitted frame increases the graph behaves as non-cyclic, and the BP allows for an optimal channel decoding with complexity linear with the frame length. In equalization, graphs are used to represent the systems a chain where at any time the observed variable depends on just a finite number of previous unobserved ones, resulting in a so-called hidden Markov model (HMM). In the case of discrete unobserved variables, the BCJR algorithm yields the symbol maximum a posteriori probabilities.<\/p>\n

The BP in channel coding performs near capacity for quite long frames, but it degrades for finite length words, being this the case for a wide range of communications systems. The problem here is that loops become shorter. We have explore solving the graph facing the existence of cycles by approximating the optimal solution using the expectation propagation (EP). This algorithm permits approximating a full graph by another simpler one. Our solutions allows for a trade off between complexity and performance. In the limit, when complexity is increased, we proved that the EP yields the ML decoder.<\/p>\n

In other digital communications systems, we found that the information available can be easily included when expectation propagation. In this sense we investigated approximations available for discrete HMM, when the BCJR is unaffordable due to the large number of states. This idea can be extended to many other scenarios with quite dense graphs. In particular we have explored the application to (turbo) equalization.<\/p>\n

Involved Members<\/h2>\n

Juan J. Murillo Fuentes,\u00a0Fernando P\u00e9rez-Cruz,\u00a0Rafael Boloix Tortosa, Eva Arias de Reyna,\u00a0Pablo M. Olmos,\u00a0Luis Salamanca and Irene Santos Vel\u00e1zquez.<\/p>\n

Publications<\/h2>\n

Journals<\/h3>\n