Deep neural networks and mixed integer linear optimization View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-07

AUTHORS

Matteo Fischetti, Jason Jo

ABSTRACT

Deep Neural Networks (DNNs) are very popular these days, and are the subject of a very intense investigation. A DNN is made up of layers of internal units (or neurons), each of which computes an affine combination of the output of the units in the previous layer, applies a nonlinear operator, and outputs the corresponding value (also known as activation). A commonly-used nonlinear operator is the so-called rectified linear unit (ReLU), whose output is just the maximum between its input value and zero. In this (and other similar cases like max pooling, where the max operation involves more than one input value), for fixed parameters one can model the DNN as a 0-1 Mixed Integer Linear Program (0-1 MILP) where the continuous variables correspond to the output values of each unit, and a binary variable is associated with each ReLU to model its yes/no nature. In this paper we discuss the peculiarity of this kind of 0-1 MILP models, and describe an effective bound-tightening technique intended to ease its solution. We also present possible applications of the 0-1 MILP model arising in feature visualization and in the construction of adversarial examples. Computational results are reported, aimed at investigating (on small DNNs) the computational performance of a state-of-the-art MILP solver when applied to a known test case, namely, hand-written digit recognition. More... »

PAGES

296-309

References to SciGraph publications

  • 2014-12. Proximity search for 0-1 mixed-integer convex programming in JOURNAL OF HEURISTICS
  • 2017-09-27. Maximum Resilience of Artificial Neural Networks in AUTOMATED TECHNOLOGY FOR VERIFICATION AND ANALYSIS
  • 2003-09. Local branching in MATHEMATICAL PROGRAMMING
  • 2016-12. On handling indicator constraints in mixed integer programming in COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10601-018-9285-6

    DOI

    http://dx.doi.org/10.1007/s10601-018-9285-6

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1103660105


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Padua", 
              "id": "https://www.grid.ac/institutes/grid.5608.b", 
              "name": [
                "Department of Information Engineering (DEI), University of Padova, Padua, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fischetti", 
            "givenName": "Matteo", 
            "id": "sg:person.015541213603.44", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015541213603.44"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Montreal Institute for Learning Algorithms (MILA), Montreal, Qu\u00e9bec, Canada", 
                "Institute for Data Valorization (IVADO), Montreal, Qu\u00e9bec, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Jo", 
            "givenName": "Jason", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s10589-016-9847-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010953651", 
              "https://doi.org/10.1007/s10589-016-9847-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-003-0395-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023883503", 
              "https://doi.org/10.1007/s10107-003-0395-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10732-014-9266-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027615537", 
              "https://doi.org/10.1007/s10732-014-9266-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disopt.2015.03.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031284123"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/5.726791", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061179979"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/ijoc.1060.0189", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064706604"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/3065386", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085642448"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/3065386", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1085642448"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-68167-2_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091962617", 
              "https://doi.org/10.1007/978-3-319-68167-2_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-68167-2_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091962617", 
              "https://doi.org/10.1007/978-3-319-68167-2_18"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-07", 
        "datePublishedReg": "2018-07-01", 
        "description": "Deep Neural Networks (DNNs) are very popular these days, and are the subject of a very intense investigation. A DNN is made up of layers of internal units (or neurons), each of which computes an affine combination of the output of the units in the previous layer, applies a nonlinear operator, and outputs the corresponding value (also known as activation). A commonly-used nonlinear operator is the so-called rectified linear unit (ReLU), whose output is just the maximum between its input value and zero. In this (and other similar cases like max pooling, where the max operation involves more than one input value), for fixed parameters one can model the DNN as a 0-1 Mixed Integer Linear Program (0-1 MILP) where the continuous variables correspond to the output values of each unit, and a binary variable is associated with each ReLU to model its yes/no nature. In this paper we discuss the peculiarity of this kind of 0-1 MILP models, and describe an effective bound-tightening technique intended to ease its solution. We also present possible applications of the 0-1 MILP model arising in feature visualization and in the construction of adversarial examples. Computational results are reported, aimed at investigating (on small DNNs) the computational performance of a state-of-the-art MILP solver when applied to a known test case, namely, hand-written digit recognition.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10601-018-9285-6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1043977", 
            "issn": [
              "1383-7133", 
              "1572-9354"
            ], 
            "name": "Constraints", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "23"
          }
        ], 
        "name": "Deep neural networks and mixed integer linear optimization", 
        "pagination": "296-309", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "4d095ab9e290ad103227a05b8ab88ab3e78a14e3a8470bc98ba4a3bbcb0c1a9f"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10601-018-9285-6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1103660105"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10601-018-9285-6", 
          "https://app.dimensions.ai/details/publication/pub.1103660105"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T09:57", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000347_0000000347/records_89807_00000003.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs10601-018-9285-6"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10601-018-9285-6'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10601-018-9285-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-018-9285-6'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10601-018-9285-6'


     

    This table displays all metadata directly associated to this object as RDF triples.

    98 TRIPLES      21 PREDICATES      35 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10601-018-9285-6 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nda08921d80f0400784573ad7aa631ae3
    4 schema:citation sg:pub.10.1007/978-3-319-68167-2_18
    5 sg:pub.10.1007/s10107-003-0395-5
    6 sg:pub.10.1007/s10589-016-9847-8
    7 sg:pub.10.1007/s10732-014-9266-x
    8 https://doi.org/10.1016/j.disopt.2015.03.002
    9 https://doi.org/10.1109/5.726791
    10 https://doi.org/10.1145/3065386
    11 https://doi.org/10.1287/ijoc.1060.0189
    12 schema:datePublished 2018-07
    13 schema:datePublishedReg 2018-07-01
    14 schema:description Deep Neural Networks (DNNs) are very popular these days, and are the subject of a very intense investigation. A DNN is made up of layers of internal units (or neurons), each of which computes an affine combination of the output of the units in the previous layer, applies a nonlinear operator, and outputs the corresponding value (also known as activation). A commonly-used nonlinear operator is the so-called rectified linear unit (ReLU), whose output is just the maximum between its input value and zero. In this (and other similar cases like max pooling, where the max operation involves more than one input value), for fixed parameters one can model the DNN as a 0-1 Mixed Integer Linear Program (0-1 MILP) where the continuous variables correspond to the output values of each unit, and a binary variable is associated with each ReLU to model its yes/no nature. In this paper we discuss the peculiarity of this kind of 0-1 MILP models, and describe an effective bound-tightening technique intended to ease its solution. We also present possible applications of the 0-1 MILP model arising in feature visualization and in the construction of adversarial examples. Computational results are reported, aimed at investigating (on small DNNs) the computational performance of a state-of-the-art MILP solver when applied to a known test case, namely, hand-written digit recognition.
    15 schema:genre research_article
    16 schema:inLanguage en
    17 schema:isAccessibleForFree false
    18 schema:isPartOf N15c6735bf02540ee984b1833b187b7db
    19 Ne6e59b43bafc4ee4b871df9a5df52f55
    20 sg:journal.1043977
    21 schema:name Deep neural networks and mixed integer linear optimization
    22 schema:pagination 296-309
    23 schema:productId N2293fbdfd1e743a7b51bb3494028ed0a
    24 N9fb7fd7061f5484991a3907086b3b53a
    25 Ne7afb23a2e2e4341a63e15e7c29c92ea
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103660105
    27 https://doi.org/10.1007/s10601-018-9285-6
    28 schema:sdDatePublished 2019-04-11T09:57
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher Na287f68ca1f340bab6737f2ca2e8057f
    31 schema:url https://link.springer.com/10.1007%2Fs10601-018-9285-6
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset articles
    34 rdf:type schema:ScholarlyArticle
    35 N02538f778ef74591baa719f2114abe65 rdf:first N93e5e39997ab4057955e91683acbe49c
    36 rdf:rest rdf:nil
    37 N15c6735bf02540ee984b1833b187b7db schema:issueNumber 3
    38 rdf:type schema:PublicationIssue
    39 N2293fbdfd1e743a7b51bb3494028ed0a schema:name dimensions_id
    40 schema:value pub.1103660105
    41 rdf:type schema:PropertyValue
    42 N93e5e39997ab4057955e91683acbe49c schema:affiliation Nabd9ad01a51b4117b14ee032e8846cb7
    43 schema:familyName Jo
    44 schema:givenName Jason
    45 rdf:type schema:Person
    46 N9fb7fd7061f5484991a3907086b3b53a schema:name readcube_id
    47 schema:value 4d095ab9e290ad103227a05b8ab88ab3e78a14e3a8470bc98ba4a3bbcb0c1a9f
    48 rdf:type schema:PropertyValue
    49 Na287f68ca1f340bab6737f2ca2e8057f schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 Nabd9ad01a51b4117b14ee032e8846cb7 schema:name Institute for Data Valorization (IVADO), Montreal, Québec, Canada
    52 Montreal Institute for Learning Algorithms (MILA), Montreal, Québec, Canada
    53 rdf:type schema:Organization
    54 Nda08921d80f0400784573ad7aa631ae3 rdf:first sg:person.015541213603.44
    55 rdf:rest N02538f778ef74591baa719f2114abe65
    56 Ne6e59b43bafc4ee4b871df9a5df52f55 schema:volumeNumber 23
    57 rdf:type schema:PublicationVolume
    58 Ne7afb23a2e2e4341a63e15e7c29c92ea schema:name doi
    59 schema:value 10.1007/s10601-018-9285-6
    60 rdf:type schema:PropertyValue
    61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Information and Computing Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Artificial Intelligence and Image Processing
    66 rdf:type schema:DefinedTerm
    67 sg:journal.1043977 schema:issn 1383-7133
    68 1572-9354
    69 schema:name Constraints
    70 rdf:type schema:Periodical
    71 sg:person.015541213603.44 schema:affiliation https://www.grid.ac/institutes/grid.5608.b
    72 schema:familyName Fischetti
    73 schema:givenName Matteo
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015541213603.44
    75 rdf:type schema:Person
    76 sg:pub.10.1007/978-3-319-68167-2_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091962617
    77 https://doi.org/10.1007/978-3-319-68167-2_18
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/s10107-003-0395-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023883503
    80 https://doi.org/10.1007/s10107-003-0395-5
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/s10589-016-9847-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010953651
    83 https://doi.org/10.1007/s10589-016-9847-8
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/s10732-014-9266-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1027615537
    86 https://doi.org/10.1007/s10732-014-9266-x
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1016/j.disopt.2015.03.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031284123
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1109/5.726791 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061179979
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1145/3065386 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085642448
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1287/ijoc.1060.0189 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706604
    95 rdf:type schema:CreativeWork
    96 https://www.grid.ac/institutes/grid.5608.b schema:alternateName University of Padua
    97 schema:name Department of Information Engineering (DEI), University of Padova, Padua, Italy
    98 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...