One of the most important queries in knowledge compilation is weighted model counting (WMC), which has been applied to probabilistic inference on various models, such as Bayesian networks. In practical situations on inference tasks, the model's parameters have uncertainty because they are often learned from data, and thus we want to compute the degree of uncertainty in the inference outcome. One possible approach is to regard the inference outcome as a random variable by introducing distributions for the parameters and evaluate the variance of the outcome. Unfortunately, the tractability of computing such a variance is hardly known. Motivated by this, we consider the problem of computing the variance of WMC and investigate this problem's tractability. First, we derive a polynomial time algorithm to evaluate the WMC variance when the input is given as a structured d-DNNF. Second, we prove the hardness of this problem for structured DNNFs, d-DNNFs, and FBDDs, which is intriguing because the latter two allow polynomial time WMC algorithms. Finally, we show an application that measures the uncertainty in the inference of Bayesian networks. We empirically show that our algorithm can evaluate the variance of the marginal probability on real-world Bayesian networks and analyze the impact of the variances of parameters on the variance of the marginal.

Neurosymbolic systems can satisfy logical constraints during learning without achieving the intended concept-label correspondence; this is a problem known as reasoning shortcuts. We formalize reasoning shortcuts as a constraint satisfaction problem and investigate under which conditions concept mappings are uniquely determined by the constraints. We prove that a discrimination property (requiring that no valid concept mapping can be transformed into another valid mapping by swapping two concept values) is necessary for shortcut-freeness under bijective mappings, but demonstrate via a counterexample that it is insufficient even when the constraint graph is connected. We develop an ASP-based algorithm that verifies whether a given constraint set uniquely determines the intended concept mapping, with proven soundness and completeness. When shortcuts are detected, a greedy repair algorithm eliminates them by augmenting the constraint set, converging in at most k iterations, where k is the number of alternative valid mappings. We further provide a complexity classification: deciding shortcut-freeness is coNP-complete, counting shortcuts is #P-complete, and finding minimal repairs is NP-hard. We also establish sample complexity bounds showing that logarithmically many label queries suffice for disambiguation in favorable cases, while querying all ambiguous positions suffices in the worst case. Experiments across eight benchmark domains validate our approach.

Knowledge compilation is a method of transforming knowledge into a compressed and tractable form for permitting more efficient operations. For Boolean functions, numerous representations have been proposed that enhance succinctness and tractability. In this paper, we introduce a new representation named structured Decomposable And-Sum Circuit (st-DASC), which employs AND and SUM nodes with signed edges, in place of the standard AND and OR nodes with unsigned edges. Notably, incorporating negative signs permits polytime logical negation. By following a knowledge compilation map, we show that st-DASCs are more succinct than Sentential Decision Diagrams (SDDs) while maintaining support for every operation on the knowledge compilation map that SDD supports. Furthermore, st-DASCs are even more succinct than structured d-DNNFs (st-d-DNNFs), which are more succinct than SDDs although they support fewer operations than SDDs. Accordingly, st-DASCs break the traditional trade-off between succinctness and tractability over SDDs and st-d-DNNFs.

A knowledge compilation map analyzes tractable operations in Boolean function representations and compares their succinctness. This enables the selection of appropriate representations for different applications. In the knowledge compilation map, all representation classes are subsets of the negation normal form (NNF). However, Boolean functions may be better expressed by a representation that is different from that of the NNF subsets. In this study, we treat tensor trains as Boolean function representations and analyze their succinctness and tractability. Our study is the first to evaluate the expressiveness of a tensor decomposition method using criteria from knowledge compilation literature. Our main results demonstrate that tensor trains are more succinct than ordered binary decision diagrams (OBDDs) and support the same polytime operations as OBDDs. Our study broadens their application by providing a theoretical link between tensor decomposition and existing NNF subsets.

Evaluating network reliability is crucial for designing communication infrastructures, particularly for such next-generation networks as 6 G, which require extremely high reliability levels, often reaching seven 9's (99.99999 %). However, network reliability evaluation is computationally tough, making it computationally intractable to achieve accurate results for large-scale networks within a reasonable time. Consequently, existing methods either sacrifice computational efficiency or lack guaranteed error bounds. This paper presents an efficient approximation method for network reliability evaluation that guarantees that the approximation error remains within a specified bound. Our proposed method first determines the maximum degree of simultaneous link failures that can be safely ignored without exceeding the bound. With binary decision diagrams, our method efficiently computes both the lower and upper bounds of network reliability. We validate our method through numerical experiments on real-world networks. Our method, which outperformed existing methods by several orders of magnitude, evaluated a network with 434 links in just 7 seconds; an existing method required more than 28 hours.

We present an efficient construction of variable-to-fixed-length (VF) codes under conditions where encoding delay is allowed. We introduce a generalized form of parsetree sets representing a class of codes broader than the almost instantaneous VF (AIVF) codes, which are the conventional VF codes that allow one symbol of an encoding delay. Using Huffman trees, we can optimally construct the codes and guarantee that the compression efficiency is at least compatible with Huffman codes. Numerical evaluations show that we can make efficient VF codes that outperform Huffman codes even for input sources that are disadvantageous to conventional VF codes.

This paper presents an optimal construction ofN-bit-delay almost instantaneous fixed-to-variable-length (AIFV) codes, the general form of binary codes we can make when finite bits of decoding delay are allowed. The presented method enables us to optimize lossless codes among a broader class of codes compared to the conventional FV and AIFV codes. The paper first discusses the problem of code construction, which contains some essential partial problems, and defines three classes of optimality to clarify how far we can solve the problems. The properties of the optimal codes are analyzed theoretically, showing the sufficient conditions for achieving the optimum. Then, we propose an algorithm for constructingN-bit-delay AIFV codes for given stationary memory-less sources. The optimality of the constructed codes is discussed both theoretically and empirically. They showed shorter expected code lengths whenN≥ 3 than the conventional AIFV-mand extended Huffman codes. Moreover, in the random numbers simulation, they performed higher compression efficiency than the 32-bit-precision range codes under reasonable conditions.

Modern society is underpinned by several network infrastructures, such as telecommunications and transportation. In these network infrastructures, every node pair should remain connected even if some network components fail. Thus, network operators must accurately evaluate the reliability between each node pair and effectively enhance unreliable pairs. Unfortunately, network reliability evaluation is known to be computationally difficult even for a single pair, and no accurate and efficient algorithm for all pairs has been developed. This paper introduces the problem of 2-NR++, evaluating network reliability for all node pairs, and proposes an efficient and exact algorithm. Unlike the previous algorithms, the proposed algorithm constructs only one data structure to compute the reliability of all node pairs. Numerical evaluation using real network benchmarks shows that our algorithm is faster than the state-of-the-art by an order of magnitude; e.g., our algorithm solves 2-NR++ in less than one hour even for a large network with 240 nodes, whereas the state-of-the-art requires more than one day. As an application of our algorithm, we also introduce a link augmentation problem to improve the least unreliable pair. We demonstrate that our algorithm reduces the computation time by around 30–90 times compared to the state-of-the-art.

As the reliability requirements increase for communication networks, e.g., the seven 9’s reliability for 6G, network operators must evaluate the reliability of their networks more accurately. Since public-communication networks are designed to be less prone to large-scale outages, their (un)reliability should be evaluated per outage scale (the number of disconnected nodes). Traditionally, scale-wise unreliability has been evaluated approximately or requires several hours due to its computational hardness. This paper proposes an efficient algorithm that exactly evaluates scale-wise unreliability by leveraging the given reliability requirements for computation acceleration. We first define a sub-problem that computes the probability of disconnecting x or more nodes and introduce a core algorithm that solves this problem with binary decision diagrams. The core algorithm is used to evaluate the scale-wise unreliability according to the given requirements, e.g., the outage probability or outage scale. The time complexity is theoretically analyzed, and its performance is experimentally verified. The proposed algorithm successfully evaluates in 82 minutes large benchmark networks with 400 links and the seven 9’s requirements; the state-of-the-art algorithm fails to evaluate it within 12 hours.

Since machine learning technologies are being used in various practical situations, models with merely low prediction errors might not be satisfactory; prediction errors occurring with a low probability might yield dangerous results in some applications. Therefore, there are attempts to achieve an ML model whose input-output pairs are guaranteed to satisfy given constraints. Among such attempts, many previous works chose the approach of modifying the outputs of an ML model at the inference time to satisfy the constraints. Such a strategy is handy because we can control its output without expensive training or fine-tuning. However, it is unclear whether using constraints only in the inference time degrades a model's predictive performance. This paper analyses how the generalization error bounds change when we only put constraints in the inference time. Our main finding is that a class of loss functions preserves the relative generalization error, i.e., the difference in generalization error compared with the best model will not increase by imposing constraints at the inference time on multi-class classification. Some popular loss functions preserve the relative error, including the softmax cross-entropy loss. On the other hand, we also show that some loss functions do not preserve relative error when we use constraints. Our results suggest the importance of choosing a suitable loss function when we only use constraints in the inference time.

Binary decision diagram (BDD) and zero-suppressed binary decision diagram (ZDD) are data structures to represent a family of (sub)sets compactly, and it can be used as succinct indexes for a family of sets. To build BDD/ZDD representing a desired family of sets, there are many transformation operations that take BDDs/ZDDs as inputs and output BDD/ZDD representing the resultant family after performing operations such as set union and intersection. However, except for some basic operations, the worst-time complexity of taking such transformation on BDDs/ZDDs has not been extensively studied, and some contradictory statements about it have arisen in the literature. In this paper, we show that many transformation operations on BDDs/ZDDs, including all operations for families of sets that appear in Knuth's book, cannot be performed in worst-case polynomial time in the size of input BDDs/ZDDs. This refutes some of the folklore circulated in past literature and resolves an open problem raised by Knuth. Our results are stronger in that such blow-up of computational time occurs even when the ordering, which has a significant impact on the efficiency of treating BDDs/ZDDs, is chosen arbitrarily.

In communication networks, the significance of an outage is measured mainly by its scale (number of disconnected nodes). To avoid serious outages, operators design their networks so that the reliability meets the specification for each outage scale, where the more significant the outage, the less likely it is to occur. Although scale-wise unreliability has been evaluated with rough approximation, sixth-generation (6G) mobile communication requires more accurate reliability evaluation with seven 9's accuracy. Unfortunately, accurate scale-wise reliability evaluation is a computationally very tough problem, so no previous literature has studied evaluation methods rigorous enough for 6G. This paper proposes an efficient algorithm to exactly compute the probability for each number of disconnected nodes. Our algorithm performs the scale-wise unreliability evaluation in a dynamic programming manner without redundant repetition for each outage scale. Numerical experiments using real network topologies show its great efficiency, e.g., our algorithm computes exact probabilities for every outage scale in just two hours for a network with nearly 200 links. We also provide several interesting insights on the reliability of real topologies from the scale-wise perspective, since our work is the first to present the scale-wise unreliability of real large topologies.

Contemporary society survives on several network infrastructures, such as communication and transportation. These network infrastructures are required to keep all nodes connected, although these nodes are occasionally disconnected due to failures. Thus, the expected number of connected node pairs (ECP) during an operation period is a reasonable reliability measure in network design. However, no work has studied ECP due to its computational hardness; we have to solve the reliability evaluation problem, which is a computationally tough problem, for O(n2) times where n is the number of nodes in a network. This paper proposes an efficient method that exactly computes ECP. Our method performs dynamic programming just once without explicit repetition for each node pair and obtains an exact ECP value weighted by the number of users at each node. A thorough complexity analysis reveals that our method is faster than an existing reliability evaluation method, which can be transferred to ECP computation, by O(n). Numerical experiments using real topologies show great efficiency; e.g., our method computes the ECP of an 821-link network in ten seconds; the existing method cannot complete it in an hour. This paper also presents two applications: critical link identification and optimal resource (e.g., a server) placement.

Network reliability, that is, the probability of con-necting specified nodes under link failures, is a key metric of network infrastructure. Because network reliability evaluation is a computationally heavy task, past research has relied on unre-alistically simple failure models such as the independent failure model, wherein each link fails stochastically and independently, ignoring large-scale failures such as disasters, or the deterministic-correlated failure model, wherein all links within a disaster area always fail. However, actual networks follow the probabilistic-correlated (PC) failure model, wherein links in a disaster area fail stochastically with respect to each disaster. This paper proposes an efficient method to accurately compute network reliability under the PC model. Following a conventional method for the independent model, the proposed method uses binary decision diagrams (BDDs) to efficiently handle an exponential number of failure states. Additionally, it employs a probabilistic inference technique to support probabilistic correlation, which is represented as another BDD for integration with the conventional method. The computational complexity was theoretically analyzed, and its performance was experimentally verified; it can compute the network reliability within 1 h for a large network with nearly 200 links and 100 potential disasters.

Since modern society largely depends on several network infrastructures such as telecommunications and various types of power, the reliability of networked systems needs to be accurately evaluated. Traditionally, network reliability has been evaluated on the assumption that the availability of each link is precisely given. However, in reality, it may be given with a degree of uncertainty, e.g., with variance, which must be propagated into the network reliability. To the best of our knowledge, no literature has investigated this issue because, since even computing the reliability itself belongs to a computationally tough class, computing the variance seems much harder.This paper proposes an efficient algorithm to compute the variance of the network reliability given the variance in link availability. We experimentally verify the performance of our algorithm and show that it can compute the variance of network reliability within 0.1 seconds for real topologies with nearly 200 links. We also perform extensive analyses on the variance of network reliability and reveal that network reliability tends to be accurate and that the variance in reliability does not significantly exceed the variance in link availability. Even when some links have a substantial variance in availability, the impact on network reliability is marginal.

Machine learning technologies have been used in a wide range of practical systems.In practical situations, it is natural to expect the input-output pairs of a machine learning model to satisfy some requirements.However, it is difficult to obtain a model that satisfies requirements by just learning from examples.A simple solution is to add a module that checks whether the input-output pairs meet the requirements and then modifies the model's outputs. Such a module, which we call a {\em concurrent verifier} (CV), can give a certification, although how the generalizability of the machine learning model changes using a CV is unclear. This paper gives a generalization analysis of learning with a CV. We analyze how the learnability of a machine learning model changes with a CV and show a condition where we can obtain a guaranteed hypothesis using a verifier only in the inference time.We also show that typical error bounds based on Rademacher complexity will be no larger than that of the original model when using a CV in multi-class classification and structured prediction settings.

The differentiable implementation of logic yields a seamless combination of symbolic reasoning and deep neural networks. Recent research, which has developed a differentiable framework to learn logic programs from examples, can even acquire reasonable solutions from noisy datasets. However, this framework severely limits expressions for solutions, e.g., no function symbols are allowed, and the shapes of clauses are fixed. As a result, the framework cannot deal with structured examples. Therefore we propose a new framework to learn logic programs from noisy and structured examples, including the following contributions. First, we propose an adaptive clause search method by looking through structured space, which is defined by the generality of the clauses, to yield an efficient search space for differentiable solvers. Second, we propose for ground atoms an enumeration algorithm, which determines a necessary and sufficient set of ground atoms to perform differentiable inference functions. Finally, we propose a new method to compose logic programs softly, enabling the system to deal with complex programs consisting of several clauses. Our experiments show that our new framework can learn logic programs from noisy and structured examples, such as sequences or trees. Our framework can be scaled to deal with complex programs that consist of several clauses with function symbols.

Network reliability, i.e., the probability of connecting a set of specified nodes under stochastic link failure, is a key indicator of network infrastructure, such as communication and power. Since network reliability evaluation is a computationally heavy task, several methods have been proposed to efficiently perform it. However, modern network infrastructures follow the client-server model, where many clients are served independently, so we have to evaluate the network reliability for every set consisting of the servers and each client. This evaluation process involves repetitive evaluations while changing the set, which imposes a heavy burden on network operators. This paper proposes a method that efficiently performs network reliability evaluation for the client-server model. Since our method is designed to evaluate reliability for multiple clients without explicit repetition, the computational complexity does not increase compared to the case where existing methods evaluate reliability for a single client. Numerical experiments using datasets of various topologies, including real communication networks, reveal great efficiency. Our method is more than 100 times faster than an existing method that requires repeated evaluation, e.g., it takes only 27 seconds to compute the reliability for 670 clients on a large network with 821 links.

Exact cover refers to the problem of finding subfamily F of a given family of sets S whose universe is D, where F forms a partition of D. Knuth’s Algorithm DLX is a state-of-the-art method for solving exact cover problems. Since DLX’s running time depends on the cardinality of input S, it can be slow if S is large. Our proposal can improve DLX by exploiting a novel data structure, DanceDD, which extends the zero-suppressed binary decision diagram (ZDD) by adding links to enable efficient modifications of the data structure. With DanceDD, we can represent S in a compressed way and perform search in linear time with the size of the structure by using link operations. The experimental results show that our method is an order of magnitude faster when the problem is highly compressed.

We propose a novel method of automatic sentence alignment from noisy parallel documents.We first formalize the sentence alignment problem as the independent predictions of spans in the target document from sentences in the source document.We then introduce a total optimization method using integer linear programming to prevent span overlapping and obtain non-monotonic alignments.We implement cross-language span prediction by fine-tuning pre-trained multilingual language models based on BERT architecture and train them using pseudo-labeled data obtained from unsupervised sentence alignment method.While the baseline methods use sentence embeddings and assume monotonic alignment, our method can capture the token-to-token interaction between the tokens of source and target text and handle non-monotonic alignments.In sentence alignment experiments on English-Japanese, our method achieved 70.3 F 1 scores, which are +8.0 points higher than the baseline method.In particular, our method improved by +53.9 F 1 scores for extracting non-parallel sentences.Our method improved the downstream machine translation accuracy by 4.1 BLEU scores when the extracted bilingual sentences are used for fine-tuning a pre-trained Japanese-to-English translation model. 1

Computing the similarity between two data points plays a vital role in many machine learning algorithms. Metric learning has the aim of learning a good metric automatically from data. Most existing studies on metric learning for tree-structured data have adopted the approach of learning the tree edit distance. However, the edit distance is not amenable for big data analysis because it incurs high computation cost. In this paper, we propose a new metric learning approach for tree-structured data with pq-grams. The pq-gram distance is a distance for ordered labeled trees, and has much lower computation cost than the tree edit distance. In order to perform metric learning based on pq-grams, we propose a new differentiable parameterized distance, weighted pq-gram distance. We also propose a way to learn the proposed distance based on Large Margin Nearest Neighbors (LMNN), which is a well-studied and practical metric learning scheme. We formulate the metric learning problem as an optimization problem and use the gradient descent technique to perform metric learning. We empirically show that the proposed approach not only achieves competitive results with the state-of-the-art edit distance-based methods in various classification problems, but also solves the classification problems much more rapidly than the edit distance-based methods.

We present a novel supervised word alignment method based on cross-language span prediction.We first formalize a word alignment problem as a collection of independent predictions from a token in the source sentence to a span in the target sentence.Since this step is equivalent to a SQuAD v2.0 style question answering task, we solve it using the multilingual BERT, which is fine-tuned on manually created gold word alignment data.It is nontrivial to obtain accurate alignment from a set of independently predicted spans.We greatly improved the word alignment accuracy by adding to the question the source token's context and symmetrizing two directional predictions.In experiments using five word alignment datasets from among Chinese, Japanese, German, Romanian, French, and English, we show that our proposed method significantly outperformed previous supervised and unsupervised word alignment methods without any bitexts for pretraining.For example, we achieved 86.7 F1 score for the Chinese-English data, which is 13.3 points higher than the previous state-of-the-art supervised method. 1

With the increase in scale and complexity of ICT systems, their operation increasingly requires automatic recovery from failures. Although it has become possible to automatically detect anomalies and analyze root causes of failures with current methods, making decisions on what commands should be executed to recover from failures still depends on manual operation, which is quite time-consuming. Toward automatic recovery, we propose a method of estimating recovery commands by using Seq2Seq, a neural network model. This model learns complex relationships between logs obtained from equipment and recovery commands that operators executed in the past. When a new failure occurs, our method estimates plausible commands that recover from the failure on the basis of collected logs. We conducted experiments using a synthetic dataset and realistic OpenStack dataset, demonstrating that our method can estimate recovery commands with high accuracy.

Subgraph enumeration is a fundamental task in computer science. Since the number of subgraphs can be large, some enumeration algorithms exploit compressed representations for efficiency. One such representation is the Zero-suppressed Binary Decision Diagram (ZDD). ZDDs can represent the set of subgraphs compactly and support several poly-time queries, such as counting and random sampling. Researchers have proposed efficient algorithms to construct ZDDs representing the set of subgraphs under several constraints, which yield fruitful results in many applications. Recently, Zero-suppressed Sentential Decision Diagrams (ZSDDs) have been proposed as variants of ZDDs. ZSDDs can be smaller than ZDDs when representing the same set of subgraphs. However, efficient algorithms to construct ZSDDs are known only for specific types of subgraphs: matchings and paths. We propose a novel framework to construct ZSDDs representing sets of subgraphs under given constraints. Using our framework, we can construct ZSDDs representing several sets of subgraphs such as matchings, paths, cycles, and spanning trees. We show the bound of sizes of constructed ZSDDs by the branch-width of the input graph, which is smaller than that of ZDDs by the path-width. Experiments show that our methods can construct ZSDDs faster than ZDDs and that the constructed ZSDDs are smaller than ZDDs when representing the same set of subgraphs.

The Sentential Decision Diagram (SDD) is a tractable representation of Boolean functions that subsumes the famous Ordered Binary Decision Diagram (OBDD) as a strict subset. SDDs are attracting much attention because they are more succinct than OBDDs, as well as having canonical forms and supporting many useful queries and transformations such as model counting and Apply operation. In this paper, we propose a more succinct variant of SDD named Variable Shift SDD (VS-SDD). The key idea is to create a unique representation for Boolean functions that are equivalent under a specific variable substitution. We show that VS-SDDs are never larger than SDDs and there are cases in which the size of a VS-SDD is exponentially smaller than that of an SDD. Moreover, despite such succinctness, we show that numerous basic operations that are supported in polytime with SDD are also supported in polytime with VS-SDD. Experiments confirm that VS-SDDs are significantly more succinct than SDDs when applied to classical planning instances, where inherent symmetry exists.

Masaaki Nishino, Sho Takase, Tsutomu Hirao, Masaaki Nagata. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Communication networks are an essential infrastructure and must be designed carefully to ensure high reliability. Identifying a fully reliable design is, however, computationally very tough since it requires that a reliability evaluation, which is known to be #P-complete, be repeated an exponential number of times. Existing studies, therefore, attempt to avoid exact optimization to reduce the computational burden by applying heuristics. Due to the importance of communication networks and to better assess the accuracy of heuristic approaches, exact optimization remains a key goal. This paper proposes an exact method for two network design problems: reliability maximization under budget constraints and cost minimization with assurance of reliability. Our method employs a common idea to solve these problems, i.e., a best-first search algorithm that runs on decision diagrams. Our method employs just a single binary decision diagram (BDD) to compute the reliability for any solution and is also used as the basis of a novel heuristic function, called the cost-aware BDD heuristic function, as a search guide. Numerical experiments show that our method scales well; it successfully optimizes a network with 189 links. In addition, our method reveals the poor performance of existing heuristic approaches; a well-known existing heuristic method is shown to yield a solution that offers less than half the optimal reliability.

Shinsaku Sakaue, Tsutomu Hirao, Masaaki Nishino, Masaaki Nagata. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). 2018.

Exact cover is the problem of finding subfamilies, S*, of a family of sets, S, over universe U, where S* forms a partition of U. It is a popular NP-hard problem appearing in a wide range of computer science studies. Knuth's algorithm DLX, a backtracking-based depth-first search implemented with the data structure called dancing links, is known as state-of-the-art for finding all exact covers. We propose a method to accelerate DLX. Our method constructs a Zero-suppressed Binary Decision Diagram (ZDD) that represents the set of solutions while running depth-first search in DLX. Constructing ZDDs enables the efficient use of memo cache to speed up the search. Moreover, our method has a virtue that it outputs ZDDs; we can perform several useful operations with them. Experiments confirm that the proposed method is up to several orders of magnitude faster than DLX.

The Zero-suppressed Sentential Decision Diagram (ZSDD) is a recentlydiscovered tractable representation of Boolean functions. ZSDD subsumes theZero-suppressed Binary Decision Diagram (ZDD) as a strict subset, andsimilar to ZDD, it can perform several useful operations like model countingand Apply operations. We propose a top-down compilation algorithmfor ZSDD that represents sets of specific graph substructures, e.g.,matchings and simple paths of a graph. We experimentally confirm that theproposed algorithm is faster than other construction methods includingbottom-up methods and top-down methods for ZDDs, and the resulting ZSDDsare smaller than ZDDs representing the same graph substructures. We alsoshow that the size constructed ZSDDs can be bounded by the branch-width of thegraph. This bound is tighter than that of ZDDs.

To analyze the limitations and the future directions of the extractive summarization paradigm, this paper proposes an Integer Linear Programming (ILP) formulation to obtain extractive oracle summaries in terms of ROUGE n .We also propose an algorithm that enumerates all of the oracle summaries for a set of reference summaries to exploit F-measures that evaluate which system summaries contain how many sentences that are extracted as an oracle summary.Our experimental results obtained from Document Understanding Conference (DUC) corpora demonstrated the following: (1) room still exists to improve the performance of extractive summarization; (2) the F-measures derived from the enumerated oracle summaries have significantly stronger correlations with human judgment than those derived from single oracle summaries.

The Sentential Decision Diagram (SDD) is a prominent knowledge representation language that subsumes the Ordered Binary Decision Diagram (OBDD) as a strict subset. Like OBDDs, SDDs have canonical forms and support bottom-up operations for combining SDDs, but they are more succinct than OBDDs. In this paper we introduce an SDD variant, called the Zero-suppressed Sentential Decision Diagram (ZSDD). The key idea of ZSDD is to employ new trimming rules for obtaining a canonical form. As a result, ZSDD subsumes the Zero-suppressed Binary Decision Diagram (ZDD) as a strict subset. ZDDs are known for their effectiveness on representing sparse Boolean functions. Likewise, ZSDDs can be more succinct than SDDs when representing sparse Boolean functions. We propose several polytime bottom-up operations over ZSDDs, and a technique for reducing ZSDD size, while maintaining applicability to important queries. We also specify two distinct upper bounds on ZSDD sizes; one is derived from the treewidth of a CNF and the other from the size of a family of sets. Experiments show that ZSDDs are smaller than SDDs or ZDDs for a standard benchmark dataset.

Summarization aims to represent source documents by a shortened passage. Existing methods focus on the extraction of key information, but often neglect coherence. Hence the generated summaries suffer from a lack of readability. To address this problem, we have developed a graph-based method by exploring the links between text to produce coherent summaries. Our approach involves finding a sequence of sentences that best represent the key information in a coherent way. In contrast to the previous methods that focus only on salience, the proposed method addresses both coherence and informativeness based on textual linkages. We conduct experiments on the DUC2004 summarization task data set. A performance comparison reveals that the summaries generated by the proposed system achieve comparable results in terms of the ROUGE metric, and show improvements in readability by human evaluation.

Dynamic programming (DP) is a fundamental tool used to obtain exact, optimal solutions for many combinatorial optimization problems. Among these problems, important ones including the knapsack problems and the computation of edit distances between string pairs can be solved with a kind of DP that corresponds to solving the shortest path problem on a directed acyclic graph (DAG). These problems can be solved efficiently with DP, however, in practical situations, we want to solve the customized problems made by adding logical constraints to the original problems. Developing an algorithm specifically for each combination of a problem and a constraint set is unrealistic. The proposed method, BDD-Constrained Search (BCS), exploits a Binary Decision Diagram (BDD) that represents the logical constraints in combination with the DAG that represents the problem. The BCS runs DP on the DAG while using the BDD to check the equivalence and the validity of intermediate solutions to efficiently solve the problem. The important feature of BCS is that it can be applied to problems with various types of logical constraints in a unified way once we represent the constraints as a BDD. We give a theoretical analysis on the time complexity of BCS and also conduct experiments to compare its performance to that of a state-of-the-art integer linear programming solver.

Masaaki Nishino, Norihito Yasuda, Tsutomu Hirao, Shin-ichi Minato, Masaaki Nagata. Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2015.

Recent studies on extractive text summarization formulate it as a combinatorial optimization problem, extracting the optimal subset from a set of the textual units that maximizes an objective function without violating the length constraint. Although these methods successfully improve automatic evaluation scores, they do not consider the discourse structure in the source document. Thus, summaries generated by these methods may lack logical coherence. In previous work, we proposed a method that exploits a discourse tree structure to produce coherent summaries. By transforming a traditional discourse tree, namely a rhetorical structure theory-based discourse tree (RST-DT), into a dependency-based discourse tree (DEP-DT), we formulated the summarization procedure as a Tree Knapsack Problem whose tree corresponds to the DEP-DT. This paper extends the work with a detailed discussion of the approach together with a novel efficient dynamic programming algorithm for solving the Tree Knapsack Problem. Experiments show that our method not only achieved the highest score in both automatic and human evaluation, but also obtained good performance in terms of the linguistic qualities of the summaries.

We propose a method for accelerating matrix multiplications that are iteratively performed with a sparse adjacency matrix. These operations appear in a wide range of data analyses and data mining situations, which include the computation of Personalized PageRank (PPR) and Nonnegative Matrix Factorization (NMF). We exploit the fact that the intermediate computational results for the matrix multiplication of equivalent partial row vectors of a matrix are the same. Our new data structure, the adjacency forest, uses this property and represents an adjacency matrix as a rooted tree that is made by sharing the common suffixes of the row vectors of the matrix. By exploiting the structure of the tree, we can perform a matrix multiplication while sharing intermediate computational results to reduce the number of required operations. We also show that we can further accelerate computation by dividing a matrix into several sub-matrices and representing the original matrix as a forest. We confirm experimentally that our approach can speed up the computation of Personalized PageRank and NMF up to 300%.

Recent studies on extractive text summarization formulate it as a combinatorial optimization problem such as a Knapsack Problem, a Maximum Coverage Problem or a Budgeted Median Problem.These methods successfully improved summarization quality, but they did not consider the rhetorical relations between the textual units of a source document.Thus, summaries generated by these methods may lack logical coherence.This paper proposes a single document summarization method based on the trimming of a discourse tree.This is a two-fold process.First, we propose rules for transforming a rhetorical structure theorybased discourse tree into a dependency-based discourse tree, which allows us to take a treetrimming approach to summarization.Second, we formulate the problem of trimming a dependency-based discourse tree as a Tree Knapsack Problem, then solve it with integer linear programming (ILP).Evaluation results showed that our method improved ROUGE scores.