Tackling Winograd Schemas
by Formalizing Relevance Theory in Knowledge Graphs

Conference: International Conference on Principles of Knowledge Representation and Reasoning 2014

Author: Peter Schüller, Marmara University, ─░stanbul, Turkey

This work has been supported by Marmara University, Scientific Research Research Projects Committee (BAPKO Project No. FEN-D-120514-0177, 2014).

Contents

Publication

The paper can be downloaded here.

Software

Knowledge graphs of the four Winograd Schemas in our tests are encoded in the following files.

Background knowledge graphs and graph-based reasoning as described in the submission is implemented in the following files.

How to Execute Benchmarks

The benchmarks were performed using clingo-4.2.1. Note that previous clingo versions do not work due to a bug that was fixed in version 4.2.1.

Experiments were performed using the following commandline, where <input> is one of the input graph files, <schema> is either 1 or 2 (selecting the first or second variant of the schema).

The relevance fitness function is defined by <frel> and composed from the following components where C_* are constants as described in the submission.

$ echo "schema<schema>. mix. #maximize { <frel> }." |
   clingo --configuration=trendy <input>
     graphprocessor.gringo mixer.gringo costfunctionhelpers.gringo min_diameter.gringo
     background.graphs background.ontology background.gringo - --project 0

The result contains answer sets and graphviz-compatible output for visualization.

Visualization of Knowledge Graphs of Winograd Schemas in the KR 2014 Paper

Knowledge Graph of (5) plus activated Background Knowledge Graphs
(5)
Knowledge Graph of (6) plus activated Background Knowledge Graphs
(6)
Knowledge Graph of (7) plus activated Background Knowledge Graphs
(7)
Knowledge Graph of (8) plus activated Background Knowledge Graphs
(8)
Knowledge Graph of (9) plus activated Background Knowledge Graphs
(9)
Knowledge Graph of (10) plus activated Background Knowledge Graphs
(10)
Knowledge Graph of (11) plus activated Background Knowledge Graphs
(11)
Knowledge Graph of (12) plus activated Background Knowledge Graphs
(12)

Benchmark Results: Accumulated Over Configurations

(Sorted by correctness percentage, descending, and then by number of result graphs, ascending.)

C_com_in(C_bg,C_com_bg,C_dis_bg)C_omC_radcorrectresultscorrecttime to optimumtime to enumerate
##%sec# timeoutssec# timeouts
3(0,1,-2)0-51010100.073105870
3(0,1,-2)0-101010100.064504210
3(0,1,-2)-10-51010100.059805200
3(0,1,-2)-10-101010100.070804680
3(0,0,-1)0-51010100.049004640
3(0,0,-1)-10-51010100.068705330
1(0,0,-1)-10-51010100.070506100
3(0,0,-1)-10-101010100.058503750
2(-1,0,0)0-51010100.026902970
3(-1,0,0)0-51010100.036402370
3(0,1,-1)0-51010100.081509500
3(0,0,-1)-30-51111100.059907060
2(0,1,-2)-30-101111100.038703410
2(-1,0,0)-10-51111100.022602770
3(0,1,-2)-30-51111100.052004610
3(0,1,-2)-20-101111100.065803460
1(0,0,-1)-30-51111100.067105260
3(-1,0,0)-10-101111100.022902260
3(-1,0,0)-10-51111100.027003310
2(-1,0,0)-30-51111100.019701890
3(0,0,-1)-30-101111100.036403110
3(0,1,-1)-30-51111100.078206190
1(-1,0,0)-10-51111100.021901990
3(0,1,-2)-30-101111100.035203680
2(0,0,-1)-30-51111100.061205710
3(0,1,-1)-20-51111100.078607680
2(0,0,-1)-20-51111100.063908510
2(0,1,-2)-30-51111100.060504960
3(-1,0,0)-20-101111100.020201850
3(0,0,-1)-20-51111100.063105020
3(0,0,-1)-20-101111100.046504560
1(-1,0,0)-30-51111100.016301500
2(-1,0,0)-20-51111100.023601650
3(0,1,-2)-20-51111100.046505730
2(0,1,-2)-20-101111100.042602770
2(0,1,-2)-20-51111100.047604740
1(0,0,-1)-20-51111100.087304890
1(-1,0,0)-20-51111100.013801390
3(-1,0,0)-30-51111100.019801870
3(-1,0,0)-30-101111100.018801650
3(-1,0,0)-20-51111100.025402590
1(0,0,-1)005959100.042103930
1(0,1,-2)006767100.042605200
2(0,1,-2)008989100.020603660
1(0,1,-2)-1008989100.024202310
2(0,1,-2)-1008989100.020002470
0(0,0,-1)-1008989100.0500360
3(-1,0,0)008989100.010401020
3(0,1,-2)-1008989100.019302600
1(0,0,-1)-1008989100.039004700
3(0,0,-1)008989100.019601330
2(-1,0,0)008989100.08501230
3(0,1,-2)008989100.022602550
2(0,0,-1)-1008989100.031102310
2(0,0,-1)009191100.033902270
1(-1,0,0)009191100.013201800
1(0,1,-1)-300122122100.028103620
2(0,1,-1)-200122122100.024203950
2(-1,0,0)-300122122100.0990760
3(0,1,-1)-300122122100.018704230
1(-1,0,0)-100122122100.010101000
1(0,1,-2)-200122122100.014302920
3(0,0,-1)-300122122100.015002330
0(-1,0,0)-300122122100.0370380
2(0,0,-1)-300122122100.032101760
3(0,1,-2)-300122122100.015202180
3(-1,0,0)-100122122100.011501020
1(0,1,-1)-100122122100.027107740
3(0,1,-1)-200122122100.025203760
2(-1,0,0)-100122122100.09201210
0(-1,0,0)-200122122100.0400330
2(0,1,-1)-100122122100.029804960
3(0,0,-1)-200122122100.024701220
0(0,0,-1)-300122122100.0470350
2(0,1,-1)-300122122100.023404880
2(0,1,-2)-200122122100.018801970
1(-1,0,0)-300122122100.0870980
1(0,0,-1)-200122122100.023302880
2(0,1,-2)-30012112299.222101770
3(0,0,-1)-10012112299.220401810
3(0,1,-1)-10012112299.225204120
2(0,0,0)-10015816098.8710410
0(0,0,-1)-20012012298.4460330
0(-1,0,0)-10011512294.3340350
3(0,1,-1)0011212291.837005660
2(0,0,-1)-20011212291.829402170
3(0,1,-1)-30-10111291.761306750
2(0,0,-1)-30-10111291.744002780
2(-1,0,0)-10-10111291.722801770
2(0,0,-1)-20-10111291.758903720
3(-1,0,0)-20-15111291.719201750
3(-1,0,0)-30-15111291.716901460
1(0,1,-1)-20011112291.037003970
3(0,1,-2)-20-15101190.947203800
1(0,0,-1)-30-15101190.944601790
1(0,0,-1)-30-10101190.950002940
2(0,1,-1)-20-15101190.934903880
1(-1,0,0)-20-15101190.91440990
1(-1,0,0)-20-10101190.99901290
2(-1,0,0)-30-15101190.914401200
2(-1,0,0)-30-10101190.919801350
3(0,0,-1)-30-15101190.949901840
2(0,1,-2)-10-10101190.970403460
3(0,1,-1)-30-15101190.956404240
1(-1,0,0)-30-10101190.916101010
2(0,1,-1)-10-15101190.965603410
2(0,1,-1)-10-10101190.995507060
3(0,1,-2)-30-15101190.945102270
2(0,1,-1)-20-10101190.951503480
3(-1,0,0)-10-15101190.924101840
2(0,0,-1)-30-15101190.934303960
3(0,1,-1)-20-15101190.979003930
2(0,0,-1)-20-15101190.943904310
3(0,0,-1)0-10101190.940702920
2(0,1,-2)-30-15101190.940702090
3(0,0,-1)-20-15101190.948802320
2(-1,0,0)-20-10101190.919001810
2(-1,0,0)-20-15101190.913801140
2(0,1,-1)-30-15101190.945003510
2(0,1,-1)-30-10101190.972105820
1(-1,0,0)-30-15101190.9830860
3(0,1,-1)-10-15101190.945804230
1(0,0,-1)-20-10101190.936202260
1(0,0,-1)-20-15101190.942802070
1(-1,0,0)-10-1091090.015601520
3(-1,0,0)0-1091090.028002160
2(-1,0,0)-10-1591090.016101200
2(0,1,-2)-20-1591090.048403160
3(0,1,-2)-20010812288.518602220
1(0,1,-2)-30010712287.715101880
3(-1,0,0)-30010712287.7890910
3(-1,0,0)-20010612286.91030860
2(-1,0,0)-20010612286.9960970
1(-1,0,0)-20010612286.9860800
2(0,0,-1)0-10101283.339404120
1(-1,0,0)0-5141782.419403090
3(-1,0,0)0-1591181.825801530
3(0,1,-1)0-1091181.855407020
2(0,0,-1)-10-1091181.839704500
2(0,0,-1)0-1581080.038802010
2(0,1,-2)0-1581080.041205200
2(0,1,-2)-10-1581080.043203490
1(-1,0,0)-10-1581080.012501030
3(0,1,-1)0-1581080.064307910
3(0,1,-2)-10-1581080.033102700
3(0,0,-1)-10-1581080.034903750
1(0,0,-1)-10-1581080.039702110
1(0,0,-1)-10-1081080.051902230
2(0,1,-1)0-1081080.076007780
2(0,1,-1)0-1581080.051906610
3(0,0,-1)0-1581080.039301980
2(-1,0,0)0-1081080.030901740
2(-1,0,0)0-1581080.025801900
3(0,1,-2)0-1581080.052404990
2(0,0,-1)-10-1581080.055202870
1(0,1,-2)-20-5162080.060305010
1(0,0,-1)-3009712279.526203130
0(0,1,-2)-3009812479.0560390
3(0,0,0)-30-5597578.716001380
1(0,0,-1)0-5101376.951504600
0(0,0,-1)-20-15162176.2680320
2(0,0,0)0-5567475.710901130
1(0,1,-1)-30-10152075.044004650
1(0,1,-1)-30-15152075.037402300
1(0,1,-2)-20-10152075.030603070
0(-1,0,0)-30-10152075.0460320
0(-1,0,0)-30-15152075.0400300
0(-1,0,0)-30-5152075.0520340
1(0,1,-1)-20-15152075.040903310
1(0,1,-1)-20-10152075.067105730
0(0,0,-1)-20-10152075.0580350
0(0,0,-1)-20-5152075.0730310
1(0,1,-1)-10-15152075.058804020
0(-1,0,0)-20-5152075.0460300
0(-1,0,0)-20-15152075.0420290
0(-1,0,0)-20-10152075.0440300
0(-1,0,0)-10-5152075.0500330
0(0,0,-1)-30-5152075.0610290
0(0,0,-1)-30-15152075.0590290
0(0,0,-1)-30-10152075.0630320
1(0,1,-2)-30-15152075.030802280
1(0,1,-2)-30-10152075.059403660
3(0,0,0)-10011916074.4830470
3(0,0,0)-20-5557573.320101660
1(0,1,-2)-20-15131872.234703080
0(0,1,-2)-2008912471.8480450
0(0,0,0)-30-1012617870.8430280
2(0,0,0)-30-5537570.714501530
2(0,0,0)0011016068.8680510
3(0,0,0)-20011016068.8720470
1(0,0,0)0011016068.8650480
3(0,0,0)0011016068.8650490
0(0,1,-2)-30-56966.7790480
0(0,1,-2)-20-56966.7680640
1(-1,0,0)0-10121866.719802070
2(0,0,0)-20-5497565.317001200
0(0,1,-2)-10-571163.6610580
0(0,0,0)-10-159815463.6430280
1(0,1,-1)0-15121963.254805740
1(0,1,-1)0-10121963.266006520
1(0,1,-2)-10-15121963.241704070
1(0,1,-2)-10-10121963.246003880
0(0,0,-1)-10-15121963.2590350
0(0,0,-1)-10-10121963.2610330
0(0,0,-1)-10-5121963.2590390
0(-1,0,0)-10-10121963.2440350
0(-1,0,0)-10-15121963.2460320
2(0,0,0)-10-5477562.718001420
0(0,1,-2)-30-155862.5560500
0(0,1,-2)-30-105862.5750540
0(0,1,-2)-20-105862.5730520
0(0,1,-2)00609761.9460480
1(0,0,-1)0-1081361.538302890
1(0,0,0)-1009816061.3620440
3(0,0,0)-3009816061.3620470
2(0,0,0)-2009816061.3670410
1(-1,0,0)0-15111861.112001140
0(0,1,-2)-20-1561060.0650590
3(0,0,0)0-5457560.013101320
0(-1,0,0)00528958.4370300
0(0,0,-1)00528958.4380320
0(0,2,-1)-20011620058.023205550
3(0,0,0)-10-5437557.323301750
0(0,1,-1)-10-1581457.1670660
1(0,1,-2)0-10173056.748403320
0(0,0,-1)0-55955.6470330
0(0,1,-2)0-55955.6630730
0(0,1,-2)-10-155955.6720510
0(0,1,-2)-10-105955.6610580
0(0,1,-2)-1005910755.1500390
1(0,0,-1)0-1571353.848702200
2(0,0,0)-3008616053.8770470
0(0,2,-1)-30010720053.533602420
0(-1,0,0)0-1581553.3430340
0(-1,0,0)0-1081553.3470330
0(0,1,-1)-30-581553.3620570
0(0,0,-1)0-1081553.3480330
0(0,0,-1)0-1581553.3480360
0(0,1,-1)-20-581553.3880710
0(0,1,-1)-10-581553.3810630
1(0,0,0)-3008516053.1630510
0(-1,0,0)0-591752.9390290
0(0,1,-2)0-10101952.6800650
0(0,1,-2)0-15101952.6800700
0(0,2,-1)0-15142751.984704980
0(0,2,-1)-10010220051.028803510
0(0,1,-1)-30-1061250.0780600
0(0,1,-1)-30-1561250.0810530
0(0,1,-1)-20-1561250.0610620
0(0,1,-1)-20-1061250.0670610
0(0,1,-1)-10-1061250.0770680
0(0,2,-1)-10-15132650.038003960
0(0,2,-1)-10-10132650.039705350
0(0,2,-1)-20-10132650.056903220
0(0,2,-1)-20-15132650.037803430
0(0,2,-1)0-10132650.051805150
0(0,2,-1)-30-15132650.036903430
0(0,2,-1)-30-10132650.056902690
0(0,2,-1)0010020050.039306340
0(0,2,-1)-20-5153148.466006710
2(0,0,0)-10-10275747.412101330
2(0,0,0)-10-15275747.413601000
1(0,0,0)-10-15275747.410001000
1(0,0,0)-10-10275747.413801100
1(0,0,0)-10-5275747.415101710
2(0,0,0)-30-15275747.41650950
3(0,0,0)-10-15275747.416801320
3(0,0,0)-10-10275747.418101480
1(0,0,0)-30-10275747.4970860
3(0,0,0)-20-10275747.416801610
3(0,0,0)-20-15275747.418301260
1(0,0,0)-20-10275747.41140750
1(0,0,0)-20-15275747.4900740
1(0,0,0)-20-5275747.41040940
2(0,0,0)-30-10275747.415101010
3(0,0,0)-30-15275747.417301210
3(0,0,0)-30-10275747.415401110
1(0,0,0)-30-5275747.41080950
1(0,0,0)-30-15275747.4710620
2(0,0,0)-20-15275747.41050870
2(0,0,0)-20-10275747.415601340
1(0,1,-2)0-15153246.942003370
3(0,0,0)0-10265646.418501180
0(0,0,0)-10-108217846.1350290
0(0,0,0)009220046.0-0200
0(0,1,-1)007316045.6590670
2(0,0,0)0-15255644.61110940
2(0,0,0)0-10255644.612201250
1(0,0,0)0-5255644.611001140
1(0,0,0)0-10255644.61040870
1(0,0,0)0-15255644.6880780
3(0,0,0)0-15255644.611101070
0(0,0,0)-3008820044.0340300
0(0,0,0)-1008820044.0350320
0(0,0,0)-2008820044.0290280
0(0,0,0)-20-157717843.3410300
0(0,0,0)-20-57717843.3420290
0(0,0,0)-10-57417841.6350260
0(0,0,0)-30-157417841.6400280
0(0,0,0)-20-107417841.6360300
0(0,1,-1)-3006216038.8510510
0(0,1,-1)-2006016037.5540600
0(0,1,-1)0-541136.4730680
0(0,1,-1)0-1541136.4880770
0(0,1,-1)0-1041136.4780760
1(0,0,0)-2005816036.3630400
0(0,0,0)0-155015033.3410320
0(0,0,0)0-55015033.3370300
0(0,0,0)0-105015033.3360300
0(0,1,-1)-1004616028.8450550
0(0,0,0)-30-52417813.5370280
Parameter Settings with at least one Timeout
2(0,1,-2)-10-588100.084407041
2(0,0,-1)-10-51010100.096118170
3(0,1,-1)-10-51111100.080809611
1(0,1,-1)006565100.051108731
2(0,2,-1)007575100.099529732
2(0,2,-1)-3007878100.097529572
2(0,1,-1)008787100.035607681
2(0,2,-1)-2009999100.097126701
3(0,2,-1)-3009910099.096426081
3(0,2,-1)00747598.799429942
3(0,2,-1)-100737498.696229792
3(0,2,-1)-20-10384095.0110628671
2(0,1,-1)-30-5161794.174915690
3(0,1,-1)-20-10111291.776516610
3(0,1,-1)-10-10111291.749907011
2(0,1,-2)0-10101190.962506991
3(0,2,-1)0-15101190.91106211162
3(0,2,-1)0-5293290.6115428821
3(0,2,-1)-200677589.399329672
2(0,2,-1)-10010812387.897127881
2(0,2,-1)-30-107887.51118210602
3(0,2,-1)-10-15283287.5106427071
3(0,2,-1)-20-156785.71082210182
2(0,2,-1)-20-10121485.71058210932
1(0,1,-1)-10-5323884.292714540
1(0,1,-2)-30-5162080.067013690
2(0,2,-1)-10-5263378.81182210171
2(0,2,-1)0-107977.81163210862
3(0,2,-1)-30-157977.81078210332
2(0,1,-2)0-5212777.875516250
1(0,1,-1)-30-5152075.090518560
1(0,1,-1)-20-5152075.087216080
1(0,1,-1)-10-10152075.099214780
3(0,2,-1)-30-5111573.31077210392
2(0,0,-1)0-5243372.790114650
2(0,1,-1)-10-5294072.599125210
1(0,2,-1)-30-5273871.1113527891
2(0,2,-1)-20-15314568.9105229431
1(0,1,-2)0-5192867.973816500
2(0,2,-1)0-15213363.6113728711
1(0,1,-2)-10-5213363.672013990
1(0,1,-1)0-5121963.298618211
1(0,2,-1)-10-581361.51139210492
2(0,2,-1)-10-10345858.61168210400
2(0,2,-1)0-5183354.51214210231
2(0,1,-1)0-5173253.198727301
1(0,2,-1)-2006111652.697529462
0(0,2,-1)0-5132552.083107941
0(0,2,-1)-30-5132552.075506681
1(0,2,-1)-3006813550.499127931
2(0,2,-1)-10-15163348.5108428681
0(0,2,-1)-10-5153148.481416560
3(0,2,-1)-20-5275747.4112027880
3(0,2,-1)-10-5235046.01083210521
1(0,2,-1)-1006213545.996427951
3(0,2,-1)-10-10204445.51099210481
1(0,2,-1)-20-5255843.1114428671
1(0,2,-1)-20-15153542.9104329371
2(0,1,-1)-20-5143441.2101016201
1(0,2,-1)004511140.597829952
1(0,2,-1)-20-10143540.0106629471
2(0,2,-1)-30-15225837.9101427680
1(0,2,-1)0-15133537.1104728121
1(0,2,-1)-10-15133537.1103329381
1(0,2,-1)-30-15164634.8101725931
3(0,2,-1)0-10113234.41139211781
1(0,2,-1)0-5133834.2114028031
1(0,2,-1)0-10206033.3110926430
1(0,2,-1)-30-10113531.4103329471
2(0,2,-1)-30-5103330.3110428401
2(0,2,-1)-20-5103330.3111527941
3(0,2,-1)-30-10103627.8111727741
1(0,2,-1)-10-10146023.3104024350

Impressum: Medieninhaber Peter Schüller, Fasangartengasse 55, 1130 Wien, Austria. Email: schueller.p@gmail.com. Telefon: +4369910963525 +905533390009