Paper of the day – Clustering problems

#paperoftheday

Title:
On the price of explainability for some clustering problems Venue: International Conference on Machine Learning (ICML), 2021

Authors:
Eduardo Sany Laber, Lucas Murtinho

Abstract:
The price of explainability for a clustering task can be defined as the unavoidable loss, in terms of the objective function, if we force the final partition to be explainable. Here, we study this price for the following clustering problems: k-means, k-medians, k-centers and maximum-spacing. We provide upper and lower bounds for a natural model where explainability is achieved via decision trees. For the k-means and k-medians problems our upper bounds improve those obtained by [Dasgupta et. al, ICML 20] for low dimensions. Another contribution is a simple and efficient algorithm for building explainable clusterings for the k-means problem. We provide empirical evidence that its performance is better than the current state of the art for decision-tree based explainable clustering.

More in:
http://proceedings.mlr.press/v139/laber21a.html

Paper of the day – Computational narrative blending based on planning

#paperoftheday

Title:
Computational Narrative Blending Based on Planning

Venue:
International Conference on Entertainment Computing (ICEC), 2021

Authors:
Edirlei Soares de Lima, Bruno Feijó, Antonio L. Furtado

Abstract:
Inspired by conceptual blending models and considering plot generation as a plan- generation problem, this paper proposes a robust method that reuses existing stories to generate new narrative variants. This method generates variants that combine episodes extracted and adapted from different stories that share the same narrative structure. By combining a plan validation algorithm with a basic narrative structure, our method guarantees the logical coherence and general plot structure of the generated narratives. We also propose a new tool to assist amateur/professional writers to visualize all narrative variants created from a set of existing stories. Our experiments created novel, coherent and structured narratives by blending and adapting episodes from old chivalry romance pieces of work and some modern adventure videogames.

More in:
https://doi.org/10.1007/978-3-030-89394-1_22

Paper of the day – Analysis of a many-objective optimization

#paperoftheday

Tittle:

Analysis of a many-objective optimization approach for identifying microservices from legacy systems

Venue:

Empirical Software Engineering volume 27, Article number: 51 (2022)

Authors: Wesley K. G. Assunção, Thelma Elita Colanzi, Luiz Carvalho, Alessandro Garcia, Juliana Alves Pereira, Maria Julia de Lima, Carlos Lucena

Abstract:

The expensive maintenance of legacy systems leads companies to migrate such systems to modern architectures. Microservice architectural style has become a trend to modernize monolithic legacy systems. A microservice architecture consists of small, autonomous, and highly-independent services communicating by using lightweight network protocols. To support the designing of microservice architectures, recent studies have proposed either single or multi-objective approaches. In order to improve the effectiveness of existing approaches, we introduced toMicroservices that is a many-objective search-based approach to aid the identification of boundaries among services. In previous studies, we have focused on a qualitative evaluation of the applicability and adoption of the proposed approach from a practical point of view, thus the optimization process itself has not been investigated in depth. In this paper, we extend our previous work by performing a more in-depth analysis of our many-objective approach for microservice identification. We compare our approach against a baseline approach based on a random search using a set of performance indicators widely used in the literature of many-objective optimization. Our results are validated through a real-world case study. The study findings reveal that (i) the criteria optimized by our approach are interdependent and conflicting; and (ii) all candidate solutions lead to better performance indicators in comparison to random search. Overall, the proposed many-objective approach for microservice identification yields promising results, which shed light on insights for further improvements.

More in:

https://link.springer.com/article/10.1007/s10664-021-10049-7