How I used INFORMATION THEORY to choose better Keybindings

Summary

この動画は、情報理論を使ってEmacsのキーバインドを最適化する方法を紹介しています。キーストロークを情報として見なし、エントロピーを計算し、ハフマン符号化を用いてより効率的なキーバインドを見つけ出します。動画では、作者が実際に使用するEmacsコマンドの頻度を計測し、そのデータを分析して情報理論の原則を応用する方法を示しています。最適なキーバインドを選ぶことで、入力するコマンドを最小限のキーストロークで伝えることができることを示しています。

Takeaways

• 📚 情報理論の概念を利用して、Emacsのキーバインドを最適化する。
• 🕵️ キーストロークとEmacsを通信チャネルで送信する情報として見る。
• 🔢 手のエントロピーを計算し、ハフマン符号化を创造する。
• 🎯 自分のより効率的なキーバインドを考案するためにハフマン符号化を使用する。
• 📈 クロード・香农が電報でメッセージをより効率的に送信する方法を考えるために情報理論を考案。
• 📊 符号化の長さを信号の発生確率に比例させることが最適な符号化であると香农は結論づけた。
• 🔧 自分のEmacs構成にキーロガーを追加し、過去2ヶ月以上実行したEmacsコマンドのデータを収集する。
• 📊 データ解析の結果、最も使用频率の高いコマンドを特定し、効率的なキーバインドを設定する。
• 🌟 情報理論は最適な符号化方法だけでなく、最適解に到達する道を示す。
• 🔄 現在のキーバインドの長さと理想的なキーバインドの長さの差を計算し、改善の余地を特定する。
• 🔄 使用頻度が高いコマンドに対して長すぎるキーバインドを、使用頻度が低いコマンドに対して短すぎるキーバインドを再割り当てる。
• 🛠️ GitHubで分析用のコードを公開し、個人のEmacs設定に適用して結果を共有するよう呼びかけている。

Q & A

この動画で取り上げられている情報理論とは何ですか？

情報理論は、データの通信や処理の効率を最大化するための理論です。この動画では、情報理論を用いてEmacのキーバインドを最適化する方法について説明されています。

クロード・シャノンはどのような状況で情報理論を考案しましたか？

クロード・シャノンは、1940年代にベル研究所で働いていた際に、電報でメッセージをより効率的に送信する方法を考案するために情報理論を発明しました。

Huffmanコードとは何ですか？

Huffmanコードは、符号化されたデータのエントロピーを最小限に抑えるための最適な符号長を算出するアルゴリズムです。この方法は、より一般的な文字に较短い符号を割り当て、レアな文字に较长の符号を割り当てることで、平均的な符号長を短くします。

この動画で収集されたデータはどのように解析されましたか？

動画の作成者は、Emacで使用されるコマンドの出現確率を計算するために、キーロガーをEmacに追加しました。その後、収集されたデータを解析し、各コマンドの使用頻度を算出しました。

情報理論に基づく最適なキーバインドの設定方法は何ですか？

情報理論に基づく最適なキーバインドは、各コマンドが発生する確率に基づいて符号長を割り当てることです。これにより、平均的な符号長を最小限に抑えることができます。

この動画の分析で見つかった最も使用頻度が高いコマンドは何ですか？

この動画の分析で見つかった最も使用頻度が高いコマンドは、自身挿入（self-insert）コマンドです。これは、文字をバッファに入力するという基本的な操作です。

分析結果から明らかな問題は何ですか？

分析結果から明らかな問題は、効率的な符号化が意味を失うことです。たとえば、使用頻度が高いコマンドが複雑なキーシーケンスに割り当てられている場合、ユーザーは覚えることが困難で、直感的でないキーバインドになります。

最適なキーバインドを実際に適用するために、どのような手順を取ること最重要ですか？

最適なキーバインドを適用するためには、使用頻度が高いコマンドに対して短いキーシーケンスを割り当て、使用頻度の低いコマンドに対して長いキーシーケンスを割り当てる必要があります。また、意味を失うことなく、キーバインドを適切に再割り当てることも重要です。

この動画の分析で得られた結果を実際にEmacに適用するために、何が必要でしたか？

実際にEmacに適用するためには、分析で得られた最適なキーバインドを現在のキーバインド設定と比較し、必要な変更を行った後、新しい設定に変更する必要がありました。

情報理論を応用して得られた分析結果は、どのようにUIデザインやHCIに影響を与える可能性がありますか？

情報理論を応用した分析結果は、メニューアイテムの配置やマルチステップメニューの組織など、一般的なUIデザインとHCIにおける最適なレイアウトを見つけるための有力なツールとなる可能性があります。

この動画の作成者が今後取り組みたいと思っているプロジェクトは何ですか？

この動画の作成者は、情報理論とログ記録、分析を用いて、メニューアイテムの配置やマルチステップメニューの組織を決定するウェブサイトを設計したいと考えています。また、この動画で使用したコードを使いやすいライブラリにパッケージ化し、ユーザーインターフェースを提供する予定です。

Outlines

00:00

📚 情報理論を使ったEmacキーバインディングの最適化

この段落では、情報理論の概念を用いてEmacのキーバインディングを最適化するプロセスが説明されています。情報理論は、キーストロークとEmacを通信チャネル上の情報として見なし、エントロピーを計算し、ハフマン符号化を创造的に行うことにより、より効率的なキーバインディングを見つけ出します。また、1940年代にクロード・シャンノンが電報でメッセージをより効率的に送信する方法を考案した際に情報理論が発見された歴史も触れられています。

05:00

🔍 Emacコマンドの確率分布とエントロピーの計算

この段落では、Emacコマンドの使用頻度をデータとして収集し、確率分布を変換し、エントロピーを計算する方法が説明されています。自身のEmac設定にキーロガーを追加し、2ヶ月以上実行することで、コマンドの入力時間、主モード、押されたキーを記録したログファイルが得られました。このデータを使って、最も使用频率の高いコマンドを特定し、情報理論に則った符号化を適用する方法が解説されています。

10:00

💡 現在のキーバインディングと理想的な符号化の比較

最後の段落では、現在のEmacのキーバインディングと情報理論に則った理想的な符号化との比較が行われています。使用頻度が高いコマンドに対して、現在のキーバインディングが長く、効率性が低いことが明らかになります。逆に、使用頻度が低いコマンドに対しては短いキーシーケンスが割り当てられていることが指摘されています。この分析に基づき、効果的にEmacを使用するためのキーバインディングの変更が提案されています。

Keywords

💡情報理論

情報理論は、データの通信や処理の効率を最大化するための理論です。この動画では、情報理論を用いてEmacのキーバインディングを最適化する方法について説明されています。キーストロークやEmacコマンドを通信チャネルで送る情報として捉え、エントロピーを計算し、ハフマン符号化を適用することで、より効率的なキーバインディングを見つけ出します。

💡エントロピー

エントロピーは、情報理論において、情報の不確実性や予測不可能性を定量化するための重要な概念です。この動画では、エントロピーを計算して、Emacエディタのコマンドを最適なキーバインディングにエンコードする方法を探求しています。エントロピーが高いほど、情報の不確実性が高いことを意味し、逆にエントロピーが低いほど、情報の予測が可能で不確実性が低くなります。

💡ハフマン符号化

ハフマン符号化は、符号化された情報のエントロピーを最小限に抑えるためのエンコード技術です。この方法は、出現頻度が高いシンボルに短いビット列を割り当て、出現頻度が低いシンボルには長いビット列を割り当てることで、通信の効率を改善します。動画では、ハフマン符号化を用いてEmacのキーバインディングを最適化する方法が解説されています。

💡キーバインディング

キーバインディングとは、コンピューターのソフトウェアやハードウェアにおいて、特定の機能を実行するために押すべきキーの組み合わせを指します。この動画では、Emacエディタのキーバインディングを最適化し、より効率的なキー操作を実現することを目的としています。

💡Emac

Emacは、GNUプロジェクトによって開発されたテキストエディタで、Emacsと似た機能を持ちますが、より軽量でシンプルなインターフェースを持っています。この動画では、Emacのキーバインディングを最適化する方法について説明されています。

💡キーストローク

キーストロークとは、コンピューターのキーボードで特定のキーを押すことを指します。この動画では、キーストロークを情報理論の観点から分析し、より効率的なキーバインディングを作成する方法を説明しています。

💡最適化

最適化は、システムやプロセスの性能を最大化するためのプロセスです。この動画では、情報理論を用いてEmacのキーバインディングを最適化し、効率的なキー操作を実現することを目指しています。

💡クレア・シャンノン

クレア・シャンノンは、情報理論の奠基者であり、電気通信の効率化に貢献した科学者です。この動画では、彼が電報でメッセージをより効率的に送信する方法を研究した際に情報理論を発見したと説明されています。

💡God Mode

God Modeは、Emacにおいて使用されるVimスタイルのコマンドモードです。このモードでは、一連のキーストロークを組み合わせることで、より高度な編集操作を行うことができます。

💡解析

解析とは、複雑なデータや現象を理解するために、それを分解し、その要素やパターンを研究するプロセスです。この動画では、Emacのキーバインディングの使用頻度を記録し、解析することで、より効率的なキーバインディングを見つけ出す方法が紹介されています。

💡GitHub

GitHubは、ソフトウェア開発において広く使用されるWebベースのバージョン管理システムです。この動画では、情報理論に基づくキーバインディング最適化のコードがGitHubで公開されており、視聴者は自身のEmac設定で同じ分析を試すことができます。

Highlights

The video discusses using information theory to optimize key bindings in Emacs.

Information theory is introduced as a way to view keystrokes in Emacs as information sent over a channel.

The concept of entropy of hands is calculated to improve efficiency.

Huffman encoding is used to create more efficient key bindings.

Information theory was discovered in the 1940s by Claud Shannon at Bell Labs.

The telegraph system and its encoding methods are explained as an analogy for key bindings.

The video demonstrates the process of calculating the entropy of Emacs commands.

A keylogger is used to collect data on the frequency of command usage over two months.

The video shows how to convert frequencies into a probability distribution and calculate entropy.

The average information needed to send commands is found to be 6.5 bits per command.

The video discusses the limitations of using binary notation for key bindings.

The importance of maintaining semantic information in key bindings is emphasized.

The video presents a method to find the optimal length of key bindings based on their usage frequency.

A method to identify and reassign inefficient key bindings is proposed.

The video suggests potential applications of information theory in UI design and HCI.

The creator plans to develop a library with a user interface for easy application of the methods discussed.

The video encourages viewers to run the analysis on their own Emacs configurations.

The video concludes with a call to action for likes, subscriptions, and viewer engagement.

Transcripts

all right so today we're going to be

using Concepts from information Theory

to optimize our key bindings in emac if

you don't know what that is yet don't

worry uh I'm going to give an intro to

information Theory as part of this video

but the tldr is that we're going to view

our keystrokes and emac as information

sent over a channel and then we're going

to calculate the entropy of my hands

create a Huffman encoding and then we're

going to use that encoding to see if I

can come up with more efficient key

bindings for myself so information

theory was discovered in the 1940s when

Claud Shannon was working at Bell labs

to come up with a more efficient way to

send messages over the telegraph you see

the telegraph was an ancient way of

sending messages way back before the

telephone and it worked like this if you

had a message you wanted to send you

would encode each of the letters in the

message as a sequence of dots and dashes

and then you would send that sequence of

dots and dashes over the wire on the

other end someone would receive your

sequence of dots and dashes and use it

to decode the original message now there

are many different ways to encode

letters as sequences of dots and dashes

you're probably familiar with things

like asky encoding but people figured

out very quickly that if they used

shorter sequences for the most common

letters and longer sequences for the

most unusual letters on average they'd

be able to send their messages faster so

Claud Shannon sat down and he thought

about this and he wanted to know what is

the best encoding and how much does it

cost on average to send a message over

the wire to get an intuition for this

let's take a look at a simple encoding

where every character uses a sequence

that's the same length if you have 10

bits then you can encode two to the 10th

different symbols uh which you can see

either by using binary notation or by by

using combinatoric since there are two

choices for each bit going the other way

if you want to encode two to the 10

different symbols you'll need to use at

least 10 bits log 2 of 2 the 10th so

more generally if you want to encode K

different symbols you need at least log

two of K bits to do so now this is only

for when you use a fixed length encoding

for each symbol so what happens if we

use our little tricks and include

shorter encodings for more common

symbols and longer encodings for Less

common symbols I won't prove all of the

math behind it uh may be a good topic

for another video but what Claud shanon

figured out is the best way to do this

is to use an encoding length that's

proportionate to the probability that

the signal occurs so more specifically

if the probability of seeing a

particular symbol is p then the encoding

length for that symbol should be

approximately log 1 over P remember p is

a number between 0 and 1 so 1 over p is

large for low probability events and

close to one for high probability events

if you use this optimal encoding for

each symbol then the average number of

bits you need to send over the wire is

the the sum of the probability each

symbol occurs times the number of bits

you need to encode that symbol in our

analogy the Emax commands are the

symbols that we want to communicate to

the editor our key bindings are a way we

encode that information to quickly enter

the commands on our keyboard some

commands take only one key press or in

our analogy one bit some commands take

two key presses and some commands take

even more what we want to do here is we

want to choose an encoding or choose a

set of key bindings for our editor so

that we can communicate the same

commands in the smallest number of key

presses so as a brief overview what

we're going to be doing is adding a key

logger to my emac figuring out the

probability that I enter each emac

command and then calculating a Huffman

encoding so that the number of key

presses I need is approximately the

optimal value to start out we're going

to need to collect some data I added a

key logger to my emac config that

records the current time major mode and

keys pressed for every emac command that

I enter I couldn't find a package that

logged everything that I wanted so I

actually wrote my own but this

implementation is Loosely based on

keylogger DOL I left this running for

over 2 months and I wound up with a text

file that was over 100 megab today we're

going to look at the data and we're

going to sit down and figure out what

happened I'll be using closure cuz it's

the language I like the most but the

analysis that we're going to be doing

isn't too complicated so any language

implementation will do here before

anything else I need to take this file

and parse it from a CSV the parser

returns each element as a closure list

so I'm just going to quickly parse it

into a map for easier access now the

first thing that I really want to know

is how often do I use each key command

so I'm just going to grab the

frequencies of each command name and

quickly look at some of the output here

but what I really want is the key

commands that I use the most so let's go

ahead and let's sort by the number of

times each command was seen so now if I

go ahead and I run this I can see the

command that I use most often is the

self-insert command which makes sense

because that's literally just typing

characters into a buffer this empty

string that I don't really understand

then there's next line and previous line

which is basically just going up and

down in a document kind of funny that

these are almost exactly the same number

and these two commands that I use to

turn on and off god mode which is

basically just an emex package that

gives you a Vim style command mode

something that's going to be kind of

tricky for us here is that when a key

sequence is bound to an anonymous

function our little logger just outputs

a text representation of the function

which as you can see here is pretty hard

to understand and follow but if we have

to guess what one of these are we're

just going to do our best I'm actually

really enjoying looking through these

just you know for like entertainment so

I'm going to go ahead and show off one

more page of results you can let me know

if you think your commands will look

anything like mine do all right now on

to the main event we're going to convert

these frequencies into a probability

distribution and then we're going to

calculate the entropy of my emac

commands before we start I'm just going

to remove self-insert character and the

empty string from our analysis because I

think it'll make the data harder to

analyze I'm also going to remove the

next three commands two of which

correspond to Mouse movement and one of

which is I search print and car which is

sort of like a self-insert next I just

want to count the number of key command

presses left in our data set and then in

order to get the probability that I'll

enter a particular command I would just

do the number of times I see that

command divided by the total number of

commands entered now I just need to get

the probabilities for every Comm command

in my data set and I can finally compute

the entropy of the commands I enter into

the emac editor now what this is saying

and this is really interesting is that

in order to send all of the commands

that I send to the emac editor I need to

communicate an average of 6.5 bits of

information per command on average I

need to type something that's 6.5 bits

long now we're making a few assumptions

here like that I enter my commands in a

random order and that I'll be able to

memorize and follow the optimal encoding

but in theory it should cost me 6.5 bits

but what does that mean in real terms

well a standard keyboard has 26 letter

keys and 26 other Keys available for use

I'm going to assume that we're inside of

God Mode's action mode so all keys are

available without modifiers and for the

keys that do use modifiers I'm going to

treat them as two separate characters

now we have a really simple model of the

world we have 52 different keys and they

each represent one symbol that we can

send over the wire we can go in reverse

to get the number of bits you can encode

with 52 different symbols which as we

saw earlier is log 2 of 52 or about 5.7

what this means is that if we have an

optimal encoding we can use an average

of one key press one single key press

per emac command but we're not done

cooking you see information Theory tells

us not just how good the optimal

encoding is but it also tells us how to

get there for this video we're going to

be using the python Library da Huffman

for our implementation of Huffman

encoding so going back to the project

I'm just going to import this library

and call it on our list of frequencies

unfortunately the library Returns the

encoding in binary notation rather than

keystrokes so we need to do some extra

work to convert the binary encodings

into key commands basically I did this

by assigning each symbol to a binary

value and then replacing the binary

values in the code with the

corresponding symbol so for example

00000000 followed by

0000001 would be encoded as the key

commands AB in this way every sequence

of five or fewer binary symbols is

encoded as a single key press since 52

is not an even power of two there are

also some symbols of length six this

approach loses a small amount of

information but it's guaranteed to be

valid because it maintains the invariant

that no encoding can be a prefix of

another encoding all right so now let's

take a moment to look through these I

can see that common key commands like

end of line new line and save buffer are

represented as a single key press and

then I can also see that more rarely

used commands are given more complicated

sequences of keys but as you can already

see there's a really obvious problem

here these key bindings don't make any

sense do you think I'm going to

memorize the sequence 2J DQ for a

command that I use one time the standard

emac key bindings are chosen to be short

but they're also chosen to be pneumonic

contrl b stands for backwards character

contrl F stands for forward character

contrl s stands for search the list goes

on encoding commands as sequences of

bits we produced an efficient encoding

but it doesn't provide any value because

it loses all of the semantic information

of what the key command actually does so

now it's time to take our lessons from

information Theory and apply them so

that we can decrease the amount that we

have to type but not increase the amount

that we have to memorize you see

information Theory provides us with one

more key piece of information the length

of a particular symbol should be

approximately log one over the

probability of that symbol occurring

this lets us find in a mathematically

precise way how far our current key

bindings are from the optimal ones to

compute this we also need the length of

the current key Bindings that we

actually use I did log this inside of my

logger but it turns out that the

internals of God mode mangled the way

that my key sequences were logged so I

had to get the list of my currently

active key bindings by running describe

bindings inside of closure mode and then

parsing the output then for each command

I computed the op optimal length of the

key binding for that command so under

the ideal encoding how many key presses

it should take to enter I compared it to

the actual length of the command so the

number of key presses that it takes for

me to enter that command under my

current key bindings now we can go ahead

and compute the difference and figure

out how far the length of our current

key binding is from the ideal value so

now I'm just going to run this and I'm

going to sort by the commands with the

largest difference as you can see this

shows us the commands that we have where

the key bindings are too long these are

the commands that we use constantly but

take a tremendous amount of effort to do

so I'm looking through this list and

it's absolutely wild like forward word

backward word cider Jack in every time I

see one of these commands I'm like God

damn it like obviously I should fix this

intuitively I know what this list is

these are the same commands that annoy

the out of me every day conversely

we can also sort by the commands that

have the most negative difference these

are the commands that have a very short

key sequence but that we don't use very

often so for example by default control

Z is bound to suspend frame which is

basically the same as clicking the

yellow minus to minimize the window and

I pretty much never do this except on

accident and then I'm you know annoyed

that the window is minimized what this

list shows us is what commands we can

unbind from their current key bindings

taken together these two lists tell us

exactly what we need to change and how

to change it specifically we need to

unbind the key bindings in the bad list

and then reassign them to key bindings

in the good list so for example I can

unbind control Z from suspend frame and

then rebind it to save buffer a command

that I use much more frequently we can

keep most of our current key bindings

but rebind all of the worst offenders so

that we can happily use emac with the

smallest amount of typing all of the

code for this video is freely available

on GitHub Link in the description so

you're welcome to try running this

analysis on your own config and see if

you get any useful results if you do run

this for yourself I'm super curious what

happened so if you have any results you

want to share definitely feel free to

reach out or respond in the comments

down below now there's a lot of other

things that I wanted to try as part of

this video but I didn't get to because I

thought it would make the format too

long I think the ideas in this video

have really interesting implications for

general purpose UI design and HCI and I

would love to design a website that uses

the principles of information Theory

along with a lot of logging and

analytics to determine how menu items

are laid out on the main page and how

nestic levels or multi-step menus are

organized I also made a lot of

approximations during the course of this

video one of the biggest being that I

did not consider the optimal way to

assign key bindings to a multi-step

sequence of commands this is super

important in taking discrete symbols to

their information theoretic limits and

also intuitively I think it will

represent things that should be emac

commands so key sequence that I use

frequently that are doing something and

could be represented by a higher level

concept I'm also planning to repackage a

lot of the code in this video into an

easy to use library with a nice user

interface so if you don't know anything

about information Theory you can just

run this and see what key bindings you

need to change and I'll add all the code

for that into the GitHub link that's

already in the description anyway if you

made it this far give the video a like

subscribe to the channel and I'll see

you in the next one I also want to thank

you guys for helping me reach 1,000

subscribers I know it's kind of dumb but

it's truly the motivation I need to keep

this channel going anyway thanks so much

for watching and I'll see you in the

next one