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

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

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.