Space Efficient Probabilistic Graphical Models and Privacy Sensitive Construction of Agent Organizations

(1)在个人和移动设备中，决策经常使用僵化、简单化的规则。例如，一个电话号码可能会因为收到来自该号码的垃圾电话的报告而被列入黑名单，从而导致来自该号码的未来呼叫被过滤。该规则忽略了报告本身可能是垃圾邮件，从而导致不良行为的可能性。贝叶斯网络(BNS)是一种基于知识的系统，能够权衡复杂的不确定上下文信息，可以帮助用户做出更智能的决策。BNS用概率表量化的图形结构对因果关系进行编码。然而，运行BNS所需的内存与每个变量的直接原因数n呈指数关系。当n较大时，所需的内存可能会超过智能手机或传感器的内存需求，从而限制了BN在此类设备中的部署。为了克服这一问题，本研究试图将运行BN所需的内存需求降低到n的线性。NAT模型在n中线性存储，并承诺比现有技术更准确地逼近BN概率表。将研究如何用NAT建模来最好地逼近BN，以及如何在线性存储器中推理NAT建模的BN。它的成功将极大地减少与BN进行概率推理所需的内存，使软件工程师能够在普适计算设备中部署BN，并在前所未有的应用范围内实现智能决策。(2)协同智能系统(称为智能体)非常适合于监控复杂设备或供应链中的协同设计等应用。代理人的合作通常是通过一个组织进行的。所谓的连接树(JT)就是这样一种组织，并且被发现优于通常使用的伪树。代理可以嵌入丰富的知识，例如关于设备组件的知识，这些知识是组件供应商专有的并且需要保持私密。然而，构建JT组织的常见方法受到了此类隐私的侵犯。为了提高这些智能系统中的隐私，本研究研究了如何在不丢失隐私的情况下构建JT组织，以及在不可避免的情况下以最小的损失构建JT组织。灵活的JT组织结构将设计为具有隐私保护，以处理系统组成中的变化，例如，当添加组件及其代理时。将调查完全自主的、保护隐私的JT建造的可行性，即不使用外部指定的领导代理。这项研究的成功完成将填补基于JT组织的代理系统中的隐私漏洞。强大的隐私保障，再加上JT组织其他优越的计算特性，将使这些代理系统得到更广泛的应用。

(1) Rigid, simplistic rules are often used for decision making in personal and mobile devices. For example, a phone number may be placed on a black list, due to the report of a spam call from it, causing future calls from the number to be filtered. The rule ignores the possibility that the report may itself be a spam, leading to undesirable actions. Bayesian Networks (BNs), knowledge based systems capable of weighing complex uncertain context information, can aid users with more intelligent decisions. BNs encode causal relations with graphical structures quantified by probability tables. However, memory needed to run BNs is exponential in the number n of direct causes per variable. When n is large, the required memory may exceed that of a smart phone or sensor, limiting deployment of BNs in such devices.To overcome that, this research seeks to reduce memory requirement for running BNs to being linear in n. It explores innovatively a recent modeling technique, Non-impeding noisy-AND Tree (NAT), to approximate probability tables in BNs. NAT models take the memory linear in n and promise to approximate BN probability tables more accurately than existing techniques. How to best approximate BNs with NAT modeling and how to reason with NAT modeled BNs within linear memory will be investigated. Its success will dramatically reduce memory required for probabilistic reasoning with BNs, allow software engineers to deploy BNs in pervasive computing devices, and enable intelligent decisions in an unprecedented range of applications. (2) Cooperative intelligent systems (called agents) are well suited for applications such as monitoring complex equipment or collaborative design in supply chains. Agent cooperation is often through an organization. The so-called Junction Tree (JT) is one such organization and is found superior than the often used pseudotrees. An agent can embed rich knowledge, e.g., about an equipment component, that is proprietary to component vendor and needs to remain private. However, common methods to construct JT organizations suffer from breach of such privacy. As a result, vendors run the risk of losing intellectual properties.To improve privacy in these intelligent systems, this research studies how to construct JT organizations without privacy loss if possible and with the minimum loss if unavoidable. Flexible JT organization construction will be devised with privacy protection to handle changes in system composition, e.g., when a component and its agent are added. Feasibility of fully autonomous, privacy protecting JT construction, i.e., without using an externally specified leader agent, will be investigated. Successful completion of this research will close a loop hole on privacy in agent systems based on JT organizations. The strong privacy guarantee, coupled with other superior computational properties of JT organizations, will make these agent systems more widely applicable.