summaryrefslogtreecommitdiffstats
path: root/slides
diff options
context:
space:
mode:
authorThibaut Horel <thibaut.horel@gmail.com>2013-02-07 14:37:17 -0800
committerThibaut Horel <thibaut.horel@gmail.com>2013-02-07 14:37:17 -0800
commit58ccbe548085600cc2fbb005726191438b450bc7 (patch)
tree2f55375aff50a738072090cb1f4df7e830bbfe1d /slides
parenta148a6f046173cd114e009c6ef50e77d5d5941f4 (diff)
downloadrecommendation-58ccbe548085600cc2fbb005726191438b450bc7.tar.gz
Slides for dimacs workshop at Stanford
Diffstat (limited to 'slides')
-rw-r--r--slides/1.pdfbin0 -> 45040 bytes
-rw-r--r--slides/2.pdfbin0 -> 45694 bytes
-rw-r--r--slides/3.pdfbin0 -> 46210 bytes
-rw-r--r--slides/4.pdfbin0 -> 46191 bytes
-rw-r--r--slides/db.svg75
-rw-r--r--slides/diagram.svg1303
-rw-r--r--slides/slides.tex493
-rw-r--r--slides/user.svg76
8 files changed, 1704 insertions, 243 deletions
diff --git a/slides/1.pdf b/slides/1.pdf
new file mode 100644
index 0000000..31bcf6b
--- /dev/null
+++ b/slides/1.pdf
Binary files differ
diff --git a/slides/2.pdf b/slides/2.pdf
new file mode 100644
index 0000000..1794dce
--- /dev/null
+++ b/slides/2.pdf
Binary files differ
diff --git a/slides/3.pdf b/slides/3.pdf
new file mode 100644
index 0000000..884f542
--- /dev/null
+++ b/slides/3.pdf
Binary files differ
diff --git a/slides/4.pdf b/slides/4.pdf
new file mode 100644
index 0000000..eaebe6e
--- /dev/null
+++ b/slides/4.pdf
Binary files differ
diff --git a/slides/db.svg b/slides/db.svg
new file mode 100644
index 0000000..03ca11c
--- /dev/null
+++ b/slides/db.svg
@@ -0,0 +1,75 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!-- Created with Inkscape (http://www.inkscape.org/) -->
+<svg xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://creativecommons.org/ns#" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:svg="http://www.w3.org/2000/svg" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" width="186.69325" height="206.07425" id="svg5378" version="1.1" inkscape:version="0.47pre4 r22446" sodipodi:docname="Documento nuevo 18">
+ <defs id="defs3">
+ <linearGradient id="linearGradient6035">
+ <stop style="stop-color:#ffffff;stop-opacity:1;" offset="0" id="stop6037"/>
+ <stop style="stop-color:#ffffff;stop-opacity:0;" offset="1" id="stop6039"/>
+ </linearGradient>
+ <linearGradient id="linearGradient5495" inkscape:collect="always">
+ <stop id="stop5497" offset="0" style="stop-color:#c6c6c6;stop-opacity:1"/>
+ <stop style="stop-color:#e3e3e3;stop-opacity:1" offset="0.20484632" id="stop5501"/>
+ <stop id="stop5499" offset="1" style="stop-color:#a5a5a8;stop-opacity:1"/>
+ </linearGradient>
+ <linearGradient inkscape:collect="always" id="linearGradient5474">
+ <stop style="stop-color:#c3c3c3;stop-opacity:1" offset="0" id="stop5476"/>
+ <stop id="stop5482" offset="0.38759774" style="stop-color:#808184;stop-opacity:1"/>
+ <stop style="stop-color:#7f7f84;stop-opacity:1" offset="0.57053357" id="stop5484"/>
+ <stop id="stop5486" offset="0.89746869" style="stop-color:#a5a6aa;stop-opacity:1"/>
+ <stop style="stop-color:#9b9b9e;stop-opacity:1" offset="1" id="stop5478"/>
+ </linearGradient>
+ <linearGradient inkscape:collect="always" id="linearGradient5466">
+ <stop style="stop-color:#e3e3e3;stop-opacity:1" offset="0" id="stop5468"/>
+ <stop style="stop-color:#a5a5a8;stop-opacity:1" offset="1" id="stop5470"/>
+ </linearGradient>
+ <inkscape:perspective sodipodi:type="inkscape:persp3d" inkscape:vp_x="0 : 526.18109 : 1" inkscape:vp_y="0 : 1000 : 0" inkscape:vp_z="744.09448 : 526.18109 : 1" inkscape:persp3d-origin="372.04724 : 350.78739 : 1" id="perspective5384"/>
+ <inkscape:perspective id="perspective5454" inkscape:persp3d-origin="0.5 : 0.33333333 : 1" inkscape:vp_z="1 : 0.5 : 1" inkscape:vp_y="0 : 1000 : 0" inkscape:vp_x="0 : 0.5 : 1" sodipodi:type="inkscape:persp3d"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient5466" id="linearGradient5472" x1="282.35706" y1="518.55707" x2="286.6308" y2="527.33539" gradientUnits="userSpaceOnUse"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient5474" id="linearGradient5480" x1="288.39856" y1="532.00739" x2="327.79306" y2="532.00739" gradientUnits="userSpaceOnUse"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient5466" id="linearGradient5490" gradientUnits="userSpaceOnUse" x1="282.35706" y1="518.55707" x2="286.6308" y2="527.33539" gradientTransform="matrix(1.1818182,0,0,1.1818182,-30.64896,-69.394391)"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient5495" id="linearGradient5493" gradientUnits="userSpaceOnUse" gradientTransform="matrix(1.1818182,0,0,1.1818182,-30.64896,-69.394391)" x1="269.96979" y1="511.96591" x2="286.62845" y2="511.96591" spreadMethod="reflect"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient5466" id="linearGradient6015" gradientUnits="userSpaceOnUse" x1="282.35706" y1="518.55707" x2="286.6308" y2="527.33539" gradientTransform="matrix(1.1818182,0,0,1.1818182,-31.65912,-123.63805)"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6041" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812" gradientUnits="userSpaceOnUse" spreadMethod="reflect" gradientTransform="translate(0,0.25)"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6045" gradientUnits="userSpaceOnUse" spreadMethod="reflect" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812" gradientTransform="translate(0,16)"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6049" gradientUnits="userSpaceOnUse" gradientTransform="translate(0,15.417003)" spreadMethod="reflect" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6052" gradientUnits="userSpaceOnUse" gradientTransform="translate(0,12)" spreadMethod="reflect" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6056" gradientUnits="userSpaceOnUse" gradientTransform="translate(0,22)" spreadMethod="reflect" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6064" gradientUnits="userSpaceOnUse" gradientTransform="translate(0,28)" spreadMethod="reflect" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6077" gradientUnits="userSpaceOnUse" gradientTransform="translate(0,12)" spreadMethod="reflect" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812"/>
+ <filter inkscape:collect="always" id="filter6093" x="-0.064257026" width="1.1285141" y="-0.19277108" height="1.3855422" color-interpolation-filters="sRGB">
+ <feGaussianBlur inkscape:collect="always" stdDeviation="0.89250425" id="feGaussianBlur6095"/>
+ </filter>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient5495" id="linearGradient6110" gradientUnits="userSpaceOnUse" gradientTransform="matrix(1.1818182,0,0,1.1818182,-30.64896,-69.394391)" spreadMethod="reflect" x1="269.96979" y1="511.96591" x2="286.62845" y2="511.96591"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient5466" id="linearGradient6112" gradientUnits="userSpaceOnUse" x1="282.35706" y1="518.55707" x2="286.6308" y2="527.33539"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6114" gradientUnits="userSpaceOnUse" gradientTransform="translate(0,0.25)" spreadMethod="reflect" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6116" gradientUnits="userSpaceOnUse" gradientTransform="translate(0,12)" spreadMethod="reflect" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6035" id="linearGradient6118" gradientUnits="userSpaceOnUse" gradientTransform="translate(0,22)" spreadMethod="reflect" x1="308.5" y1="522.61218" x2="327.78125" y2="520.32812"/>
+ </defs>
+ <sodipodi:namedview inkscape:document-units="mm" id="base" pagecolor="#ffffff" bordercolor="#666666" borderopacity="1.0" inkscape:pageopacity="0.0" inkscape:pageshadow="2" inkscape:zoom="1" inkscape:cx="21.488191" inkscape:cy="189.49112" inkscape:current-layer="layer1" showgrid="false" inkscape:window-width="1280" inkscape:window-height="949" inkscape:window-x="0" inkscape:window-y="24" inkscape:window-maximized="1"/>
+ <metadata id="metadata4">
+ <rdf:RDF>
+ <cc:Work rdf:about="">
+ <dc:format>image/svg+xml</dc:format>
+ <dc:type rdf:resource="http://purl.org/dc/dcmitype/StillImage"/>
+ <dc:title/>
+ </cc:Work>
+ </rdf:RDF>
+ </metadata>
+ <g inkscape:label="Layer 1" inkscape:groupmode="layer" id="layer1" transform="translate(-285.86708,-510.6882)">
+ <g id="g6097" transform="matrix(4.1992341,0,0,4.1992341,-914.55576,-1633.811)">
+ <path sodipodi:type="arc" style="fill:#2e3436;fill-opacity:1;stroke:none;filter:url(#filter6093)" id="path6079" sodipodi:cx="286.6308" sodipodi:cy="521.77954" sodipodi:rx="16.667517" sodipodi:ry="5.5558391" d="m 303.29832,521.77954 c 0,3.06841 -7.46231,5.55584 -16.66752,5.55584 -9.20522,0 -16.66752,-2.48743 -16.66752,-5.55584 0,-3.0684 7.4623,-5.55584 16.66752,-5.55584 9.20521,0 16.66752,2.48744 16.66752,5.55584 z" transform="matrix(1.1818182,0,0,1.1818182,-30.64896,-65.983596)"/>
+ <path sodipodi:nodetypes="cccssscccc" id="path5488" d="m 288.40625,517.5 0,30.09191 0.125,0 c -0.0806,0.24126 -0.125,0.47032 -0.125,0.71875 0,3.6263 8.80861,6.5625 19.6875,6.5625 10.87889,0 19.6875,-2.9362 19.6875,-6.5625 0,-0.24879 -0.0442,-0.47715 -0.125,-0.71875 l 0.125,0 0,-30.09191 -39.375,0 z" style="fill:url(#linearGradient6110);fill-opacity:1;stroke:none"/>
+ <path transform="matrix(1.1818182,0,0,1.1818182,-30.64896,-99.394391)" d="m 303.29832,521.77954 c 0,3.06841 -7.46231,5.55584 -16.66752,5.55584 -9.20522,0 -16.66752,-2.48743 -16.66752,-5.55584 0,-3.0684 7.4623,-5.55584 16.66752,-5.55584 9.20521,0 16.66752,2.48744 16.66752,5.55584 z" sodipodi:ry="5.5558391" sodipodi:rx="16.667517" sodipodi:cy="521.77954" sodipodi:cx="286.6308" id="path5460" style="fill:url(#linearGradient6112);fill-opacity:1;stroke:none" sodipodi:type="arc"/>
+ <path id="path6026" d="m 288.375,539.09375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -3.45152,2.93589 -10.95919,4.96875 -19.6875,4.96875 -8.74612,0 -16.27686,-2.05444 -19.71875,-5 z" style="fill:#565656;fill-opacity:1;stroke:none"/>
+ <path id="path6030" d="m 288.375,517.34375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -0.21572,0.18349 -0.44078,0.35509 -0.6875,0.53125 -0.009,0.0117 -0.0216,0.0196 -0.0312,0.0312 -2.29214,2.77744 -9.90349,4.8125 -18.96875,4.8125 -9.12203,0 -16.78563,-2.07074 -19.03125,-4.875 -0.0249,-0.0179 -0.038,-0.0446 -0.0625,-0.0625 -0.21872,-0.15969 -0.43159,-0.30323 -0.625,-0.46875 z" style="fill:url(#linearGradient6114);fill-opacity:1;stroke:none"/>
+ <g id="g6071">
+ <g transform="translate(0,-0.52315203)" id="g6067">
+ <path style="fill:#565656;fill-opacity:1;stroke:none" d="m 288.375,529.09375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -3.45152,2.93589 -10.95919,4.96875 -19.6875,4.96875 -8.74612,0 -16.27686,-2.05444 -19.71875,-5 z" id="path6022"/>
+ <path id="path6043" d="m 288.375,529.09375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -0.0497,0.0422 -0.10543,0.0838 -0.15625,0.125 -1.24216,3.22677 -9.51064,5.71875 -19.53125,5.71875 -10.11275,0 -18.46774,-2.51121 -19.59375,-5.78125 -0.0401,-0.0317 -0.0863,-0.0607 -0.125,-0.0937 z" style="fill:url(#linearGradient6116);fill-opacity:1;stroke:none"/>
+ </g>
+ <path id="path6054" d="m 288.375,539.09375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -0.0497,0.0422 -0.10543,0.0838 -0.15625,0.125 -1.24216,3.22677 -9.51064,5.71875 -19.53125,5.71875 -10.11275,0 -18.46774,-2.51121 -19.59375,-5.78125 -0.0401,-0.0317 -0.0863,-0.0607 -0.125,-0.0937 z" style="fill:url(#linearGradient6118);fill-opacity:1;stroke:none"/>
+ </g>
+ <path id="path6060" d="m 288.5,549.9375 c 1.12601,3.27004 9.481,5.78125 19.59375,5.78125 10.02061,0 18.28909,-2.49198 19.53125,-5.71875 -3.51634,2.86779 -10.92856,4.84375 -19.53125,4.84375 -8.64783,0 -16.10003,-2.01374 -19.59375,-4.90625 z" style="fill:#565656;fill-opacity:1;stroke:none"/>
+ </g>
+ </g>
+</svg> \ No newline at end of file
diff --git a/slides/diagram.svg b/slides/diagram.svg
new file mode 100644
index 0000000..c4b4fa2
--- /dev/null
+++ b/slides/diagram.svg
@@ -0,0 +1,1303 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!-- Created with Inkscape (http://www.inkscape.org/) -->
+
+<svg
+ xmlns:osb="http://www.openswatchbook.org/uri/2009/osb"
+ xmlns:dc="http://purl.org/dc/elements/1.1/"
+ xmlns:cc="http://creativecommons.org/ns#"
+ xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+ xmlns:svg="http://www.w3.org/2000/svg"
+ xmlns="http://www.w3.org/2000/svg"
+ xmlns:xlink="http://www.w3.org/1999/xlink"
+ xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
+ xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+ width="1052.36"
+ height="1052.36"
+ id="svg2"
+ version="1.1"
+ inkscape:version="0.48.4 r9939"
+ sodipodi:docname="diagram.svg">
+ <defs
+ id="defs4">
+ <marker
+ inkscape:stockid="Arrow1Send"
+ orient="auto"
+ refY="0.0"
+ refX="0.0"
+ id="Arrow1Send"
+ style="overflow:visible;">
+ <path
+ id="path4654"
+ d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z "
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;"
+ transform="scale(0.2) rotate(180) translate(6,0)" />
+ </marker>
+ <marker
+ inkscape:stockid="Arrow1Mstart"
+ orient="auto"
+ refY="0.0"
+ refX="0.0"
+ id="Arrow1Mstart"
+ style="overflow:visible">
+ <path
+ id="path4645"
+ d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z "
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt"
+ transform="scale(0.4) translate(10,0)" />
+ </marker>
+ <marker
+ inkscape:stockid="Arrow2Lstart"
+ orient="auto"
+ refY="0.0"
+ refX="0.0"
+ id="Arrow2Lstart"
+ style="overflow:visible">
+ <path
+ id="path4657"
+ style="fill-rule:evenodd;stroke-width:0.62500000;stroke-linejoin:round"
+ d="M 8.7185878,4.0337352 L -2.2072895,0.016013256 L 8.7185884,-4.0017078 C 6.9730900,-1.6296469 6.9831476,1.6157441 8.7185878,4.0337352 z "
+ transform="scale(1.1) translate(1,0)" />
+ </marker>
+ <marker
+ inkscape:stockid="Arrow2Mend"
+ orient="auto"
+ refY="0"
+ refX="0"
+ id="Arrow2Mend"
+ style="overflow:visible">
+ <path
+ id="path4666"
+ style="fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round"
+ d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z"
+ transform="scale(-0.6,-0.6)"
+ inkscape:connector-curvature="0" />
+ </marker>
+ <marker
+ inkscape:stockid="Arrow1Lend"
+ orient="auto"
+ refY="0"
+ refX="0"
+ id="Arrow1Lend"
+ style="overflow:visible">
+ <path
+ id="path4642"
+ d="M 0,0 5,-5 -12.5,0 5,5 0,0 z"
+ style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt"
+ transform="matrix(-0.8,0,0,-0.8,-10,0)"
+ inkscape:connector-curvature="0" />
+ </marker>
+ <linearGradient
+ id="linearGradient4184"
+ osb:paint="solid">
+ <stop
+ style="stop-color:#0000ff;stop-opacity:1;"
+ offset="0"
+ id="stop4186" />
+ </linearGradient>
+ <radialGradient
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="matrix(0.103799,0.0814516,-0.214019,0.272739,-132.2014,63.74477)"
+ r="15.008935"
+ fy="72.644211"
+ fx="-164.86122"
+ cy="72.644211"
+ cx="-164.86122"
+ id="radialGradient17178"
+ xlink:href="#linearGradient17172"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientUnits="userSpaceOnUse"
+ y2="48.75983"
+ x2="-172.04314"
+ y1="16.79554"
+ x1="-247.27679"
+ id="linearGradient14509"
+ xlink:href="#linearGradient14503"
+ inkscape:collect="always" />
+ <radialGradient
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="matrix(0.7193,-0.0171987,0.03513213,1.469327,-47.5673,-19.60001)"
+ r="21.607157"
+ fy="33.695477"
+ fx="-165.2417"
+ cy="33.695477"
+ cx="-165.2417"
+ id="radialGradient13603"
+ xlink:href="#linearGradient13597"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="-1.6124004"
+ x2="56.009064"
+ y1="7.1001654"
+ x1="40.537895"
+ gradientTransform="translate(-199.9859,52.32021)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient12710"
+ xlink:href="#linearGradient7269"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientTransform="translate(-331.4237,73.06709)"
+ y2="-67.703445"
+ x2="164.94254"
+ y1="-8.0820084"
+ x1="160.12111"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient12708"
+ xlink:href="#linearGradient7301"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientTransform="translate(-331.4237,73.06709)"
+ y2="13.3125"
+ x2="159.78572"
+ y1="-10.794643"
+ x1="161.20535"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient12706"
+ xlink:href="#linearGradient10894"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientTransform="translate(-331.4237,73.06709)"
+ y2="-11.642858"
+ x2="158.40045"
+ y1="24.964285"
+ x1="158.42857"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient12704"
+ xlink:href="#linearGradient11787"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="-10.638393"
+ x2="1.6168088"
+ y1="-31.888393"
+ x1="8.3035717"
+ gradientTransform="translate(-199.9859,52.32021)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient12702"
+ xlink:href="#linearGradient6376"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="-25.337072"
+ x2="27.385256"
+ y1="5.3772144"
+ x1="-13.709487"
+ gradientTransform="translate(-199.9859,52.32021)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient12700"
+ xlink:href="#linearGradient5483"
+ inkscape:collect="always" />
+ <linearGradient
+ id="linearGradient5483">
+ <stop
+ id="stop5485"
+ offset="0"
+ style="stop-color:#664314;stop-opacity:1;" />
+ <stop
+ id="stop5487"
+ offset="1"
+ style="stop-color:#a06b08;stop-opacity:1;" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient6376">
+ <stop
+ id="stop6378"
+ offset="0"
+ style="stop-color:#da8410;stop-opacity:1;" />
+ <stop
+ id="stop6380"
+ offset="1"
+ style="stop-color:#c97402;stop-opacity:0;" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient7269"
+ inkscape:collect="always">
+ <stop
+ id="stop7271"
+ offset="0"
+ style="stop-color:#9f5f09;stop-opacity:1;" />
+ <stop
+ id="stop7273"
+ offset="1"
+ style="stop-color:#9f5f09;stop-opacity:0;" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient7301">
+ <stop
+ id="stop7303"
+ offset="0"
+ style="stop-color:#d49c56;stop-opacity:1;" />
+ <stop
+ id="stop7305"
+ offset="1"
+ style="stop-color:#d49c56;stop-opacity:0;" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient10894">
+ <stop
+ id="stop10896"
+ offset="0"
+ style="stop-color:#d49c56;stop-opacity:1;" />
+ <stop
+ id="stop10898"
+ offset="1"
+ style="stop-color:#d49c56;stop-opacity:0.25806451;" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient11787">
+ <stop
+ id="stop11789"
+ offset="0"
+ style="stop-color:black;stop-opacity:1;" />
+ <stop
+ id="stop11791"
+ offset="1"
+ style="stop-color:#747474;stop-opacity:1;" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient13597">
+ <stop
+ id="stop13599"
+ offset="0"
+ style="stop-color:#ffeed6;stop-opacity:1;" />
+ <stop
+ id="stop13601"
+ offset="1"
+ style="stop-color:#ffcd8b;stop-opacity:1;" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient14503"
+ inkscape:collect="always">
+ <stop
+ id="stop14505"
+ offset="0"
+ style="stop-color:white;stop-opacity:1;" />
+ <stop
+ id="stop14507"
+ offset="1"
+ style="stop-color:white;stop-opacity:0;" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient17172">
+ <stop
+ id="stop17174"
+ offset="0"
+ style="stop-color:#ffeed6;stop-opacity:1;" />
+ <stop
+ id="stop17176"
+ offset="1"
+ style="stop-color:#ffcd8b;stop-opacity:1;" />
+ </linearGradient>
+ <linearGradient
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ spreadMethod="reflect"
+ gradientTransform="translate(0,22)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6118"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ spreadMethod="reflect"
+ gradientTransform="translate(0,12)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6116"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ spreadMethod="reflect"
+ gradientTransform="translate(0,0.25)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6114"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="527.33539"
+ x2="286.6308"
+ y1="518.55707"
+ x1="282.35706"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6112"
+ xlink:href="#linearGradient5466"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="511.96591"
+ x2="286.62845"
+ y1="511.96591"
+ x1="269.96979"
+ spreadMethod="reflect"
+ gradientTransform="matrix(1.1818182,0,0,1.1818182,-30.64896,-69.394391)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6110"
+ xlink:href="#linearGradient5495"
+ inkscape:collect="always" />
+ <filter
+ color-interpolation-filters="sRGB"
+ height="1.3855422"
+ y="-0.19277108"
+ width="1.1285141"
+ x="-0.064257026"
+ id="filter6093"
+ inkscape:collect="always">
+ <feGaussianBlur
+ id="feGaussianBlur6095"
+ stdDeviation="0.89250425"
+ inkscape:collect="always" />
+ </filter>
+ <linearGradient
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ spreadMethod="reflect"
+ gradientTransform="translate(0,12)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6077"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ spreadMethod="reflect"
+ gradientTransform="translate(0,28)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6064"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ spreadMethod="reflect"
+ gradientTransform="translate(0,22)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6056"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ spreadMethod="reflect"
+ gradientTransform="translate(0,12)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6052"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ spreadMethod="reflect"
+ gradientTransform="translate(0,15.417003)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6049"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientTransform="translate(0,16)"
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ spreadMethod="reflect"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6045"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientTransform="translate(0,0.25)"
+ spreadMethod="reflect"
+ gradientUnits="userSpaceOnUse"
+ y2="520.32812"
+ x2="327.78125"
+ y1="522.61218"
+ x1="308.5"
+ id="linearGradient6041"
+ xlink:href="#linearGradient6035"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientTransform="matrix(1.1818182,0,0,1.1818182,-31.65912,-123.63805)"
+ y2="527.33539"
+ x2="286.6308"
+ y1="518.55707"
+ x1="282.35706"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient6015"
+ xlink:href="#linearGradient5466"
+ inkscape:collect="always" />
+ <linearGradient
+ spreadMethod="reflect"
+ y2="511.96591"
+ x2="286.62845"
+ y1="511.96591"
+ x1="269.96979"
+ gradientTransform="matrix(1.1818182,0,0,1.1818182,-30.64896,-69.394391)"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient5493"
+ xlink:href="#linearGradient5495"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientTransform="matrix(1.1818182,0,0,1.1818182,-30.64896,-69.394391)"
+ y2="527.33539"
+ x2="286.6308"
+ y1="518.55707"
+ x1="282.35706"
+ gradientUnits="userSpaceOnUse"
+ id="linearGradient5490"
+ xlink:href="#linearGradient5466"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientUnits="userSpaceOnUse"
+ y2="532.00739"
+ x2="327.79306"
+ y1="532.00739"
+ x1="288.39856"
+ id="linearGradient5480"
+ xlink:href="#linearGradient5474"
+ inkscape:collect="always" />
+ <linearGradient
+ gradientUnits="userSpaceOnUse"
+ y2="527.33539"
+ x2="286.6308"
+ y1="518.55707"
+ x1="282.35706"
+ id="linearGradient5472"
+ xlink:href="#linearGradient5466"
+ inkscape:collect="always" />
+ <inkscape:perspective
+ sodipodi:type="inkscape:persp3d"
+ inkscape:vp_x="0 : 0.5 : 1"
+ inkscape:vp_y="0 : 1000 : 0"
+ inkscape:vp_z="1 : 0.5 : 1"
+ inkscape:persp3d-origin="0.5 : 0.33333333 : 1"
+ id="perspective5454" />
+ <inkscape:perspective
+ id="perspective5384"
+ inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
+ inkscape:vp_z="744.09448 : 526.18109 : 1"
+ inkscape:vp_y="0 : 1000 : 0"
+ inkscape:vp_x="0 : 526.18109 : 1"
+ sodipodi:type="inkscape:persp3d" />
+ <linearGradient
+ id="linearGradient5466"
+ inkscape:collect="always">
+ <stop
+ id="stop5468"
+ offset="0"
+ style="stop-color:#e3e3e3;stop-opacity:1" />
+ <stop
+ id="stop5470"
+ offset="1"
+ style="stop-color:#a5a5a8;stop-opacity:1" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient5474"
+ inkscape:collect="always">
+ <stop
+ id="stop5476"
+ offset="0"
+ style="stop-color:#c3c3c3;stop-opacity:1" />
+ <stop
+ style="stop-color:#808184;stop-opacity:1"
+ offset="0.38759774"
+ id="stop5482" />
+ <stop
+ id="stop5484"
+ offset="0.57053357"
+ style="stop-color:#7f7f84;stop-opacity:1" />
+ <stop
+ style="stop-color:#a5a6aa;stop-opacity:1"
+ offset="0.89746869"
+ id="stop5486" />
+ <stop
+ id="stop5478"
+ offset="1"
+ style="stop-color:#9b9b9e;stop-opacity:1" />
+ </linearGradient>
+ <linearGradient
+ inkscape:collect="always"
+ id="linearGradient5495">
+ <stop
+ style="stop-color:#c6c6c6;stop-opacity:1"
+ offset="0"
+ id="stop5497" />
+ <stop
+ id="stop5501"
+ offset="0.20484632"
+ style="stop-color:#e3e3e3;stop-opacity:1" />
+ <stop
+ style="stop-color:#a5a5a8;stop-opacity:1"
+ offset="1"
+ id="stop5499" />
+ </linearGradient>
+ <linearGradient
+ id="linearGradient6035">
+ <stop
+ id="stop6037"
+ offset="0"
+ style="stop-color:#ffffff;stop-opacity:1;" />
+ <stop
+ id="stop6039"
+ offset="1"
+ style="stop-color:#ffffff;stop-opacity:0;" />
+ </linearGradient>
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient5483"
+ id="linearGradient4559"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-198.23195,52.32021)"
+ x1="-13.709487"
+ y1="5.3772144"
+ x2="27.385256"
+ y2="-25.337072" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient11787"
+ id="linearGradient4561"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-331.4237,73.06709)"
+ x1="158.42857"
+ y1="24.964285"
+ x2="158.40045"
+ y2="-11.642858" />
+ <radialGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient17172"
+ id="radialGradient4563"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="matrix(0.103799,0.0814516,-0.214019,0.272739,-132.2014,63.74477)"
+ cx="-164.86122"
+ cy="72.644211"
+ fx="-164.86122"
+ fy="72.644211"
+ r="15.008935" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient10894"
+ id="linearGradient4565"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-331.4237,73.06709)"
+ x1="161.20535"
+ y1="-10.794643"
+ x2="159.78572"
+ y2="13.3125" />
+ <radialGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient13597"
+ id="radialGradient4567"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="matrix(0.7193,-0.0171987,0.03513213,1.469327,-44.059406,-19.60001)"
+ cx="-165.2417"
+ cy="33.695477"
+ fx="-165.2417"
+ fy="33.695477"
+ r="21.607157" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient7301"
+ id="linearGradient4569"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-327.9158,73.06709)"
+ x1="160.12111"
+ y1="-8.0820084"
+ x2="164.94254"
+ y2="-67.703445" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient14503"
+ id="linearGradient4571"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(1.7539475,0)"
+ x1="-247.27679"
+ y1="16.79554"
+ x2="-172.04314"
+ y2="48.75983" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient5483"
+ id="linearGradient4605"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-198.23195,52.32021)"
+ x1="-13.709487"
+ y1="5.3772144"
+ x2="27.385256"
+ y2="-25.337072" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient11787"
+ id="linearGradient4607"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-331.4237,73.06709)"
+ x1="158.42857"
+ y1="24.964285"
+ x2="158.40045"
+ y2="-11.642858" />
+ <radialGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient17172"
+ id="radialGradient4609"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="matrix(0.103799,0.0814516,-0.214019,0.272739,-132.2014,63.74477)"
+ cx="-164.86122"
+ cy="72.644211"
+ fx="-164.86122"
+ fy="72.644211"
+ r="15.008935" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient10894"
+ id="linearGradient4611"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-331.4237,73.06709)"
+ x1="161.20535"
+ y1="-10.794643"
+ x2="159.78572"
+ y2="13.3125" />
+ <radialGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient13597"
+ id="radialGradient4613"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="matrix(0.7193,-0.0171987,0.03513213,1.469327,-44.059406,-19.60001)"
+ cx="-165.2417"
+ cy="33.695477"
+ fx="-165.2417"
+ fy="33.695477"
+ r="21.607157" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient7301"
+ id="linearGradient4615"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-327.9158,73.06709)"
+ x1="160.12111"
+ y1="-8.0820084"
+ x2="164.94254"
+ y2="-67.703445" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient14503"
+ id="linearGradient4617"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(1.7539475,0)"
+ x1="-247.27679"
+ y1="16.79554"
+ x2="-172.04314"
+ y2="48.75983" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient5483"
+ id="linearGradient4619"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-198.23195,52.32021)"
+ x1="-13.709487"
+ y1="5.3772144"
+ x2="27.385256"
+ y2="-25.337072" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient11787"
+ id="linearGradient4621"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-331.4237,73.06709)"
+ x1="158.42857"
+ y1="24.964285"
+ x2="158.40045"
+ y2="-11.642858" />
+ <radialGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient17172"
+ id="radialGradient4623"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="matrix(0.103799,0.0814516,-0.214019,0.272739,-132.2014,63.74477)"
+ cx="-164.86122"
+ cy="72.644211"
+ fx="-164.86122"
+ fy="72.644211"
+ r="15.008935" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient10894"
+ id="linearGradient4625"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-331.4237,73.06709)"
+ x1="161.20535"
+ y1="-10.794643"
+ x2="159.78572"
+ y2="13.3125" />
+ <radialGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient13597"
+ id="radialGradient4627"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="matrix(0.7193,-0.0171987,0.03513213,1.469327,-44.059406,-19.60001)"
+ cx="-165.2417"
+ cy="33.695477"
+ fx="-165.2417"
+ fy="33.695477"
+ r="21.607157" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient7301"
+ id="linearGradient4629"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(-327.9158,73.06709)"
+ x1="160.12111"
+ y1="-8.0820084"
+ x2="164.94254"
+ y2="-67.703445" />
+ <linearGradient
+ inkscape:collect="always"
+ xlink:href="#linearGradient14503"
+ id="linearGradient4631"
+ gradientUnits="userSpaceOnUse"
+ gradientTransform="translate(1.7539475,0)"
+ x1="-247.27679"
+ y1="16.79554"
+ x2="-172.04314"
+ y2="48.75983" />
+ </defs>
+ <sodipodi:namedview
+ id="base"
+ pagecolor="#ffffff"
+ bordercolor="#666666"
+ borderopacity="1.0"
+ inkscape:pageopacity="0.0"
+ inkscape:pageshadow="2"
+ inkscape:zoom="0.75658575"
+ inkscape:cx="606.47078"
+ inkscape:cy="761.2996"
+ inkscape:document-units="px"
+ inkscape:current-layer="layer1"
+ showgrid="false"
+ inkscape:snap-global="false"
+ showguides="true"
+ inkscape:guide-bbox="true"
+ inkscape:window-width="1364"
+ inkscape:window-height="747"
+ inkscape:window-x="0"
+ inkscape:window-y="19"
+ inkscape:window-maximized="0">
+ <inkscape:grid
+ type="xygrid"
+ id="grid4194"
+ empspacing="5"
+ visible="true"
+ enabled="true"
+ snapvisiblegridlinesonly="true"
+ spacingx="0.1px"
+ spacingy="0.1px"
+ dotted="true" />
+ </sodipodi:namedview>
+ <metadata
+ id="metadata7">
+ <rdf:RDF>
+ <cc:Work
+ rdf:about="">
+ <dc:format>image/svg+xml</dc:format>
+ <dc:type
+ rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+ <dc:title></dc:title>
+ </cc:Work>
+ </rdf:RDF>
+ </metadata>
+ <g
+ inkscape:label="Layer 1"
+ inkscape:groupmode="layer"
+ id="layer1"
+ transform="translate(0,-0.00216797)"
+ style="display:inline">
+ <g
+ transform="matrix(0.68415603,0,0,0.68415603,387.57682,-250.1076)"
+ id="layer1-4"
+ inkscape:label="Layer 1">
+ <g
+ transform="matrix(4.1992341,0,0,4.1992341,-914.55576,-1633.811)"
+ id="g6097">
+ <path
+ transform="matrix(1.1818182,0,0,1.1818182,-30.64896,-65.983596)"
+ d="m 303.29832,521.77954 a 16.667517,5.5558391 0 1 1 -33.33504,0 16.667517,5.5558391 0 1 1 33.33504,0 z"
+ sodipodi:ry="5.5558391"
+ sodipodi:rx="16.667517"
+ sodipodi:cy="521.77954"
+ sodipodi:cx="286.6308"
+ id="path6079"
+ style="fill:#2e3436;fill-opacity:1;stroke:none;filter:url(#filter6093)"
+ sodipodi:type="arc" />
+ <path
+ style="fill:url(#linearGradient6110);fill-opacity:1;stroke:none"
+ d="m 288.40625,517.5 0,30.09191 0.125,0 c -0.0806,0.24126 -0.125,0.47032 -0.125,0.71875 0,3.6263 8.80861,6.5625 19.6875,6.5625 10.87889,0 19.6875,-2.9362 19.6875,-6.5625 0,-0.24879 -0.0442,-0.47715 -0.125,-0.71875 l 0.125,0 0,-30.09191 -39.375,0 z"
+ id="path5488"
+ sodipodi:nodetypes="cccssscccc"
+ inkscape:connector-curvature="0" />
+ <path
+ sodipodi:type="arc"
+ style="fill:url(#linearGradient6112);fill-opacity:1;stroke:none"
+ id="path5460"
+ sodipodi:cx="286.6308"
+ sodipodi:cy="521.77954"
+ sodipodi:rx="16.667517"
+ sodipodi:ry="5.5558391"
+ d="m 303.29832,521.77954 a 16.667517,5.5558391 0 1 1 -33.33504,0 16.667517,5.5558391 0 1 1 33.33504,0 z"
+ transform="matrix(1.1818182,0,0,1.1818182,-30.64896,-99.394391)" />
+ <path
+ style="fill:#565656;fill-opacity:1;stroke:none"
+ d="m 288.375,539.09375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -3.45152,2.93589 -10.95919,4.96875 -19.6875,4.96875 -8.74612,0 -16.27686,-2.05444 -19.71875,-5 z"
+ id="path6026"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#linearGradient6114);fill-opacity:1;stroke:none"
+ d="m 288.375,517.34375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -0.21572,0.18349 -0.44078,0.35509 -0.6875,0.53125 -0.009,0.0117 -0.0216,0.0196 -0.0312,0.0312 -2.29214,2.77744 -9.90349,4.8125 -18.96875,4.8125 -9.12203,0 -16.78563,-2.07074 -19.03125,-4.875 -0.0249,-0.0179 -0.038,-0.0446 -0.0625,-0.0625 -0.21872,-0.15969 -0.43159,-0.30323 -0.625,-0.46875 z"
+ id="path6030"
+ inkscape:connector-curvature="0" />
+ <g
+ id="g6071">
+ <g
+ id="g6067"
+ transform="translate(0,-0.52315203)">
+ <path
+ id="path6022"
+ d="m 288.375,529.09375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -3.45152,2.93589 -10.95919,4.96875 -19.6875,4.96875 -8.74612,0 -16.27686,-2.05444 -19.71875,-5 z"
+ style="fill:#565656;fill-opacity:1;stroke:none"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#linearGradient6116);fill-opacity:1;stroke:none"
+ d="m 288.375,529.09375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -0.0497,0.0422 -0.10543,0.0838 -0.15625,0.125 -1.24216,3.22677 -9.51064,5.71875 -19.53125,5.71875 -10.11275,0 -18.46774,-2.51121 -19.59375,-5.78125 -0.0401,-0.0317 -0.0863,-0.0607 -0.125,-0.0937 z"
+ id="path6043"
+ inkscape:connector-curvature="0" />
+ </g>
+ <path
+ style="fill:url(#linearGradient6118);fill-opacity:1;stroke:none"
+ d="m 288.375,539.09375 c 0.14735,3.58398 8.93182,6.46875 19.71875,6.46875 10.75628,0 19.4918,-2.86766 19.6875,-6.4375 -0.0497,0.0422 -0.10543,0.0838 -0.15625,0.125 -1.24216,3.22677 -9.51064,5.71875 -19.53125,5.71875 -10.11275,0 -18.46774,-2.51121 -19.59375,-5.78125 -0.0401,-0.0317 -0.0863,-0.0607 -0.125,-0.0937 z"
+ id="path6054"
+ inkscape:connector-curvature="0" />
+ </g>
+ <path
+ style="fill:#565656;fill-opacity:1;stroke:none"
+ d="m 288.5,549.9375 c 1.12601,3.27004 9.481,5.78125 19.59375,5.78125 10.02061,0 18.28909,-2.49198 19.53125,-5.71875 -3.51634,2.86779 -10.92856,4.84375 -19.53125,4.84375 -8.64783,0 -16.10003,-2.01374 -19.59375,-4.90625 z"
+ id="path6060"
+ inkscape:connector-curvature="0" />
+ </g>
+ </g>
+ <g
+ id="layer1-1"
+ inkscape:label="Ebene 1"
+ transform="matrix(0.72220204,0,0,0.72220204,132.27534,121.05237)">
+ <g
+ transform="matrix(1.140285,0,0,1.140285,257.5128,9.583516)"
+ id="g17180">
+ <path
+ style="fill:url(#linearGradient4619);fill-opacity:1;fill-rule:evenodd;stroke:none"
+ d="m -147.33901,25.709573 c 1.60248,-11.000871 -4.47637,-25.92402727 -21.36656,-26.24812697 -21.91736,-0.42056427 -25.99283,15.37022297 -24.88152,27.15852797 1.35349,14.35731 43.43226,18.41994 46.24808,-0.910401 z"
+ id="path12688"
+ sodipodi:nodetypes="csss"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#linearGradient4621);fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
+ d="m -222.67372,95.620662 c 2.44913,-6.76266 3.53352,-19.316348 11.96428,-23.507891 l 39.10715,-8.367105 40.84427,7.763769 c 7.18714,2.580184 10.58445,16.564047 14.02048,24.487407 -2.23825,1.60676 -4.16734,3.98641 -6.82904,4.534538 l -92.67857,0 c -3.00971,-1.116788 -4.53412,-3.124768 -6.42857,-4.910718 z"
+ id="path12692"
+ sodipodi:nodetypes="cccccccc"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#radialGradient4623);fill-opacity:1;fill-rule:evenodd;stroke:url(#linearGradient4625);stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
+ d="m -183.12015,55.084952 c 0.20847,5.059484 -0.99076,7.975428 -3.3611,12.263909 9.22895,16.963145 33.15006,8.218841 32.52577,-0.478195 l -2.64681,-14.464286 -26.51786,2.678572 z"
+ id="path12694"
+ sodipodi:nodetypes="ccccc"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#radialGradient4627);fill-opacity:1;fill-rule:evenodd;stroke:url(#linearGradient4629);stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
+ d="m -149.37964,27.913445 c -0.51037,7.997041 -0.7342,17.748029 -2.52538,25.74507 0,0 -8.14428,7.402937 -12.69005,9.420866 -4.54577,2.017929 -5.81808,1.744272 -10.10153,-0.06313 -4.28344,-1.807406 -14.20527,-8.852654 -14.20527,-8.852654 -4.26434,-17.290001 -5.7232,-35.412143 13.25826,-45.0642384 l 5.62,6.6745734 c 2.0794,2.469598 11.20933,6.30898 14.65825,3.016129 2.7221,-2.598909 4.38415,6.931223 5.98572,9.123389 z"
+ id="path12696"
+ sodipodi:nodetypes="cczzccssc"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#linearGradient4631);fill-opacity:1;fill-rule:evenodd;stroke:none"
+ d="m -189.88923,29.284383 c -0.7068,8.01587 0.46446,15.673295 2.23958,23.851961 4.89236,3.952642 8.6008,9.167299 18.81302,7.080731 3.49665,-0.796865 2.20012,-2.468331 4.20841,-3.477821 -12.07205,3.58663 -14.04134,1.050382 -20.26382,-6.252832 l -4.10785,-23.873488 -0.88934,2.671449 z"
+ id="path13605"
+ sodipodi:nodetypes="ccccccc"
+ inkscape:connector-curvature="0" />
+ </g>
+ </g>
+ <text
+ xml:space="preserve"
+ style="font-size:40px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ x="75.275787"
+ y="188.31525"
+ id="text4196"
+ sodipodi:linespacing="125%"><tspan
+ sodipodi:role="line"
+ id="tspan4198"
+ x="75.275787"
+ y="188.31525"
+ style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana">x1</tspan><tspan
+ sodipodi:role="line"
+ x="75.275787"
+ y="238.31525"
+ id="tspan4200" /></text>
+ <g
+ transform="matrix(0.72220204,0,0,0.72220204,132.27534,262.19428)"
+ inkscape:label="Ebene 1"
+ id="g4529">
+ <g
+ id="g4531"
+ transform="matrix(1.140285,0,0,1.140285,257.5128,9.583516)">
+ <path
+ inkscape:connector-curvature="0"
+ sodipodi:nodetypes="csss"
+ id="path4533"
+ d="m -147.33901,25.709573 c 1.60248,-11.000871 -4.47637,-25.92402727 -21.36656,-26.24812697 -21.91736,-0.42056427 -25.99283,15.37022297 -24.88152,27.15852797 1.35349,14.35731 43.43226,18.41994 46.24808,-0.910401 z"
+ style="fill:url(#linearGradient4559);fill-opacity:1;fill-rule:evenodd;stroke:none" />
+ <path
+ inkscape:connector-curvature="0"
+ sodipodi:nodetypes="cccccccc"
+ id="path4535"
+ d="m -222.67372,95.620662 c 2.44913,-6.76266 3.53352,-19.316348 11.96428,-23.507891 l 39.10715,-8.367105 40.84427,7.763769 c 7.18714,2.580184 10.58445,16.564047 14.02048,24.487407 -2.23825,1.60676 -4.16734,3.98641 -6.82904,4.534538 l -92.67857,0 c -3.00971,-1.116788 -4.53412,-3.124768 -6.42857,-4.910718 z"
+ style="fill:url(#linearGradient4561);fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ sodipodi:nodetypes="ccccc"
+ id="path4537"
+ d="m -183.12015,55.084952 c 0.20847,5.059484 -0.99076,7.975428 -3.3611,12.263909 9.22895,16.963145 33.15006,8.218841 32.52577,-0.478195 l -2.64681,-14.464286 -26.51786,2.678572 z"
+ style="fill:url(#radialGradient4563);fill-opacity:1;fill-rule:evenodd;stroke:url(#linearGradient4565);stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ sodipodi:nodetypes="cczzccssc"
+ id="path4539"
+ d="m -149.37964,27.913445 c -0.51037,7.997041 -0.7342,17.748029 -2.52538,25.74507 0,0 -8.14428,7.402937 -12.69005,9.420866 -4.54577,2.017929 -5.81808,1.744272 -10.10153,-0.06313 -4.28344,-1.807406 -14.20527,-8.852654 -14.20527,-8.852654 -4.26434,-17.290001 -5.7232,-35.412143 13.25826,-45.0642384 l 5.62,6.6745734 c 2.0794,2.469598 11.20933,6.30898 14.65825,3.016129 2.7221,-2.598909 4.38415,6.931223 5.98572,9.123389 z"
+ style="fill:url(#radialGradient4567);fill-opacity:1;fill-rule:evenodd;stroke:url(#linearGradient4569);stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1" />
+ <path
+ inkscape:connector-curvature="0"
+ sodipodi:nodetypes="ccccccc"
+ id="path4541"
+ d="m -189.88923,29.284383 c -0.7068,8.01587 0.46446,15.673295 2.23958,23.851961 4.89236,3.952642 8.6008,9.167299 18.81302,7.080731 3.49665,-0.796865 2.20012,-2.468331 4.20841,-3.477821 -12.07205,3.58663 -14.04134,1.050382 -20.26382,-6.252832 l -4.10785,-23.873488 -0.88934,2.671449 z"
+ style="fill:url(#linearGradient4571);fill-opacity:1;fill-rule:evenodd;stroke:none" />
+ </g>
+ </g>
+ <text
+ sodipodi:linespacing="125%"
+ id="text4553"
+ y="329.45715"
+ x="75.275787"
+ style="font-size:40px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ xml:space="preserve"><tspan
+ style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana"
+ y="329.45715"
+ x="75.275787"
+ id="tspan4555"
+ sodipodi:role="line">x2</tspan><tspan
+ id="tspan4557"
+ y="379.45715"
+ x="75.275787"
+ sodipodi:role="line" /></text>
+ <g
+ id="g4575"
+ inkscape:label="Ebene 1"
+ transform="matrix(0.72220204,0,0,0.72220204,132.27534,403.33618)">
+ <g
+ transform="matrix(1.140285,0,0,1.140285,257.5128,9.583516)"
+ id="g4577">
+ <path
+ style="fill:url(#linearGradient4605);fill-opacity:1;fill-rule:evenodd;stroke:none"
+ d="m -147.33901,25.709573 c 1.60248,-11.000871 -4.47637,-25.92402727 -21.36656,-26.24812697 -21.91736,-0.42056427 -25.99283,15.37022297 -24.88152,27.15852797 1.35349,14.35731 43.43226,18.41994 46.24808,-0.910401 z"
+ id="path4579"
+ sodipodi:nodetypes="csss"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#linearGradient4607);fill-opacity:1;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
+ d="m -222.67372,95.620662 c 2.44913,-6.76266 3.53352,-19.316348 11.96428,-23.507891 l 39.10715,-8.367105 40.84427,7.763769 c 7.18714,2.580184 10.58445,16.564047 14.02048,24.487407 -2.23825,1.60676 -4.16734,3.98641 -6.82904,4.534538 l -92.67857,0 c -3.00971,-1.116788 -4.53412,-3.124768 -6.42857,-4.910718 z"
+ id="path4581"
+ sodipodi:nodetypes="cccccccc"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#radialGradient4609);fill-opacity:1;fill-rule:evenodd;stroke:url(#linearGradient4611);stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
+ d="m -183.12015,55.084952 c 0.20847,5.059484 -0.99076,7.975428 -3.3611,12.263909 9.22895,16.963145 33.15006,8.218841 32.52577,-0.478195 l -2.64681,-14.464286 -26.51786,2.678572 z"
+ id="path4583"
+ sodipodi:nodetypes="ccccc"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#radialGradient4613);fill-opacity:1;fill-rule:evenodd;stroke:url(#linearGradient4615);stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
+ d="m -149.37964,27.913445 c -0.51037,7.997041 -0.7342,17.748029 -2.52538,25.74507 0,0 -8.14428,7.402937 -12.69005,9.420866 -4.54577,2.017929 -5.81808,1.744272 -10.10153,-0.06313 -4.28344,-1.807406 -14.20527,-8.852654 -14.20527,-8.852654 -4.26434,-17.290001 -5.7232,-35.412143 13.25826,-45.0642384 l 5.62,6.6745734 c 2.0794,2.469598 11.20933,6.30898 14.65825,3.016129 2.7221,-2.598909 4.38415,6.931223 5.98572,9.123389 z"
+ id="path4585"
+ sodipodi:nodetypes="cczzccssc"
+ inkscape:connector-curvature="0" />
+ <path
+ style="fill:url(#linearGradient4617);fill-opacity:1;fill-rule:evenodd;stroke:none"
+ d="m -189.88923,29.284383 c -0.7068,8.01587 0.46446,15.673295 2.23958,23.851961 4.89236,3.952642 8.6008,9.167299 18.81302,7.080731 3.49665,-0.796865 2.20012,-2.468331 4.20841,-3.477821 -12.07205,3.58663 -14.04134,1.050382 -20.26382,-6.252832 l -4.10785,-23.873488 -0.88934,2.671449 z"
+ id="path4587"
+ sodipodi:nodetypes="ccccccc"
+ inkscape:connector-curvature="0" />
+ </g>
+ </g>
+ <text
+ xml:space="preserve"
+ style="font-size:40px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ x="75.275787"
+ y="470.59906"
+ id="text4599"
+ sodipodi:linespacing="125%"><tspan
+ sodipodi:role="line"
+ id="tspan4601"
+ x="75.275787"
+ y="470.59906"
+ style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana">x3</tspan><tspan
+ sodipodi:role="line"
+ x="75.275787"
+ y="520.59906"
+ id="tspan4603" /></text>
+ <path
+ style="fill:none;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;marker-end:url(#Arrow2Mend)"
+ d="m 320.19964,169.77456 254.2406,0"
+ id="path4633"
+ inkscape:connector-curvature="0"
+ mask="none" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path5265"
+ d="M 325.93148,316.3562 572.86629,188.87701"
+ style="fill:none;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;marker-end:url(#Arrow2Mend)"
+ mask="none" />
+ <path
+ inkscape:connector-curvature="0"
+ id="path5271"
+ d="M 323.07593,451.978 575.40831,208.79379"
+ style="fill:none;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;marker-end:url(#Arrow2Mend)" />
+ <path
+ style="fill:none;stroke:#000000;stroke-width:6;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;marker-mid:none;marker-end:url(#Arrow2Mend)"
+ d="m 646.96052,244.78681 0,134.81618"
+ id="path5297"
+ inkscape:connector-curvature="0" />
+ <g
+ id="g5865"
+ transform="translate(-15.531454,0)">
+ <rect
+ y="397.80536"
+ x="559.4549"
+ height="103.09473"
+ width="206.18945"
+ id="rect5851"
+ style="fill:none;stroke:#000000;stroke-width:6;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none" />
+ <text
+ sodipodi:linespacing="125%"
+ id="text5853"
+ y="437.75897"
+ x="662.43243"
+ style="font-size:40px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ xml:space="preserve"><tspan
+ style="font-size:32px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;text-anchor:middle;font-family:Verdana;-inkscape-font-specification:Verdana"
+ y="437.75897"
+ x="662.43243"
+ id="tspan5855"
+ sodipodi:role="line">Data mining</tspan><tspan
+ style="font-size:32px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;text-anchor:middle;font-family:Verdana;-inkscape-font-specification:Verdana"
+ id="tspan5857"
+ y="477.75897"
+ x="662.43243"
+ sodipodi:role="line">engine</tspan></text>
+ </g>
+ <g
+ style="display:inline"
+ id="g4543"
+ transform="translate(0,141.14185)">
+ <g
+ id="g4547">
+ <text
+ sodipodi:linespacing="125%"
+ id="text4549"
+ y="188.31531"
+ x="252.366"
+ style="font-size:40px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ xml:space="preserve"><tspan
+ style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana"
+ y="188.31531"
+ x="252.366"
+ id="tspan4551"
+ sodipodi:role="line">y2</tspan></text>
+ </g>
+ </g>
+ <g
+ style="display:inline"
+ id="g4500"
+ transform="translate(0,-6.104e-5)">
+ <text
+ sodipodi:linespacing="125%"
+ id="text4190"
+ y="188.31531"
+ x="252.366"
+ style="font-size:40px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ xml:space="preserve"><tspan
+ style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana"
+ y="188.31531"
+ x="252.366"
+ id="tspan4192"
+ sodipodi:role="line">y1</tspan></text>
+ </g>
+ <g
+ style="display:inline"
+ id="g4593"
+ transform="translate(0,282.28375)">
+ <text
+ sodipodi:linespacing="125%"
+ id="text4595"
+ y="188.31531"
+ x="252.366"
+ style="font-size:40px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ xml:space="preserve"><tspan
+ style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana"
+ y="188.31531"
+ x="252.366"
+ id="tspan4597"
+ sodipodi:role="line">y3</tspan></text>
+ </g>
+ </g>
+ <g
+ inkscape:groupmode="layer"
+ id="layer6"
+ inkscape:label="boxes"
+ style="display:inline">
+ <rect
+ style="fill:none;stroke:#000000;stroke-width:3;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none"
+ id="rect3414"
+ width="74.021072"
+ height="74.021072"
+ x="238.37305"
+ y="136.506" />
+ <rect
+ transform="translate(0,141.13968)"
+ style="fill:none;stroke:#000000;stroke-width:3;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"
+ id="rect4545"
+ width="74.021072"
+ height="74.021072"
+ x="238.37305"
+ y="136.50822" />
+ <rect
+ style="fill:none;stroke:#000000;stroke-width:3;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none"
+ id="rect4591"
+ width="74.021072"
+ height="74.021072"
+ x="238.37305"
+ y="418.78979" />
+ </g>
+ <g
+ inkscape:groupmode="layer"
+ id="layer3"
+ inkscape:label="sellers"
+ style="display:none">
+ <text
+ transform="translate(0,-0.00216797)"
+ xml:space="preserve"
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ x="423.69418"
+ y="159.81699"
+ id="text5279"
+ sodipodi:linespacing="125%"><tspan
+ sodipodi:role="line"
+ id="tspan5281"
+ x="423.69418"
+ y="159.81699"
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana">c1$</tspan></text>
+ <text
+ sodipodi:linespacing="125%"
+ id="text9285"
+ y="541.96613"
+ x="75.831871"
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ xml:space="preserve"
+ transform="matrix(0.70710678,-0.70710678,0.70710678,0.70710678,0,-0.00216797)"><tspan
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana"
+ y="541.96613"
+ x="75.831871"
+ sodipodi:role="line"
+ id="tspan9289">c3$</tspan></text>
+ </g>
+ <g
+ inkscape:groupmode="layer"
+ id="layer5"
+ inkscape:label="seller2"
+ style="display:none">
+ <text
+ sodipodi:linespacing="125%"
+ id="text9316"
+ y="433.87756"
+ x="232.12007"
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ xml:space="preserve"
+ transform="matrix(0.8660254,-0.5,0.5,0.8660254,0,0)"
+ inkscape:transform-center-y="21.191452"><tspan
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana"
+ y="433.87756"
+ x="232.12007"
+ sodipodi:role="line"
+ id="tspan9320">c2$</tspan></text>
+ </g>
+ <g
+ inkscape:groupmode="layer"
+ id="layer4"
+ inkscape:label="buyer"
+ style="display:none">
+ <path
+ transform="translate(0,-0.00216797)"
+ mask="none"
+ inkscape:connector-curvature="0"
+ id="path5871"
+ d="m 320.19964,181.67011 254.2406,0"
+ style="fill:none;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;marker-start:url(#Arrow1Mstart);marker-mid:none;marker-end:none;display:inline" />
+ <path
+ transform="translate(0,-0.00216797)"
+ style="fill:none;stroke:#000000;stroke-width:3;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;marker-start:url(#Arrow1Mstart);marker-end:none;display:inline"
+ d="M 323.07593,467.83873 575.40831,224.65452"
+ id="path8101"
+ inkscape:connector-curvature="0" />
+ <text
+ transform="translate(0,-0.00216797)"
+ sodipodi:linespacing="125%"
+ id="text9281"
+ y="208.7209"
+ x="423.69418"
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ xml:space="preserve"><tspan
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana"
+ y="208.7209"
+ x="423.69418"
+ id="tspan9283"
+ sodipodi:role="line">p1$</tspan></text>
+ <text
+ transform="matrix(0.70710678,-0.70710678,0.70710678,0.70710678,0,-0.00216797)"
+ xml:space="preserve"
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Apple Garamond;-inkscape-font-specification:Apple Garamond"
+ x="64.616638"
+ y="592.43469"
+ id="text9293"
+ sodipodi:linespacing="125%"><tspan
+ id="tspan9295"
+ sodipodi:role="line"
+ x="64.616638"
+ y="592.43469"
+ style="font-size:28px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-family:Verdana;-inkscape-font-specification:Verdana">p2$</tspan></text>
+ <text
+ xml:space="preserve"
+ style="font-size:40px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;line-height:125%;letter-spacing:0px;word-spacing:0px;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Verdana;-inkscape-font-specification:Verdana"
+ x="715.05438"
+ y="181.34174"
+ id="text9324"
+ sodipodi:linespacing="125%"><tspan
+ sodipodi:role="line"
+ id="tspan9326"
+ x="715.05438"
+ y="181.34174">B$</tspan></text>
+ </g>
+</svg>
diff --git a/slides/slides.tex b/slides/slides.tex
index 81f6deb..1bccd02 100644
--- a/slides/slides.tex
+++ b/slides/slides.tex
@@ -4,21 +4,21 @@
\usepackage[LGR,T1]{fontenc}
\usepackage{amsmath}
\usepackage{algpseudocode,algorithm}
+\usepackage{graphicx}
\DeclareMathOperator*{\argmax}{arg\,max}
\usetheme{Boadilla}
-\usecolortheme{beaver}
-\title[Budget Feasible Mechanisms for Experimental Design]{Budget Feasible Mechanisms for Experimental Design}
-\author{xx\\ Joint work with yy and zz}
+\title[]{Budget Feasible Mechanisms for Experimental Design}
+\author[Thibaut Horel]{Thibaut Horel\\ Joint work with Stratis Ioannidis and S. Muthukrishnan}
\institute[]{}
\setbeamercovered{transparent}
-
-\AtBeginSection[]
-{
-\begin{frame}<beamer>
-\frametitle{Outline}
-\tableofcontents[currentsection]
-\end{frame}
-}
+\setbeamertemplate{navigation symbols}{}
+%\AtBeginSection[]
+%{
+%\begin{frame}<beamer>
+%\frametitle{Outline}
+%\tableofcontents[currentsection]
+%\end{frame}
+%}
\begin{document}
@@ -26,229 +26,214 @@
\maketitle
\end{frame}
-\begin{frame}
-\tableofcontents
-\end{frame}
+\section{Introduction}
-\section{Experimental Design}
-\begin{frame}{Experimental Design}
- An experimenter is about to conduct an experiment with users.
- \begin{itemize}
- \item $n$ users
- \item $x_i\in\mathbb{R}^d$: public features of user $i$
- \item $c_i\in\mathbb{R}^+$: cost of user $i$ for taking part in the experiment
- \end{itemize}
+\begin{frame}{Motivation}
+ \begin{center}
+ \includegraphics<1-4>[scale=0.5]{1.pdf}
+ \includegraphics<5>[scale=0.5]{2.pdf}
+ \includegraphics<6>[scale=0.5]{3.pdf}
+ \includegraphics<7>[scale=0.5]{4.pdf}
+ \end{center}
- When paid $c_i$, user $i$ reveals $y_i$:
- \begin{displaymath}
- y_i = \beta^T x_i + \varepsilon_i,\quad\beta\in\mathbb{R}^d,\;
- \varepsilon_i\sim\mathcal{N}(0,\sigma^2)
- \end{displaymath}
- $\beta$ is \alert{unknown} to the experimenter.
-
- \begin{block}{}
- \alert{Question:} budget constraint $B$, which users to pick to learn $\beta$ as
- well as possible without spending more than $B$?
- \end{block}
+ \begin{center}
+ \begin{overprint}
+ \onslide<1>\begin{center}$N$ users\end{center}
+ \onslide<2>
+ \begin{center}
+ $x_i\in\mathbb{R}^d$: public features (e.g. age, sex, height, etc.)
+ \end{center}
+ \onslide<3>
+ \begin{center}
+ $y_i\in\mathbb{R}$: private date (e.g. disease, etc.)
+ \end{center}
+ \onslide<4>
+ \begin{center}
+ Linear model: $y_i = \beta^Tx_i + \varepsilon_i$
+ \end{center}
+ \begin{displaymath}
+ \beta^* = \arg\min_\beta \sum_i |y_i-\beta^Tx_i|^2
+ \end{displaymath}
+ \end{overprint}
+ \end{center}
\end{frame}
-\begin{frame}{Evaluation criterion}
- \begin{block}{}
- \alert{Question:} How to measure the helpfulness of a set of users $S$ in learning $\beta$?
- \end{block}
-
- \vspace{0.5cm}
- Bayesian approach:
+\begin{frame}{Challenges}
\begin{itemize}
- \item \emph{a priori} knowledge: prior distribution over $\beta$
- \item the entropy of $\beta$, $H(\beta)$ measures the uncertainty of the experimenter
- \item after observing $Y_S = \{y_i,\; i\in S\}$, uncertainty becomes $H(\beta\mid Y_S)$
+ \item Value of data?
+ \vspace{1cm}
+ \pause
+ \item How to optimize it?
+ \vspace{1cm}
+ \pause
+ \item Strategic users?
\end{itemize}
-
- \vspace{0.5cm}
-
- The value of $S$ is the \alert{entropy reduction}:
- \begin{displaymath}
- V(S) = H(\beta) - H(\beta\mid Y_S)
- \end{displaymath}
\end{frame}
-\begin{frame}{Value function}
- Gaussian linear model:
- \begin{displaymath}
- y_i = \beta^T x_i + \varepsilon_i,\quad\beta\in\mathbb{R}^d,\;
- \varepsilon_i\sim\mathcal{N}(0,\sigma^2)
- \end{displaymath}
-
- Typical prior distribution $\beta\sim\mathcal{N}(0,\tau I_d)$
-
- \vspace{0.5cm}
-
- \begin{block}{}
- Under the Gaussian linear model and Gaussian prior distribution:
- \begin{displaymath}
- V(S) = \log\det\Big(I_d + \lambda\sum_{i\in S}x_i x_i^T \Big)
- \end{displaymath}
- \end{block}
-
- \vspace{0.5cm}
-
- \alert{Remark:} $V$ can be computed efficiently using a Cholesky decomposition
+\begin{frame}{Contributions}
+ \begin{itemize}
+ \item case of the linear regression
+ \vspace{1cm}
+ \pause
+ \item deterministic mechanism
+ \vspace{1cm}
+ \pause
+ \item generalization (randomized mechanism)
+ \end{itemize}
\end{frame}
-\section{Non-strategic case}
-\begin{frame}{Optimization Problem}
- \begin{block}{P1}
- \begin{align*}
- &\text{maximize}\; V(S) = \log\det\Big(I_d + \lambda\sum_{i\in S}x_i x_i^T \Big)\\
- &\text{subject to}\; \sum_{i\in S}c_i\leq B\quad\text{(Knapsack constraint)}
- \end{align*}
- \end{block}
+\section{Budget feasible mechanism design}
- \onslide<2->
- Good news:
-
- $V$ is submodular (diminishing return):
- \begin{displaymath}
- \forall S\subseteq T\, \forall i,\; V(S\cup\{i\}) - V(S)\geq
- V(T\cup\{i\}) - V(T)
- \end{displaymath}
-
- \onslide<3->
- Bad news:
-
- Maximizing a submodular function under a knapsack constraint is NP-hard (even
- in the specific case of $\log\det$)
+\begin{frame}{Outline}
+\tableofcontents
\end{frame}
-\begin{frame}{Approximation}
- \begin{definition}[Approximation ratio]
- Let $OPT$ denote the optimal solution to P1, $S$ is an $\alpha$-approximation
- if:
- \begin{displaymath}
- V(OPT)\leq \alpha V(S)
- \end{displaymath}
- \end{definition}
-
- \vspace{0.5cm}
-
- \begin{theorem}[Sviridenko]
- \begin{enumerate}
- \item There is an algorithm which returns a set $S$ which is a $\frac{e}{e-1}$-approximation
- \item No algorithm can do better unless P=NP
- \end{enumerate}
- \end{theorem}
-
- \vspace{0.5cm}
-
- The algorithm is a combination of an enumeration method and a greedy heuristic.
+\begin{frame}{Outline}
+ \tableofcontents[currentsection]
\end{frame}
-\begin{frame}{Greedy algorithm}
- \begin{block}{Greedy($V$, $B$)}
- \begin{algorithmic}
- \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
- \State $S \gets \emptyset$
- \While{$c_i\leq B - \sum_{j\in S} c_j$}
- \State $S \gets S\cup\{i\}$
- \State $i \gets \argmax_{1\leq j\leq n}
- \frac{V(S\cup\{j\})-V(S)}{c_j}$
- \EndWhile
- \State \textbf{return} $S$
- \end{algorithmic}
- \end{block}
+\begin{frame}{Reverse auction}
+\begin{itemize}
+ \item set of $N$ sellers $\mathcal{A} = \{1,\ldots,N\}$ and a buyer
+ \vspace{0.3cm}
+ \pause
+ \item $V$ value function of the buyer, $V:2^\mathcal{A}\rightarrow \mathbb{R}^+$
+ \vspace{0.3cm}
+ \pause
+ \item $c_i\in\mathbb{R}^+$ price of seller's $i$ good
+ \vspace{0.3cm}
+ \pause
+ \item $B$ budget constraint of the buyer
+\end{itemize}
- \vspace{0.5cm}
+\vspace{0.5cm}
+\pause
- \begin{lemma}
- Greedy has an \alert{unbounded} approximation ratio.
- \end{lemma}
+\begin{block}{Goal}
+ \begin{itemize}
+ \item Find $S\subset \mathcal{A}$ \alert{maximizing} $V(S)$
+ \vspace{0.3cm}
+ \item Find \alert{payment} $p_i$ to seller $i$
+ \end{itemize}
+\end{block}
\end{frame}
-\begin{frame}
- \begin{block}{MaxGreedy}
- \begin{algorithmic}
- \State $i^* \gets \argmax_{1\leq j\leq n} V(j)$
- \State $S \gets$ Greedy($V$, $B$)
- \If{$V(i^*)\geq V(S)$}
- \State \textbf{return} $\{i^*\}$
- \Else
- \State \textbf{return} $S$
- \EndIf
- \end{algorithmic}
- \end{block}
+\begin{frame}{Objectives}
+ Payments $(p_i)_{i\in S}$ must be:
+ \pause
+ \vspace{0.3cm}
+ \begin{itemize}
+ \item individually rational: $p_i\geq c_i,\;i\in S$
+ \vspace{0.2cm}
+ \pause
+ \item truthful: reporting one's true cost is a dominant strategy
+ \vspace{0.2cm}
+ \pause
+ \item budget feasible: $\sum_{i\in S} p_i \leq B$
+ \vspace{0.2cm}
+ \end{itemize}
- \vspace{0.5cm}
+ \pause
+ \vspace{0.3cm}
- \begin{lemma}
- MaxGreedy is a $\frac{5e}{e-1}$ approximation
- \end{lemma}
+ Mechanism must be:
+ \vspace{0.3cm}
+ \pause
+ \begin{itemize}
+ \item computationally efficient: polynomial time
+ \pause
+ \vspace{0.2cm}
+ \item good approximation: $V(OPT) \leq \alpha V(S)$ with:
+ \begin{displaymath}
+ OPT = \arg\max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\}
+ \end{displaymath}
+ \end{itemize}
\end{frame}
-\section{Strategic case}
-
-\begin{frame}{Reverse auction}
+\begin{frame}{Known results}
+ When $V$ is submodular:
+ \vspace{1cm}
+ \pause
+ \begin{itemize}
+ \item \alert{randomized} budget feasible mechanism,
+ approximation ratio: $7.91$ (Chen et al., 2011)
+ \vspace{1cm}
+ \pause
+ \item \alert{deterministic} mechanisms for:
+ \vspace{0.3cm}
+ \begin{itemize}
+ \item Knapsack: $2+\sqrt{2}$ (Chen et al., 2011)
+ \vspace{0.3cm}
+ \item Matching: 7.37 (Singer, 2010)
+ \vspace{0.3cm}
+ \item Coverage: 31 (Singer, 2012)
+ \vspace{0.3cm}
+ \end{itemize}
+ \end{itemize}
+\end{frame}
- \alert{Problem:} In real life, user are strategic agents. They lie about their costs.
- This is a \alert{reverse auction}: the experimenter wants to buy data
- from users.
+\section{Budget feasible mechanism for linear regression}
- \vspace{0.5cm}
+\begin{frame}{Outline}
+ \tableofcontents[currentsection]
+\end{frame}
- \alert{Goal:} Design an auction mechanism:
+\begin{frame}{Linear regression}
+ Each user $i\in\mathcal{A}$ has:
\begin{itemize}
- \item a selection rule $s: (c_1,\ldots,c_n) \mapsto (s_1,\ldots,s_n)$,
- $s_i\in\{0,1\}$
- \item a payment rule $p: (c_1,\ldots,c_n) \mapsto (p_1,\ldots,p_n)$,
- $p_i\in\mathbb{R}^+$
+ \item Public feature vector $x_i\in\mathbb{R}^d$
+ \item Private data $y_i\in\mathbb{R}$
\end{itemize}
+ \pause
\vspace{0.5cm}
- As usual in auction mechanism design, we want payments to be:
- \begin{itemize}
- \item individually rational: $p_i\geq c_i$
- \item truthful: reporting one's true cost is a dominant strategy
- \item normalized: $s_i=0$ implies $p_i=0$
- \end{itemize}
-\end{frame}
+ Gaussian linear model:
+ \begin{displaymath}
+ y_i = \beta^T x_i + \varepsilon_i,\quad\beta\in\mathbb{R}^d,\;
+ \varepsilon_i\sim\mathcal{N}(0,\sigma^2)
+ \end{displaymath}
-\begin{frame}{Optimization problem for budget feasible auctions}
- \begin{block}{P2}
- \begin{align*}
- &\text{maximize}\; V\big(s(c_1,\ldots,c_n)\big) = \log\det\Big(I_d + \lambda\sum_{i\in S}x_i x_i^T \Big)\\
- &\text{subject to}\; \sum_{i\in S}\alert{p_i}\leq B\quad\text{(budget feasible)}
- \end{align*}
- where the payments are further constrained to be individually rational, truthful
- and normalized
- \end{block}
+ \pause
+ \vspace{0.5cm}
- \vspace{1cm}
+ Which users to select?\pause{} Experimental design $\Rightarrow$ D-optimal criterion
- This is again NP-hard $\Rightarrow$ we seek good approximation ratios
+ \vspace{0.5cm}
+
+ \begin{block}{Experimental Design}
+ \begin{displaymath}
+ \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right),\quad S\subset\mathcal{A}
+ \end{displaymath}
+ \end{block}
\end{frame}
-\begin{frame}{Myerson's theorem}
- \begin{theorem}[Myerson]
- Let $(s, p)$ be a mechanism. If:
- \begin{itemize}
- \item $s$ is \alert{monotonic}: if $c_i\leq c_i'$ then $s_i \geq s_i'$
- \item users are paid \alert{threshold payments}: $p_i = \inf\{c_i':i\notin s(c_i',c_{-i})\}$
- \end{itemize}
- Then, the mechanism is individually rational and truthful.
- \end{theorem}
+\begin{frame}{Experimental design}
+ \begin{displaymath}
+ \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right),\quad S\subset\mathcal{A}
+ \end{displaymath}
\vspace{1cm}
- \alert{Consequence:} It suffices to find a monotonic selection rule such that
- the threshold payments are within the budget constraint.
+ \begin{itemize}
+ \item the non-strategic optimization problem is NP-hard
+ \vspace{0.3cm}
+ \pause
+ \item $V$ is submodular
+ \vspace{0.3cm}
+ \pause
+ \item previous results give a randomized budget feasible mechanism
+ \vspace{0.3cm}
+ \pause
+ \item deterministic mechanism?
+ \end{itemize}
\end{frame}
\begin{frame}{Main result}
\begin{theorem}
- There is a budget feasible, individually rational and truthful mechanism for
- the experimental design problem which runs in polynomial time. Its
+ There exists a budget feasible, individually rational and truthful mechanism for
+ experimental design which runs in polynomial time. Its
approximation ratio is:
\begin{displaymath}
\frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)}
@@ -257,80 +242,102 @@
\end{theorem}
\end{frame}
-
-\begin{frame}{Greedy revisited}
- \begin{block}{Greedy\only<2>{\alert{'}}($V$, $B$)}
- \begin{algorithmic}
- \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
- \State $S \gets \emptyset$
- \While{$c_i\leq \only<1>{B - \sum_{j\in S} c_j} \only<2->{\alert{\frac{B}{2}\frac{V(S\cup\{i\})-V(S)}{V(S\cup\{i\})}}}$}
- \State $S \gets S\cup\{i\}$
- \State $i \gets \argmax_{1\leq j\leq n}
- \frac{V(S\cup\{j\})-V(S)}{c_j}$
- \EndWhile
- \State \textbf{return} $S$
- \end{algorithmic}
+\begin{frame}{Sketch of proof}
+ \begin{block}{Mechanism (Chen et. al, 2011)}
+ \begin{itemize}
+ \item Find $i^* = \arg\max_i V(\{i\})$
+ \item Compute $S_G$ greedily
+ \item Return:
+ \begin{itemize}
+ \item $\{i^*\}$ if $V(\{i^*\}) \geq \only<1-2>{V(OPT_{-i^*})}\only<3>{\alert{V(OPT_{-i^*})}}\only<4->{\alert{L^*}}$
+ \item $S_G$ otherwise
+ \end{itemize}
+ \end{itemize}
\end{block}
- \vspace{1cm}
-
- \alert{Problem:} The threshold payments are not budget feasible.
-\end{frame}
+ \vspace{0.5cm}
+ \pause
-\begin{frame}{MaxGreedy revisited}
- \begin{block}{MaxGreedy}
- \begin{algorithmic}
- \State $i^* \gets \argmax_{1\leq j\leq n} V(j)$
- \State $S \gets$ Greedy\alert{'}($V$, $B$)
- \If{$V(i^*)\geq \only<1>{V(S)}\only<2,3>{\alert{OPT_{-i^*}}}\only<4>{\alert{OPT'_{i^*}}}$}
- \State \textbf{return} $\{i^*\}$
- \Else
- \State \textbf{return} $S$
- \EndIf
- \end{algorithmic}
- \end{block}
+ Valid mechanism, approximation ratio: 8.34
\vspace{0.5cm}
+ \pause
- \only<1>{\alert{Problem:} MaxGreedy is not monotonic}
+ \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute
- \only<2,3>{\alert{Solution 1:} use $OPT_{-i^*} = \max_{S, i^*\notin S}\{V(S) \mid \sum_{j\in S} c_j\}$. Gives a 8.34 approximation}
+ \vspace{0.5cm}
+ \pause
- \only<3>{\alert{Problem:} $OPT_{-i^*}$ cannot be computed in polynomial time}
+ \alert{Solution:} Replace $V(OPT_{-i^*})$ with $L^*$:
+ \pause
+ \begin{itemize}
+ \item computable in polynomial time
+ \pause
+ \item close to $V(OPT_{-i^*})$
+ \end{itemize}
+\end{frame}
- \only<4->{\alert{Solution 2:} use a concave relaxation:
+\begin{frame}{Sketch of proof (2)}
\begin{displaymath}
- OPT'_{i^*} = \max_{\lambda\in[0, 1]^n, \lambda_{i^*} = 0} L(\lambda)
- = \max_{\lambda\in[0, 1]^n, \lambda_{i^*} = 0}\log\det\big(I_d + \sum_{i=1}^n \lambda_i x_ix_i^T\big)
+ L^* = \arg\max_{\lambda\in [0,1]^n} \left\{\log\det\left(I_d + \sum_i \lambda_i x_i x_i^T\right)\mid \sum_{i=1}^n\lambda_i c_i\leq B\right\}
\end{displaymath}
- }
+ \vspace{1cm}
+ \begin{itemize}
+ \item polynomial time?\pause{} convex optimization problem
+ \pause
+ \vspace{0.5cm}
+ \item close to $V(OPT_{-i^*})$?\pause
+ \vspace{0.5cm}
+ \begin{block}{Technical lemma}
+ \begin{displaymath}
+ L^* \leq 2 V(OPT) + V(\{i^*\})
+ \end{displaymath}
+ \end{block}
+ \end{itemize}
\end{frame}
-\begin{frame}{Proof}
-\begin{itemize}
- \item Monotonicity: OK
- \pause
- \item Budget feasibility: OK
- \pause
- \item Approximation ratio: what do we lose by using a concave relaxation? Powerful
- method, \alert{pipage rounding} [Ageev, Sviridenko]
+\section{Generalization}
+
+\begin{frame}{Outline}
+ \tableofcontents[currentsection]
+\end{frame}
+
+\begin{frame}{Generalization}
\begin{itemize}
- \item let's introduce $F(\lambda) = \mathbb{E}\Big[\log\det(I_d+\sum_{i=1}^n \mu_ix_ix_i^T)\Big]$, $\mu_i\sim\mathcal{B}(\lambda_i)$
- \item $L(\lambda) \leq 2 F(\lambda)$ (technical lemma)
- \item $F$ is well-behaved: $\lambda$ can be round to a binary vector $\bar{\lambda}$ s.t $F(\lambda)\leq F(\bar{\lambda})$
- \item $OPT'_{-i^*}\leq 2 OPT_{-i^*} + V(i^*)$
- \item we can conclude by using the approximation ratio for $OPT_{-i^*}$
+ \item Generative model: $y_i = f(x_i) + \varepsilon_i,\;i\in\mathcal{A}$
+ \pause
+ \item prior knowledge of the experimenter: $f$ is a \alert{random variable}
+ \pause
+ \item \alert{uncertainty} of the experimenter: entropy $H(f)$
+ \pause
+ \item after observing $\{y_i,\; i\in S\}$, uncertainty: $H(f\mid S)$
\end{itemize}
-\end{itemize}
+
+ \pause
+ \vspace{0.5cm}
+
+ \begin{block}{Value function: entropy reduction}
+ \begin{displaymath}
+ V(S) = H(f) - H(f\mid Y_S),\quad S\subset\mathcal{A}
+ \end{displaymath}
+ \end{block}
+
+ \pause
+ \vspace{0.5cm}
+
+ $V$ is \alert{submodular} $\Rightarrow$ randomized budget feasible mechanism
\end{frame}
+
\begin{frame}{Conclusion}
\begin{itemize}
- \item Experimental design + Auction theory = powerful framework when working with user data
+ \item Experimental design + Auction theory = powerful framework
\vspace{1cm}
- \item Can we extend this to learning tasks beyond linear regression?
+ \pause
+ \item deterministic mechanism for the general case? other learning tasks?
\vspace{1cm}
- \item $\simeq \alert{13}$ approximation ratio. Lower bound: \alert{$2$}
+ \pause
+ \item approximation ratio $\simeq \alert{13}$. Lower bound: \alert{$2$}
\end{itemize}
\end{frame}
\end{document}
diff --git a/slides/user.svg b/slides/user.svg
new file mode 100644
index 0000000..76be844
--- /dev/null
+++ b/slides/user.svg
@@ -0,0 +1,76 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!-- Created with Inkscape (http://www.inkscape.org/) -->
+<svg xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:svg="http://www.w3.org/2000/svg" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" width="128" height="128" id="svg2" sodipodi:version="0.32" inkscape:version="0.44+devel" version="1.0" sodipodi:docbase="E:\Bilder\Eigene\scalable\kdm" sodipodi:docname="dagobert83_female_user_icon.svg" inkscape:output_extension="org.inkscape.output.svg.inkscape">
+ <defs id="defs4">
+ <linearGradient id="linearGradient17172">
+ <stop style="stop-color:#ffeed6;stop-opacity:1;" offset="0" id="stop17174"/>
+ <stop style="stop-color:#ffcd8b;stop-opacity:1;" offset="1" id="stop17176"/>
+ </linearGradient>
+ <linearGradient inkscape:collect="always" id="linearGradient14503">
+ <stop style="stop-color:white;stop-opacity:1;" offset="0" id="stop14505"/>
+ <stop style="stop-color:white;stop-opacity:0;" offset="1" id="stop14507"/>
+ </linearGradient>
+ <linearGradient id="linearGradient13597">
+ <stop style="stop-color:#ffeed6;stop-opacity:1;" offset="0" id="stop13599"/>
+ <stop style="stop-color:#ffcd8b;stop-opacity:1;" offset="1" id="stop13601"/>
+ </linearGradient>
+ <linearGradient id="linearGradient11787">
+ <stop style="stop-color:black;stop-opacity:1;" offset="0" id="stop11789"/>
+ <stop style="stop-color:#747474;stop-opacity:1;" offset="1" id="stop11791"/>
+ </linearGradient>
+ <linearGradient id="linearGradient10894">
+ <stop style="stop-color:#d49c56;stop-opacity:1;" offset="0" id="stop10896"/>
+ <stop style="stop-color:#d49c56;stop-opacity:0.25806451;" offset="1" id="stop10898"/>
+ </linearGradient>
+ <linearGradient id="linearGradient7301">
+ <stop style="stop-color:#d49c56;stop-opacity:1;" offset="0" id="stop7303"/>
+ <stop style="stop-color:#d49c56;stop-opacity:0;" offset="1" id="stop7305"/>
+ </linearGradient>
+ <linearGradient inkscape:collect="always" id="linearGradient7269">
+ <stop style="stop-color:#9f5f09;stop-opacity:1;" offset="0" id="stop7271"/>
+ <stop style="stop-color:#9f5f09;stop-opacity:0;" offset="1" id="stop7273"/>
+ </linearGradient>
+ <linearGradient id="linearGradient6376">
+ <stop style="stop-color:#da8410;stop-opacity:1;" offset="0" id="stop6378"/>
+ <stop style="stop-color:#c97402;stop-opacity:0;" offset="1" id="stop6380"/>
+ </linearGradient>
+ <linearGradient id="linearGradient5483">
+ <stop style="stop-color:#664314;stop-opacity:1;" offset="0" id="stop5485"/>
+ <stop style="stop-color:#a06b08;stop-opacity:1;" offset="1" id="stop5487"/>
+ </linearGradient>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient5483" id="linearGradient12700" gradientUnits="userSpaceOnUse" gradientTransform="translate(-199.9859,52.32021)" x1="-13.709487" y1="5.3772144" x2="27.385256" y2="-25.337072"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient6376" id="linearGradient12702" gradientUnits="userSpaceOnUse" gradientTransform="translate(-199.9859,52.32021)" x1="8.3035717" y1="-31.888393" x2="1.6168088" y2="-10.638393"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient11787" id="linearGradient12704" gradientUnits="userSpaceOnUse" x1="158.42857" y1="24.964285" x2="158.40045" y2="-11.642858" gradientTransform="translate(-331.4237,73.06709)"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient10894" id="linearGradient12706" gradientUnits="userSpaceOnUse" x1="161.20535" y1="-10.794643" x2="159.78572" y2="13.3125" gradientTransform="translate(-331.4237,73.06709)"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient7301" id="linearGradient12708" gradientUnits="userSpaceOnUse" x1="160.12111" y1="-8.0820084" x2="164.94254" y2="-67.703445" gradientTransform="translate(-331.4237,73.06709)"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient7269" id="linearGradient12710" gradientUnits="userSpaceOnUse" gradientTransform="translate(-199.9859,52.32021)" x1="40.537895" y1="7.1001654" x2="56.009064" y2="-1.6124004"/>
+ <radialGradient inkscape:collect="always" xlink:href="#linearGradient13597" id="radialGradient13603" cx="-165.2417" cy="33.695477" fx="-165.2417" fy="33.695477" r="21.607157" gradientTransform="matrix(0.7193,-1.71987e-2,3.513213e-2,1.469327,-47.5673,-19.60001)" gradientUnits="userSpaceOnUse"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient14503" id="linearGradient14509" x1="-247.27679" y1="16.79554" x2="-172.04314" y2="48.75983" gradientUnits="userSpaceOnUse"/>
+ <radialGradient inkscape:collect="always" xlink:href="#linearGradient17172" id="radialGradient17178" cx="-164.86122" cy="72.644211" fx="-164.86122" fy="72.644211" r="15.008935" gradientTransform="matrix(0.103799,8.14516e-2,-0.214019,0.272739,-132.2014,63.74477)" gradientUnits="userSpaceOnUse"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient5483" id="linearGradient17191" gradientUnits="userSpaceOnUse" gradientTransform="translate(-198.23195,52.32021)" x1="-13.709487" y1="5.3772144" x2="27.385256" y2="-25.337072"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient11787" id="linearGradient17195" gradientUnits="userSpaceOnUse" gradientTransform="translate(-331.4237,73.06709)" x1="158.42857" y1="24.964285" x2="158.40045" y2="-11.642858"/>
+ <radialGradient inkscape:collect="always" xlink:href="#linearGradient17172" id="radialGradient17197" gradientUnits="userSpaceOnUse" gradientTransform="matrix(0.103799,8.14516e-2,-0.214019,0.272739,-132.2014,63.74477)" cx="-164.86122" cy="72.644211" fx="-164.86122" fy="72.644211" r="15.008935"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient10894" id="linearGradient17199" gradientUnits="userSpaceOnUse" gradientTransform="translate(-331.4237,73.06709)" x1="161.20535" y1="-10.794643" x2="159.78572" y2="13.3125"/>
+ <radialGradient inkscape:collect="always" xlink:href="#linearGradient13597" id="radialGradient17201" gradientUnits="userSpaceOnUse" gradientTransform="matrix(0.7193,-1.71987e-2,3.513213e-2,1.469327,-44.059406,-19.60001)" cx="-165.2417" cy="33.695477" fx="-165.2417" fy="33.695477" r="21.607157"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient7301" id="linearGradient17203" gradientUnits="userSpaceOnUse" gradientTransform="translate(-327.9158,73.06709)" x1="160.12111" y1="-8.0820084" x2="164.94254" y2="-67.703445"/>
+ <linearGradient inkscape:collect="always" xlink:href="#linearGradient14503" id="linearGradient17207" gradientUnits="userSpaceOnUse" x1="-247.27679" y1="16.79554" x2="-172.04314" y2="48.75983" gradientTransform="translate(1.7539475,0)"/>
+ </defs>
+ <sodipodi:namedview id="base" pagecolor="#ffffff" bordercolor="#666666" borderopacity="1.0" inkscape:pageopacity="0.0" inkscape:pageshadow="2" inkscape:zoom="1" inkscape:cx="54.48184" inkscape:cy="66.68521" inkscape:document-units="px" inkscape:current-layer="g17180" width="128px" height="128px" inkscape:window-width="1280" inkscape:window-height="744" inkscape:window-x="22" inkscape:window-y="29"/>
+ <metadata id="metadata7">
+ <rdf:RDF>
+ <cc:Work rdf:about="">
+ <dc:format>image/svg+xml</dc:format>
+ <dc:type rdf:resource="http://purl.org/dc/dcmitype/StillImage"/>
+ </cc:Work>
+ </rdf:RDF>
+ </metadata>
+ <g inkscape:label="Ebene 1" inkscape:groupmode="layer" id="layer1">
+ <g id="g17180" transform="matrix(1.140285,0,0,1.140285,257.5128,9.583516)">
+ <path sodipodi:nodetypes="csss" id="path12688" d="M -147.33901,25.709573 C -145.73653,14.708702 -151.81538,-0.21445427 -168.70557,-0.53855397 C -190.62293,-0.95911824 -194.6984,14.831669 -193.58709,26.619974 C -192.2336,40.977284 -150.15483,45.039914 -147.33901,25.709573 z" style="fill:url(#linearGradient17191);fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"/>
+ <path sodipodi:nodetypes="cccccccc" id="path12692" d="M -222.67372,95.620662 C -220.22459,88.858002 -219.1402,76.304314 -210.70944,72.112771 L -171.60229,63.745666 L -130.75802,71.509435 C -123.57088,74.089619 -120.17357,88.073482 -116.73754,95.996842 C -118.97579,97.603602 -120.90488,99.983252 -123.56658,100.53138 L -216.24515,100.53138 C -219.25486,99.414592 -220.77927,97.406612 -222.67372,95.620662 z" style="fill:url(#linearGradient17195);fill-opacity:1;fill-rule:evenodd;stroke:black;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"/>
+ <path sodipodi:nodetypes="ccccc" id="path12694" d="M -183.12015,55.084952 C -182.91168,60.144436 -184.11091,63.06038 -186.48125,67.348861 C -177.2523,84.312006 -153.33119,75.567702 -153.95548,66.870666 L -156.60229,52.40638 L -183.12015,55.084952 z" style="fill:url(#radialGradient17197);fill-opacity:1;fill-rule:evenodd;stroke:url(#linearGradient17199);stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"/>
+ <path sodipodi:nodetypes="cczzccssc" id="path12696" d="M -149.37964,27.913445 C -149.89001,35.910486 -150.11384,45.661474 -151.90502,53.658515 C -151.90502,53.658515 -160.0493,61.061452 -164.59507,63.079381 C -169.14084,65.09731 -170.41315,64.823653 -174.6966,63.016246 C -178.98004,61.20884 -188.90187,54.163592 -188.90187,54.163592 C -193.16621,36.873591 -194.62507,18.751449 -175.64361,9.0993536 L -170.02361,15.773927 C -167.94421,18.243525 -158.81428,22.082907 -155.36536,18.790056 C -152.64326,16.191147 -150.98121,25.721279 -149.37964,27.913445 z" style="fill:url(#radialGradient17201);fill-opacity:1;fill-rule:evenodd;stroke:url(#linearGradient17203);stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"/>
+ <path sodipodi:nodetypes="ccccccc" id="path13605" d="M -189.88923,29.284383 C -190.59603,37.300253 -189.42477,44.957678 -187.64965,53.136344 C -182.75729,57.088986 -179.04885,62.303643 -168.83663,60.217075 C -165.33998,59.42021 -166.63651,57.748744 -164.62822,56.739254 C -176.70027,60.325884 -178.66956,57.789636 -184.89204,50.486422 L -188.99989,26.612934 L -189.88923,29.284383 z" style="fill:url(#linearGradient17207);fill-opacity:1;fill-rule:evenodd;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"/>
+ </g>
+ </g>
+</svg> \ No newline at end of file
generated by cgit v1.2.3-70-g09d2 (git 2.52.0) at 2025-12-21 15:33:13 +0000