管理三元式的新思路，涉及到查詢時(shí)似乎可以借用Social Network的思想
2024-07-21 02:17:03
供稿：網(wǎng)友
今天參加了一次討論會(huì)，一個(gè)主題是social network的search方法，另一個(gè)是關(guān)于本體中添加刪除三元式時(shí)的一致性問題和環(huán)路解決方法。
我對(duì)這次討論會(huì)的內(nèi)容有一些想法，想法有幾個(gè)方面，但我發(fā)現(xiàn)它們是有聯(lián)系的
首先是關(guān)于推理的問題。在討論會(huì)上提到sesame在加入一個(gè)三元式的時(shí)候選取一些規(guī)則盡可能作一些相對(duì)有價(jià)值的推理，我想能不能反其道而行之：使得整個(gè)模型中的三元式的數(shù)量盡可能少，也就是盡力去除可以被其他現(xiàn)有三元式推理出來的三元式，使得整個(gè)模型最小化。也就是說，在每次添加新的三元式的時(shí)候，要做的不是推理出更多的三元式，而是看看有沒有三元式可以刪除，并盡可能這樣做。一個(gè)例子：如果已經(jīng)有a subclass b，a subclass c，那么新加入b subclass c時(shí)就可以去除a subclass c，因?yàn)樗梢杂闪韮蓚€(gè)三元式推理得到。這樣想的直接考慮是在應(yīng)用中刪除三元式時(shí)不存在一致性等種種問題，可以直接刪除；相應(yīng)的增加三元式時(shí)時(shí)間代價(jià)會(huì)大一些，但是空間代價(jià)小了。
然而問題就是表面上看直接信息量少了很多，可能應(yīng)用于查詢時(shí)的時(shí)間代價(jià)會(huì)很大，在查詢時(shí)可能要做很多推理。但我覺得也許這是可以解決的，這是我的第二個(gè)想法，關(guān)于social network?？刹豢梢詫⑺械谋倔w中的所有的實(shí)體看成一個(gè)個(gè)結(jié)點(diǎn)，它們也許組成了一個(gè)social network。這個(gè)需要進(jìn)一步論證是否符合social network的定義和相關(guān)概念。我先假定是符合的。考慮一個(gè)實(shí)際的查詢，比如可能需要知道兩個(gè)給定結(jié)點(diǎn)（實(shí)體）之間的關(guān)系（路徑），不妨就采用窮舉法，假定兩個(gè)結(jié)點(diǎn)之間最短可以通過k個(gè)關(guān)系聯(lián)結(jié)，假定每個(gè)結(jié)點(diǎn)的度數(shù)是a，那么窮舉的推理相當(dāng)于a^k數(shù)量級(jí)，這個(gè)數(shù)量級(jí)理論上是不可接受的，但是實(shí)際上可能是可以接受的，原因如下：首先兩邊同時(shí)進(jìn)行，也許指數(shù)可以減半，僅需要a^(k/2)就可以解決；第二，因?yàn)閟ocial network有小世界的性質(zhì)，那么平均兩個(gè)結(jié)點(diǎn)可以通過大約6個(gè)關(guān)系就能連接，這樣k通常是小于6的，這樣開銷大約是a^3以內(nèi)（統(tǒng)計(jì)意義上的）；另外，social network中，每個(gè)結(jié)點(diǎn)的度數(shù)是極其有限的，僅和有限的結(jié)點(diǎn)關(guān)聯(lián)，典型的值比如100（我隨意估計(jì)的），這樣整個(gè)推理次數(shù)大約是10^6（請(qǐng)注意這個(gè)數(shù)字已經(jīng)不是數(shù)量級(jí)，而是實(shí)際的次數(shù)），這個(gè)值可能仍然不能接受，但我認(rèn)為是可以繼續(xù)降低的，原因如下：
可以考慮social network中的社區(qū)的概念，每個(gè)結(jié)點(diǎn)更多的是和有限的結(jié)點(diǎn)關(guān)聯(lián)，它們組成了社區(qū)，社區(qū)內(nèi)連接比較密集，我的理解就是：在一個(gè)社區(qū)內(nèi)部，彼此之間路徑應(yīng)當(dāng)很短（否則就不叫社區(qū)了），比如大約1-2步就可以到達(dá)對(duì)方；社區(qū)間的聯(lián)系是相對(duì)比較稀疏的，那么可不可能去管理社區(qū)間的關(guān)系（通過某種方式記錄），也就是將關(guān)注的焦點(diǎn)抽象一下，在查詢時(shí)先關(guān)注社區(qū)級(jí)別的關(guān)系：如果兩個(gè)結(jié)點(diǎn)在一個(gè)社區(qū)中，顯然查詢是很快的；如果不在一個(gè)社區(qū)中，那么可以很容易找到社區(qū)間的關(guān)系，因?yàn)樯鐓^(qū)間的關(guān)系是很稀疏的，記錄并提供合理和有效的索引也許是有可能的，這樣建立社區(qū)間的聯(lián)系以后再考慮社區(qū)內(nèi)的聯(lián)系，最終得到兩個(gè)結(jié)點(diǎn)的關(guān)系，其實(shí)與討論會(huì)上的所謂social netword的組織結(jié)構(gòu)的search方式有類似。
沒有考慮太仔細(xì)，我這方面基本功還很薄
