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.

For example to configure the third line of Table 1 [3 (0,1,-2) -10 -5] you would create the following configuration file example-config.gringo: (percent signs are comments)
  schema1.
  mix.
  #maximize {
    % C_com_in = 3
    N : nodestats(N,orig,Coll,0) ;
    % C_bg = 0, C_com_bg = 1, C_dis_bg = -2
    1*Coll-2*Dist,N : nodestats(N,new,Coll,Dist) ;
    % C_om = -10
    0,G,A : activated_unused(G,A) ;
    % C_rad = -5
    -5*N : diameter(N)
}.

The program is then executed as follows, where you need to use the graphprocessor.gringo compatible with your clingo version and replace schoolbag.graph with the graph you want to use.
  $ clingo-4.2.1-bin --configuration=trendy schoolbag.graph example-config.gringo \
    graphprocessor.4.2.1.gringo mixer.gringo costfunctionhelpers.gringo min_diameter.gringo \
    background.graphs background.ontology --project 0

The output contains answer sets and graphviz-compatible output for visualization. At the moment there is no option to write the graphviz file to a separate file, you need to extract it with a script or manually from the output to render it with neato.

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