Personalized Extractive Summarization Using an Ising Machine Towards Real-time Generation of Efficient and Coherent Dialogue Scenarios (2021)

Abstract: We propose a personalized dialogue scenario generation system which transmits efficient and coherent information with a real-time extractive summarization method optimized by an Ising machine. The summarization problem is formulated as a quadratic unconstraint binary optimization (QUBO) problem, which extracts sentences that maximize the sum of the degree of user’s interest in the sentences of documents with the discourse structure of each document and the total utterance time as constraints. To evaluate the proposed method, we constructed a news article corpus with annotations of the discourse structure, users’ profiles, and interests in sentences and topics. The experimental results confirmed that a Digital Annealer, which is a simulated annealing-based Ising machine, can solve our QUBO model in a practical time without violating the constraints using this dataset.

## introduction as mobile personal assistants and smart speakers become ubiquitous, the demand for dialogue-based media technologies has increased since they allow users to consume a fair amount of information via a dialogue form in daily life situations. dialoguebased media is more restrictive than textual media. for example, when listening to an ordinary smart speaker, users can not skip unnecessary information or skim only for necessary information. thus, it is crucial for future dialogue-based media to extract and efficiently transmit information that the users are particularly interested in without excess or deficiencies. in addition, the dialogue scenarios generated based on the extracted information should be coherent to aid in the proper understanding. generating such efficient and coherent scenarios personalized for each user generally takes more time as the information source size and the number of target users increase. moreover, the nature of conversational experiences requires personalization in real time. in this paper, we propose a personalized extractive summarization method formulated as a combinatorial optimization problem to generate efficient and coherent dialogue scenarios and demonstrate that an ising machine can solve the problem at high speeds. as a realistic application of the proposed personalized summarization method for a spoken dialogue system, we consider a news delivery task @xcite . this news dialogue system proceeds the dialogue according to a primary plan to explain the summary of the news article and subsidiary plans to transmit supplementary information though question answering. as long as the user is listening passively, the system transmits the content of the primary plan. the personalized primary plan generation problem can be formulated as follows: from n documents with different topics, sentences that may be of interest to the user are extracted based on the discourse structure of each document. then the contents are transmitted by voice within t seconds. specifically, this problem can be formulated as an integer linear programming (ilp) problem, which extracts sentences that maximize the sum of the degree of user's interest in the sentences of documents with the discourse structure of each document and the total utterance time t as constraints. because this ilp problem is np-hard, it takes an enormous amount of time to find an optimal solution using the branch-and-cut method @xcite as the problem scale becomes large. in recent years, non-von neumann computers called ising machines have been attracting attention as they can solve combinatorial optimization problems and obtain quasi-optimal solutions instantly @xcite . ising machines can solve combi-natorial optimization problems represented by an ising model or a quadratic unconstrained binary optimization (qubo) model @xcite . in this paper, we propose a qubo model that generates an efficient and coherent personalized summary for each user. additionally, we verify that our qubo model can be solved by a digital annealer @xcite , which is a simulated annealing-based ising machine, in a practical time without violating the constraints using the constructed dataset. the contributions of this paper are three-fold: the rest of this paper is organized as follows. section 2 discusses the related work. section 3 overviews the annotations of the discourse structure and interest data collection. section 4 details the proposed method. section 5 describes the digital annealer. section 6 evaluates the performance of the proposed method. section 7 provides the conclusions and prospects. ## datasets we constructed a news article corpus with annotations of the discourse structure, users' profiles, and interests in sentences and topics. experts annotated the inter-sentence dependencies, discourse relations, and chunks for the japanese news articles. users' profiles and interests in the sentences and topics of news articles were collected via crowdsourcing. ## methods we propose an integer linear programming (ilp) model and a quadratic unconstraint binary optimization (qubo) model for the personalized summary generation in terms of efficient and coherent information transmission. ## digital annealer quantum computing technologies are categorized into two types: quantum gate computers @xcite and ising machines. quantum gate computers are for universal computing, whereas ising machines specialize in searching for solutions of combinatorial optimization problems. ising machines can be subdivided into two categories: quantum annealing machines @xcite @xcite and simulated annealing machines @xcite @xcite . quantum annealing machines search solutions using quantum bits, which are made of quantum devices such as a superconducting circuit. by contrast, simulated annealing machines use a digital circuit. digital annealer @xcite is a type of simulated annealing machines with a new digital circuit architecture, which is designed to solve combinatorial optimization problems efficiently. this study uses a digital annealing unit (dau) of the second generation digital annealer. the dau has an annealing mode @xcite or parallel tempering mode @xcite to solve qubo models. it can handle up to 4,096 binary variables with 64-bit precision or as many as 8,192 binary variables with 16-bit precision. hereinafter, the dau in the annealing mode is referred to as dau-am, and the dau in the parallel tempering mode is referred to as dau-ptm. ## experiments using the constructed dataset, we evaluated the performance of the personalized summarization method for dialogue scenario planning. the ilp model was solved by the branch-and-cut method foot_0 @xcite on the cpu. hereinafter, this method is referred to as cpu-cbc. we used cpu-cbc as a benchmark and compared the performance of cpu-cbc, dau-am and dau-ptm. ## conclusion this paper proposed a quadratic unconstraint binary optimization (qubo) model for the real-time personalized summary generation in terms of effi-cient and coherent information transmission. the model extracts sentences that maximize the sum of the degree of user's interest in the sentences of documents with the discourse structure of each document and total utterance time as constraints. to evaluate the effectiveness of the proposed method, we constructed a japanese news article corpus with annotations of the discourse structure, users' profiles, and interests in sentences and topics. experiments demonstrated that our qubo model could be solved by a digital annealer, which is a simulated annealing-based ising machine, in a practical time without violating the constraints using the dataset. in the future, we will verify the effect of personalized scenarios on the spoken dialogue system.