نمایش مبدأ برای تعبیه گراف دانش


[[File:KnowledgeGraphEmbedding.png|پیوند=https://en.wikipedia.org/wiki/File:KnowledgeGraphEmbedding.png|بندانگشتی|تاف عبیه‌سازی یک گراف دانش. نمایش برداری موجودیت‌ها و روابط می‌تواند برای مقاصد مختلف یادگیری ماشین استفاده شود.]]
در یادگیری بازنمایی، تعبیه گراف دانش (معادل Knowledge Graph Embedding یا KGE)، که از آن به عنوان یادگیری بازنمایی دانش (KRL) و یا یادگیری چند رابطه‌ای هم یاد می‌شود،<ref name=":0">{{Cite journal|last1=Ji|first1=Shaoxiong|last2=Pan|first2=Shirui|last3=Cambria|first3=Erik|last4=Marttinen|first4=Pekka|last5=Yu|first5=Philip S.|date=2021|title=A Survey on Knowledge Graphs: Representation, Acquisition, and Applications|url=https://ieeexplore.ieee.org/document/9416312|journal=IEEE Transactions on Neural Networks and Learning Systems|volume=PP|pages=1–21|arxiv=2002.00388|doi=10.1109/TNNLS.2021.3070843|issn=2162-237X|pmid=33900922|s2cid=211010433}}</ref> یک کار یادگیری ماشینی برای یادگیری یک نمایش کم بعدی از موجودیت ها و روابط یک نمودار دانش است. با حفظ معنای معنایی آنها<ref name=":02">{{Cite journal|last1=Ji|first1=Shaoxiong|last2=Pan|first2=Shirui|last3=Cambria|first3=Erik|last4=Marttinen|first4=Pekka|last5=Yu|first5=Philip S.|date=2021|title=A Survey on Knowledge Graphs: Representation, Acquisition, and Applications|url=https://ieeexplore.ieee.org/document/9416312|journal=IEEE Transactions on Neural Networks and Learning Systems|volume=PP|pages=1–21|arxiv=2002.00388|doi=10.1109/TNNLS.2021.3070843|issn=2162-237X|pmid=33900922|s2cid=211010433}}</ref><ref>{{Cite journal|last1=Mohamed|first1=Sameh K|last2=Nováček|first2=Vít|last3=Nounu|first3=Aayah|date=2019-08-01|editor-last=Cowen|editor-first=Lenore|title=Discovering Protein Drug Targets Using Knowledge Graph Embeddings|url=https://academic.oup.com/bioinformatics/advance-article/doi/10.1093/bioinformatics/btz600/5542390|journal=Bioinformatics|language=en|volume=36|issue=2|pages=603–610|doi=10.1093/bioinformatics/btz600|issn=1367-4803|pmid=31368482|hdl-access=free|hdl=10379/15375}}</ref><ref name=":2">{{cite arXiv|last1=Lin|first1=Yankai|last2=Han|first2=Xu|last3=Xie|first3=Ruobing|last4=Liu|first4=Zhiyuan|last5=Sun|first5=Maosong|date=2018-12-28|title=Knowledge Representation Learning: A Quantitative Review|class=cs.CL|eprint=1812.10901}}</ref>. نمودارهای دانش (KGs) با استفاده از نمایش تعبیه شده آنها می‌توانند برای کاربردهای مختلفی مانند پیش‌بینی پیوند، طبقه‌بندی سه‌گانه، شناسایی موجودیت، خوشه بندی و استخراج رابطه استفاده شوند.

== تعریف ==
یک گراف دانش، با <math>\mathcal{G} = \{E, R, F\}</math> نمایش داده می‌شود و مجموعه‌ای‌ از موجودیت‌ها (entity) و روابط (relations) و حقایق (fact) است. یک حقیقت، سه‌گانه‌ای به صورت <math>(h, r, t) \in F</math> است که در آن، <math>r \in R</math> ارتباطی میان ابتدا یا سر (<math>h \in E</math>) و انتها یا دم (<math>t \in E</math>) برقرار می‌کند. طریقه دیگر نشان دادن حقیقت، به صورت <math><head, relation, tail></math> است که به این نمادگذاری، چارچوب توصیف منابع (RDF) هم می‌گویند. نمودار دانش، نشان‌دهنده دانش مربوط به یک حوزه خاص است. با استفاده از این نمایش ساختاریافته، می‌توان پس از چند مرحله اصلاح، بخشی از دانش جدید را از آن استنتاج کرد. با این حال، امروزه، مردم برای استفاده از آنها در یک برنامه واقعی باید با پراکندگی داده ها و ناکارآمدی محاسباتی دست و پنجه نرم کنند. تعبیه یک نمودار دانش، هر موجودیت و رابطه یک نمودار دانش (<math>\mathcal{G}</math>) را به بردار با یک بعد معین (<math>d</math> یا بعد تعبیه)، ترجمه می‌کند. مجموعه بردارهای جاسازی شده برای همه موجودیت ها و روابط در نمودار دانش، نمایش متراکم و کارآمدتری از دامنه است که می تواند به راحتی برای بسیاری از وظایف مختلف استفاده شود.

تعبیه گراف دانش با چهار جنبه مختلف مشخص می‌شود:

# فضای بازنمایی: فضایی با تعداد بعد کم که موجودیت ها و روابط در آن نمایش داده می‌شوند.
# تابع امتیاز دهی: معیار خوب بودن برای نمایش سه گانه تعبیه شده.
# مدل‌های رمزگذاری: روشی که در آن بازنمایی تعبیه‌شده موجودیت‌ها و روابط با یکدیگر تعامل دارند.
# اطلاعات اضافی: هر گونه اطلاعات اضافی که از نمودار دانش حاصل می‌شود و می‌تواند نمایش تعبیه شده را غنی کند. معمولاً برای هر اطلاعات اضافی، یک تابع امتیازدهی موقت در تابع امتیازدهی عمومی ادغام می‌شود.

=== '''فرایند تعبیه''' ===
همه مدل‌های مختلف جاسازی نمودار دانش تقریباً از یک روش برای یادگیری معنای معنایی حقایق پیروی می‌کنند. در ابتدا، برای یادگیری یک نمایش تعبیه شده از یک نمودار دانش، بردارهای تعبیه شده موجودیت ها و روابط به مقادیر تصادفی مقداردهی اولیه می‌شوند. سپس، با شروع از یک مجموعه آموزشی تا رسیدن به یک شرط توقف، الگوریتم به طور مداوم تعبیه‌ها را بهینه می‌کند. معمولاً شرط توقف با اضافه شدن بیش از حد روی مجموعه تمرینی داده می‌شود. برای هر تکرار، یک دسته از اندازه <math>b</math> از مجموعه آموزشی نمونه‌برداری می‌شود و برای هر سه‌گانه‌ای از دسته، یک واقعیت خراب تصادفی نمونه برداری می‌شود، (منظور از واقعیت خراب تصادفی، یعنی سه‌گانه‌ای که یک واقعیت درست و واقعی را در نمودار دانش نشان نمی‌دهد.) فساد سه‌گانه شامل جایگزینی سر یا دم (یا هر دو) سه گانه با موجودیت دیگری است که واقعیت را نادرست می کند. سه گانه اصلی و سه گانه خراب در دسته آموزشی اضافه می‌شوند و سپس جاسازی ها به روز می‌شوند و یک تابع امتیازدهی را بهینه می‌کنند. در پایان الگوریتم، تعبیه‌های آموخته شده باید معنای معنایی را از سه‌گانه استخراج کرده و حقایق واقعی را به درستی در نمودار دانش مشاهده نکرده باشند.

=== شبه کد ===
شبه‌ کد برای توصیف رفتار یک KGE به صورت زیر است:<ref name=":9">{{Cite journal|last1=Bordes|first1=Antoine|last2=Usunier|first2=Nicolas|last3=Garcia-Durán|first3=Alberto|last4=Weston|first4=Jason|last5=Yakhnenko|first5=Oksana|date=May 2013|title=Translating embeddings for modeling multi-relational data|url=https://dl.acm.org/doi/10.5555/2999792.2999923|journal=Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2|series=NIPS'13|location=Lake Tahoe, Nevada|publisher=Curran Associates Inc.|pages=2787–2795}}</ref><ref name=":3">{{Cite journal|last1=Dai|first1=Yuanfei|last2=Wang|first2=Shiping|last3=Xiong|first3=Neal N.|last4=Guo|first4=Wenzhong|date=May 2020|title=A Survey on Knowledge Graph Embedding: Approaches, Applications and Benchmarks|journal=Electronics|language=en|volume=9|issue=5|pages=750|doi=10.3390/electronics9050750|doi-access=free}}</ref><syntaxhighlight lang="cpp" line="1">
Algorithm Compute entity and relation embeddings
input: The training set S={(h,r,t)}, entity set E, relation set R, embedding dimension k
output: Entity and relation embeddings 
initialization: the entities e and relations r, embeddings (vectors) are randomly initialized 
while stop condition do 
    S_batch <- sample(S,b) // From the training set randomly sample a batch of size b 
    for each (h,r,t) in S_{batch} do 
        (h',r,t') <- sample(S') // sample a corrupted fact of triple 
        T_{batch} <- T_{batch} union {((h,r,t),(h',r,t'))}}
    end for 
     Update embeddings by minimizing the loss function 
 end while
</syntaxhighlight>

=== شاخصه‌های اجرا ===
این شاخص‌ها اغلب برای اندازه‌گیری کیفیت تعبیه یک مدل استفاده می‌شوند. سادگی شاخص ها آنها را برای ارزیابی عملکرد یک الگوریتم جاسازی حتی در مقیاس بزرگ بسیار مناسب می کند. با فرض داشتن <chem>Q</chem> به عنوان مجموعه‌ای از تمام پیش‌بینی‌های رتبه‌بندی شده یک مدل، می‌توان سه شاخص عملکرد مختلف را تعریف کرد:

==== Hits@K ====
Hits@K یا به طور خلاصه، H@K، یک شاخص عملکرد است که احتمال یافتن پیش‌بینی صحیح را در اولین K پیش‌بینی‌های برتر مدل اندازه‌گیری می‌کند. معمولاً از <math>k=10</math> استفاده می‌شود. Hits@K منعکس کننده دقت یک مدل تعبیه شده برای پیش بینی رابطه بین دو سه‌گانه به درستی است.

<math>= \frac{|\{q \in Q : q < k \}|}{|Q|} \in [0, 1]</math> Hits@K

مقادیر بالاتر، نشان‌دهنده نتایج پیش‌بینی بهتر است.<ref name=":31">{{Cite journal|last1=Chen|first1=Zhe|last2=Wang|first2=Yuehan|last3=Zhao|first3=Bin|last4=Cheng|first4=Jing|last5=Zhao|first5=Xin|last6=Duan|first6=Zongtao|date=2020|title=Knowledge Graph Completion: A Review|journal=IEEE Access|volume=8|pages=192435–192456|doi=10.1109/ACCESS.2020.3030076|issn=2169-3536|doi-access=free|s2cid=226230006}}</ref>

==== Mean rank (MR) ====
میانگین رتبه، میانگین رتبه‌بندی اقلام پیش‌بینی شده توسط مدل در بین تمامی آیتم‌های ممکن است.

<math>MR = \frac{1}{|Q|}\sum_{q \in Q}{q}</math>

مقادیر پایین‌تر، نشان‌دهنده مدل بهتر است.<ref name=":31" />

==== Mean reciprocal rank (MRR) ====
میانگین رتبه متقابل، تعداد سه گانه های پیش بینی شده درست را اندازه می‌گیرد. اگر اولین سه‌گانه پیش‌بینی شده درست باشد، 1 اضافه می‌شود. اگر دومی درست باشد، <math>\frac{1}{2}</math> اضافه می‌شود و به همین ترتیب تا انتها.

MRR معمولاً برای تعیین کمیت اثر الگوریتم های جستجو استفاده می شود.

<math>MRR = \frac{1}{|Q|}\sum_{q \in Q}{\frac{1}{q}}  \in [0, 1]</math>

مقادیر بالاتر، نشان‌دهنده مدل بهتر است.<ref name=":31" />

== کاربردها<ref name=":12">{{cite arXiv|last1=Cai|first1=Hongyun|last2=Zheng|first2=Vincent W.|last3=Chang|first3=Kevin Chen-Chuan|date=2018-02-02|title=A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications|class=cs.AI|eprint=1709.07604}}</ref> ==

=== وظایف یادگیری ماشین ===
تکمیل نمودار دانش (KGC) مجموعه‌ای از تکنیک‌ها برای استنتاج دانش از نمایش نمودار دانش تعبیه‌شده است. به طور خاص، این تکنیک یک استنتاج سه‌گانه موجودیت یا رابطه گمشده را تکمیل می‌کند. وظایف فرعی مربوطه، پیش‌بینی پیوند یا موجودیت (یعنی حدس زدن یک موجودیت از جاسازی موجودیت دیگر سه‌گانه و رابطه) و پیش‌بینی رابطه (یعنی پیش‌بینی معقول‌ترین رابطه‌ای که دو موجودیت را به هم متصل می‌کند) نامیده می‌شوند.

طبقه بندی سه‌گانه یک مسئله طبقه‌بندی دودویی است. با فرض داده شدن یک سه‌گانه، مدل آموزش دیده معقول بودن سه‌گانه را با استفاده از تعبیه برای تعیین درست یا نادرست بودن یک سه گانه ارزیابی می‌کند. تصمیم با تابع امتیاز مدل و یک آستانه معین گرفته می‌شود. خوشه‌بندی برنامه دیگری است که از نمایش تعبیه شده یک نمودار دانش پراکنده برای متراکم کردن نمایش موجودیت های معنایی مشابه در یک [[فضای دوبعدی|فضای دو بعدی]] استفاده می‌کند.

=== کاربردهای مخصوص دنیای واقعی ===
استفاده از جاسازی گراف دانش به طور فزاینده‌ای در بسیاری از کاربردها فراگیر شده است. در مورد سیستم‌های توصیه گر، استفاده از جاسازی نمودار دانش می‌تواند بر محدودیت‌های [[یادگیری تقویتی]] معمول غلبه کند. آموزش این نوع سیستم توصیه‌گر نیازمند حجم عظیمی از اطلاعات کاربران است. با این حال، تکنیک‌های نمودار دانش می‌توانند با استفاده از نموداری که قبلاً بر روی دانش قبلی از همبستگی آیتم ساخته شده است و استفاده از تعبیه برای استنباط از آن توصیه، این مسئله را برطرف کند. استفاده مجدد از دارو، استفاده از یک داروی قبلاً تأیید شده است، اما برای یک هدف درمانی متفاوت از آنچه در ابتدا برای آن طراحی شده بود. می توان از وظیفه پیش بینی پیوند برای استنباط جدید بین یک داروی موجود و یک بیماری با استفاده از یک نمودار دانش زیست پزشکی ساخته شده با استفاده از در دسترس بودن ادبیات عظیم و پایگاه های داده زیست پزشکی استفاده کرد. تعبیه نمودار دانش نیز می تواند در حوزه سیاست اجتماعی مورد استفاده قرار گیرد.

== مدل‌ها ==
با فرض داده‌ شدن مجموعه‌ای از سه‌گانه‌ها (یا حقایق) به صورت <math>\mathcal{F} = \{<head, relation, tail>\}</math>، نمودار تعبیه دانش برای هر موجودیت و رابطه حاضر در داده‌ها، یک نمایش برداری پیوسته می‌سازد، که همان مدل ماست. <math>(h, r, t)</math> متناظر با سه‌گانه‌ای با مشخصات <math>h,t \in {\rm I\!R}^{d}</math> و <math>r \in {\rm I\!R}^{k}</math> است که <math>d</math> بیانگر بعد تعبیه برای موجودیت‌ها و <math>k</math> برابر بعد تعبیه برای روابط است. مدل‌ها انواع مختلفی دارند که در ادامه به آنها می‌پردازیم.<ref name=":1">{{Cite journal|last1=Rossi|first1=Andrea|last2=Barbosa|first2=Denilson|last3=Firmani|first3=Donatella|last4=Matinata|first4=Antonio|last5=Merialdo|first5=Paolo|date=2020|title=Knowledge Graph Embedding for Link Prediction: A Comparative Analysis|url=https://dl.acm.org/doi/10.1145/3424672|journal=ACM Transactions on Knowledge Discovery from Data|language=en|volume=15|issue=2|pages=1–49|arxiv=2002.00819|doi=10.1145/3424672|issn=1556-4681|s2cid=211011226}}</ref>

=== مدل تجزیه تنسور ===
تجزیه تنسور خانواده‌ای از مدل‌های تعبیه گراف دانش است که از یک ماتریس چند بعدی برای نشان دادن یک نمودار دانش استفاده می‌کند، که به دلیل شکاف‌های نمودار دانش که یک دامنه خاص را به طور کامل توصیف می‌کند، تا حدی قابل شناخت است.

=== مدل‌های دو خطی ===
این خانواده از مدل‌ها از یک معادله خطی برای تعبیه ارتباط بین موجودیت‌ها از طریق یک رابطه استفاده می‌کنند. به طور خاص، نمایش تعبیه شده روابط، یک ماتریس دو بعدی است.

=== مدل‌های هندسی ===
فضای هندسی تعریف شده توسط این خانواده از مدل‌ها، این رابطه را به عنوان یک تبدیل هندسی بین ابتدا و انتهای یک واقعیت و حقیقت رمزگذاری می‌کند.

== مراجع ==
<references />
[[رده:یادگیری ماشین]]
[[رده:الگوریتم‌های گراف]]
[[رده:علم اطلاعات]]