III: Small: Collaborative Research: Explaining Unsupervised Learning: Combinatorial Optimization Formulations, Methods and Applications

集群是一种常见的机器学习和数据挖掘技术，它获取实例/记录/事物的集合并将它们分成组。它被用于多种领域，包括社交网络（寻找社区）、生物学（创建分类法）和神经科学（寻找大脑中感兴趣的区域）。已经存在许多聚类算法，但这些算法并不总能解释聚类。该奖项解决了向各种利益相关者（包括数据科学家、领域科学家和公众）描述聚类算法结果的问题。解释这些算法的结果将使利益相关者更好地理解它们，并允许它们在需要透明度的具有挑战性和敏感的领域中使用。使用标签等易于理解的辅助信息以主动的形式进行说明。该项目将由三个相互交织的任务组成。第一个将开发易于理解的机制来解释聚类，而第二个将允许人类通过询问查询来与解释进行交互。最后，第三个任务将对任务一生成的解释附加稳定性、信任度和正确性的衡量标准。由于不需要标记数据，无监督学习领域非常受欢迎，并且存在许多可以处理各种数据类型的算法：图像、图形、文档、空间和时间数据。许多领域都有首选/广泛接受的聚类算法。然而，大多数算法仅提供将实例/对象分组为具有有限描述的集群。描述和/或解释解决方案的工作在监督学习环境中已经很受欢迎，但在无监督环境中研究不足。 该奖项通过离散组合优化公式探索这些新颖的解释问题。这样的表述有助于开发需要可解释（因此离散）结果的解释、最佳可能的解释（不是任何合理的解释），并有助于实施复杂的约束以使解释符合人类的期望。这项研究将利用理论计算机科学中的大量工作，并使用声明性范例中的工具，例如 ILP 求解器和约束编程语言。这些工具可以轻松修改配方，这是一个理想的特性，因为不同的领域可能需要不同的解释变化。这些技术的实用性将通过其在社交网络和基因组数据等多个领域的应用来证明，并由该领域的两名领域专家进行评估。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Clustering is a common machine learning and data mining technique which takes a collection of instances/records/things and divides them into groups. It is used in a large variety of domains including social networks (to find communities), biology (to create taxonomies) and neuroscience (to find regions of interest in the brain). There are many clustering algorithms already in existence, but these algorithms do not always explain the clustering. This award addresses the problem of describing the clustering algorithm results to a variety of stakeholders including data scientists, domain scientists and the general public. Explaining the results of these algorithms will allow them to be better understood by stakeholders and allow their use in challenging and sensitive domains where transparency is required. Explanations are given in an initiative form using easy to understand auxiliary information such as tags. This project will consist of three inter-twined tasks. The first will develop easy to understand mechanisms to explain a clustering, whilst the second will allow a human to interact with the explanation by asking queries about it. Finally the third task will attach measure of stability, trust and correctness to the explanations generated from task one.The area of unsupervised learning is immensely popular due to the lack of need for labeled data and there exist many algorithms that can work on a variety of data types: images, graphs, documents, spatial and temporal data. Many domains have a preferred/well-accepted clustering algorithm. However, most algorithms provide just a grouping of the instances/objects into clusters with limited description. The work on describing and/or explaining a solution has gained popularity in the supervised learning context but is under-studied in the unsupervised context. This award explores these novel explanation problems through discrete combinatorial optimization formulations. Such formulations help in developing explanations requiring interpretable (hence discrete) results, best possible explanations (not any plausible explanation) and in enforcing complex constraints to make explanations match human expectations. This research will leverage much work in theoretical computer science and use tools from declarative paradigms such as ILP solvers and constraint programming languages. Such tools allow for easy modifications of formulations, a desirable trait as different domains may need different variations in explanation. The usefulness of the techniques will be demonstrated through their applications to several domains including social networks and genomic data and evaluated by two domain experts in the area.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.