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.