지역 의존 해시를 이해하려면 어떻게 해야 하나요?
LSH는 고차원적인 특성을 가진 유사한 아이템을 찾는 좋은 방법인 것 같습니다.
http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf,이라는 논문을 읽고 난 후에도 나는 아직도 그 공식들에 혼란스럽다.
이 쉬운 방법을 설명하는 블로그나 기사를 아는 사람이 있나요?
LSH에 관한 최고의 튜토리얼은 다음 책에 나와 있습니다.대규모 데이터 세트의 마이닝.3장 - 유사한 항목 찾기 http://infolab.stanford.edu/~Ullman/mmds/ch3a.pdf
또한 다음 슬라이드를 추천합니다.http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf. 이 슬라이드의 예는 코사인 유사성에 대한 해시를 이해하는 데 큰 도움이 됩니다.
Benjamin Van Durme & Ashwin Lall, ACL2010에서 슬라이드 2개를 빌려 LSH Families for Cosine Distance의 직관을 설명하겠습니다. 
- 그림에는 빨간색과 노란색으로 표시된 두 개의 원이 있으며, 두 개의 2차원 데이터 점을 나타냅니다.LSH를 사용하여 코사인 유사성을 찾고 있습니다.
- 회색 선은 균일하게 랜덤하게 선택된 평면입니다.
- 데이터 포인트가 회색 선 위에 있는지 아래에 있는지에 따라 이 관계를 0/1로 표시합니다.
- 왼쪽 상단 모서리에는 두 데이터 포인트의 시그니처를 각각 나타내는 흰색/검은색 정사각형 행이 있습니다.각 사각형은 비트 0(흰색) 또는 1(검은색)에 대응합니다.
- 따라서 평면 풀이 있으면 데이터 점을 평면에 대한 위치로 인코딩할 수 있습니다.풀에 평면이 많아지면 시그니처에 부호화된 각도의 차이가 실제 차이에 가깝다고 상상해 보십시오.두 점 사이에 있는 평면만 두 데이터에 서로 다른 비트 값을 제공하기 때문입니다.
- 이제 두 데이터 포인트의 시그니처를 살펴보겠습니다.예시와 같이 각 데이터를 나타내는 데 6비트(제곱)만 사용합니다.이것은 원래 데이터에 대한 LSH 해시입니다.
- 두 해시 값 사이의 해밍 거리는 1입니다.이는 시그니처가 1비트만 다르기 때문입니다.
- 서명 길이를 고려하여 그래프와 같이 각도의 유사도를 계산할 수 있습니다.
여기 코사인 유사성을 사용하는 파이썬 샘플 코드(50줄만)가 있습니다.https://gist.github.com/94a3d425009be0f94751
벡터 공간의 트윗은 고차원 데이터의 좋은 예가 될 수 있습니다.
비슷한 트윗을 찾으려면 지역감응형 해싱을 트윗에 적용하는 방법에 대한 블로그 게시물을 확인하십시오.
http://micvog.com/2013/09/08/storm-first-story-detection/
그리고 한 장의 사진은 천 개의 단어이기 때문에 아래 그림을 확인해 주세요.
http://micvog.files.wordpress.com/2013/08/lsh1.png
도움이 됐으면 좋겠다.@mvogiatzis
스탠포드 대학의 프레젠테이션이 이에 대한 설명입니다.그것은 나에게 큰 변화를 주었다.2부는 LSH에 관한 내용이지만 1부는 LSH에 대해서도 다루고 있습니다.
개요 그림(슬라이드에 더 자세히 나와 있습니다):
고차원 데이터의 근접 네이버 검색 - Part 1: http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf
고차원 데이터 근린검색 - Part 2: http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf
- LSH는 문서/이미지/개체 집합을 입력으로 사용하여 해시 테이블의 일종을 출력하는 절차입니다.
- 이 표의 색인에는 동일한 색인에 있는 문서가 유사한 것으로 간주되고 다른 색인에 있는 문서가 "비슷한" 문서들이 들어 있습니다.
- 여기서 유사성은 메트릭시스템에 따라 다르며 LSH의 글로벌파라미터와 같이 동작하는 임계값 유사성에 따라 달라집니다.
- 문제의 적절한 문턱값을 정의하는 것은 사용자에게 달려 있습니다.
서로 다른 유사성 측정이 서로 다른 LSH 구현을 가지고 있다는 점을 강조하는 것이 중요하다.
블로그에서는 min Hashing(자카드의 유사성 측정)과 sim Hashing(코사인 거리 측정)의 경우에 대해 LSH에 대해 자세히 설명하려고 했습니다.도움이 되시길 바랍니다.https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/
저는 시각적인 사람입니다.직감적으로 할 수 있는 게 여기 있어요.
검색하고자 하는 것은 각각 사과, 큐브, 의자 등의 물리적 객체입니다.
LSH에 대한 제 직관은 이러한 물체의 그림자를 찍는 것과 비슷하다는 것입니다.예를 들어, 3D 큐브의 그림자를 취하면 종이에 2D 정사각형 모양의 그림자가 생기거나 3D 구체가 종이에 동그라미 모양의 그림자가 생기거나 합니다.
결국 검색 문제(텍스트의 각 단어가 1차원이 될 수 있음)에는 3차원 이상의 차원이 있지만 섀도우 유추는 여전히 매우 유용합니다.
이제 소프트웨어의 비트 문자열을 효율적으로 비교할 수 있습니다.고정 길이의 비트 문자열은 어느 정도 단일 차원의 선과 같습니다.
LSH를 사용하면 오브젝트의 그림자를 포인트(0 또는 1)로 1개의 고정 길이 선/비트 문자열에 투영합니다.
전체적인 요령은 그림자가 여전히 하위 차원에서도 의미가 있도록 하는 것입니다. 예를 들어, 그림자가 원래의 물체를 인식할 수 있을 만큼 잘 닮았습니다.
원근법으로 큐브를 2D로 그려보면 큐브임을 알 수 있습니다.하지만 투시도 없이 2D 사각과 3D 큐브 섀도를 쉽게 구분할 수 없습니다. 둘 다 사각형처럼 보입니다.
내 물체를 빛에 어떻게 비추느냐에 따라 내가 잘 알아볼 수 있는 그림자가 생기는지 여부가 결정됩니다.그래서 저는 "좋은" LSH가 빛 앞에서 물체를 돌려서 그림자가 내 물체를 가장 잘 나타낼 수 있도록 하는 것이라고 생각합니다.
요약하면:LSH로 인덱싱할 대상을 큐브, 테이블, 의자 등의 물리적 객체로 생각하고 그림자를 2D로 투영하여 최종적으로 선(비트 문자열)을 따라 투영합니다.또, 「좋은」LSH의 「기능」은, 2D 평지에서 대략적으로 구별 가능한 형상을 얻기 위해서, 조명 앞에 물체를 표시하는 방법이며, 나중에 비트 스트링도 사용할 수 있습니다.
마지막으로 내가 가지고 있는 객체가 내가 인덱스를 작성한 객체와 유사한지 여부를 검색하려면 동일한 방법으로 이 "쿼리" 객체의 그림자를 사용하여 조명 앞에 객체를 표시합니다(결국 비트 문자열도 표시됨).그리고 그 비트 문자열이 다른 인덱스 비트 문자열과 얼마나 비슷한지 비교할 수 있습니다.이 비트 문자열은 오브젝트 전체를 검색하는 프록시입니다.만약에 내 오브젝트를 빛에 비추는 좋은 방법을 발견했을 경우입니다.
간단히 말하면 다음과 같습니다.
지역감응 해시의 예로는 먼저 해시할 입력 공간에서 평면을 랜덤하게 설정한 다음(회전 및 오프셋으로) 공간의 해시에 포인트를 드롭하고 점이 그 위 또는 아래에 있는 경우(예: 0 또는 1) 측정하는 각 평면에 대해 해시가 정답입니다.따라서 공간에서 유사한 점은 이전 또는 이후의 코사인 거리로 측정하면 유사한 해시를 가집니다.
다음 예시는 skikit-learn을 사용하여 읽을 수 있습니다.https://github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer
언급URL : https://stackoverflow.com/questions/12952729/how-to-understand-locality-sensitive-hashing
'programing' 카테고리의 다른 글
| 로드 시 Vue.js v-if 및 v-f를 포함하는 HTML 태그 (0) | 2022.06.29 |
|---|---|
| gcc에서 컴파일러 최적화를 비활성화하는 방법 (0) | 2022.06.29 |
| Vue 2. JSX에서 v-html을 사용하는 방법 (0) | 2022.06.29 |
| 자바 클래스 파일 형식의 메이저버전 번호 목록 (0) | 2022.06.29 |
| Vue 라우터 킵얼라이브가 작동하지 않음 (0) | 2022.06.29 |