<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="sakaue-etal-2018-provable">
    <titleInfo>
        <title>Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Shinsaku</namePart>
        <namePart type="family">Sakaue</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Tsutomu</namePart>
        <namePart type="family">Hirao</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Masaaki</namePart>
        <namePart type="family">Nishino</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Masaaki</namePart>
        <namePart type="family">Nagata</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2018-06</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Marilyn</namePart>
            <namePart type="family">Walker</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Heng</namePart>
            <namePart type="family">Ji</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Amanda</namePart>
            <namePart type="family">Stent</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">New Orleans, Louisiana</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>Submodular maximization with the greedy algorithm has been studied as an effective approach to extractive summarization. This approach is known to have three advantages: its applicability to many useful submodular objective functions, the efficiency of the greedy algorithm, and the provable performance guarantee. However, when it comes to compressive summarization, we are currently missing a counterpart of the extractive method based on submodularity. In this paper, we propose a fast greedy method for compressive summarization. Our method is applicable to any monotone submodular objective function, including many functions well-suited for document summarization. We provide an approximation guarantee of our greedy algorithm. Experiments show that our method is about 100 to 400 times faster than an existing method based on integer-linear-programming (ILP) formulations and that our method empirically achieves more than 95%-approximation.</abstract>
    <identifier type="citekey">sakaue-etal-2018-provable</identifier>
    <identifier type="doi">10.18653/v1/N18-1157</identifier>
    <location>
        <url>https://aclanthology.org/N18-1157</url>
    </location>
    <part>
        <date>2018-06</date>
        <extent unit="page">
            <start>1737</start>
            <end>1746</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function
%A Sakaue, Shinsaku
%A Hirao, Tsutomu
%A Nishino, Masaaki
%A Nagata, Masaaki
%Y Walker, Marilyn
%Y Ji, Heng
%Y Stent, Amanda
%S Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)
%D 2018
%8 June
%I Association for Computational Linguistics
%C New Orleans, Louisiana
%F sakaue-etal-2018-provable
%X Submodular maximization with the greedy algorithm has been studied as an effective approach to extractive summarization. This approach is known to have three advantages: its applicability to many useful submodular objective functions, the efficiency of the greedy algorithm, and the provable performance guarantee. However, when it comes to compressive summarization, we are currently missing a counterpart of the extractive method based on submodularity. In this paper, we propose a fast greedy method for compressive summarization. Our method is applicable to any monotone submodular objective function, including many functions well-suited for document summarization. We provide an approximation guarantee of our greedy algorithm. Experiments show that our method is about 100 to 400 times faster than an existing method based on integer-linear-programming (ILP) formulations and that our method empirically achieves more than 95%-approximation.
%R 10.18653/v1/N18-1157
%U https://aclanthology.org/N18-1157
%U https://doi.org/10.18653/v1/N18-1157
%P 1737-1746

Markdown (Informal)

[Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function](https://aclanthology.org/N18-1157) (Sakaue et al., NAACL 2018)

• Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function (Sakaue et al., NAACL 2018)

ACL

• Shinsaku Sakaue, Tsutomu Hirao, Masaaki Nishino, and Masaaki Nagata. 2018. Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 1737–1746, New Orleans, Louisiana. Association for Computational Linguistics.